Meaningless Drivel is fun!
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
Author

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!

Thanks.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 19357
    
  10

Then first explain in words how to do it. The second step would be to change those words into code.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Extended Euclidean Algorithm