File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Extended Euclidean Algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Extended Euclidean Algorithm" Watch "Extended Euclidean Algorithm" New topic

Extended Euclidean Algorithm

Cheryl Scodario
Ranch Hand

Joined: Nov 28, 2009
Posts: 69
Hi all, I am doing an encryption program, and need to find the x and y in this formula: gcd(a,b)=a*x+b*y;
I know the idea is to follow the steps of the actual Euclidean algorithm, and then just doing everything backwards, but I don't know how to put that in code.
One thing to note, gcd (a, b) will be 1 in my case, because a and b are coprime. so basically we are looking at 1=a*x+b*y and find x and y.
Please give me some hints!

Paul Clapham

Joined: Oct 14, 2005
Posts: 19413

Then first explain in words how to do it. The second step would be to change those words into code.
I agree. Here's the link:
subject: Extended Euclidean Algorithm