Results 1 to 2 of 2

Math Help - Euclidean Algorithm

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Euclidean Algorithm

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 10:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum