Use the Euclidean Algorithm to find the the inverse to 297 mod 349.
Can someone show the steps on how to do this...
Thanks in advance.
It's actually the enhanced Euclidean algorithm - when you get a new number r (at each step), you calculate a and b such that r = ax + by, where x and y are the original numbers.
I can get you started:
349 = 0 * 297 + 1 * 349
297 = 1 * 297 + 0 * 349
52 = 349 - 297 = -1 * 297 + 1 * 349
37 = 297 - 5 * 52 = 297 - 5 * (-1 * 297 + 1 * 349) = 6 * 297 + -5 * 349
You might want to organize the work with a table. A spreadsheet works pretty well, too.
When you get to 1 = a * 297 + b * 349, you have a * 297 congruent to 1 (mod 349), so a is the inverse of 297. If you don't ever get to 1, then the gcd of the two numbers is not 1, and the inverse doesn't exist.
Post again if you're still having trouble.