This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
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

Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
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: 18541

Then first explain in words how to do it. The second step would be to change those words into code.
Don't get me started about those stupid light bulbs.
subject: Extended Euclidean Algorithm
Similar Threads
GCD calculation using Euclidean algorithm fails
if gcd(a,b)=1 , what happens?
GCD/LCM problems
Card Shuffle Problem
I got it, but is my code sloppy?