Results 1 to 5 of 5

Math Help - reverse euclidean algorithm

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    20

    reverse euclidean algorithm

    Hi all,
    I can't solve this.
    x = 18^-1 mod 31
    I know that I have to use thew reverse euclidean algorithm but I don't see how since 1/18 is not a integer
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    It could be a badly written way of saying 18x\equiv1\!\!\!\pmod{31}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    18x\equiv 1 (\bmod 31)
    18x \equiv -30(\bmod 31)
    3x\equiv -5(\bmod 31)
    3x\equiv -36(\bmod 31)
    x\equiv -12(\bmod 31)
    x\equiv 19(\bmod 31)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,686
    Thanks
    617
    Hello, maria_stoeva!

    Here's a very primitive solution . . .


    Solve: . x \:\equiv \:18^{-1}\pmod{31}

    We have: . 18x \:\equiv \:1 \pmod{31}

    That is: . 18x - 1 \:=\:31a\:\text{ for some integer }a

    Solve for x\!:\;\;x \:=\:\frac{31a+1}{18} \:=\:a + \frac{13a+1}{18}\;\;{\color{blue}[1]}


    Since x is an integer, 13a + 1 must be a multiple of 18.
    . . That is: . 13a + 1 \:=\:18b\:\text{ for some integer} b

    Solve for a\!:\;\;a \:=\:\frac{18b-1}{13} \:=\:b + \frac{5b-1}{13}\;\;{\color{blue}[2]}


    Since a is an integer, 5b-1 must be a multiple of 13.
    . . That is: . 5b-1 \:=\:13c\:\text{ for some integer } c

    Solve for b\!:\;\;b \:=\:\frac{13c+1}{5} \:=\:2c + \frac{3c+1}{5} \;\;{\color{blue}[3]}


    Since b is an integer, 3c+1 must be a multiple of 5.
    . . This first happens when: c = 3

    Substitute into [3]: . b \:=\:2(3) + \frac{3(3)+1}{5} \quad\Rightarrow\quad b\:=\:8

    Substitute into [2]: . a \:=\:8 + \frac{5(8)-1}{13} \quad\Rightarrow\quad a \:=\:11

    Substitute into [1]: . x \:=\:11 + \frac{13(11)+1}{18} \quad\Rightarrow\quad\boxed{ x \:=\:19}


    Therefore: . 19 \:\equiv\:18^{-1} \pmod{31}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by maria_stoeva View Post
    Hi all,
    I can't solve this.
    x = 18^-1 mod 31
    I know that I have to use thew reverse euclidean algorithm but I don't see how since 1/18 is not a integer
    Thanks
    ThePerfectHacker has a very neat solution.

    But in case you ever need to know how to do the inverse GCD,
    you still need to do the forward GCD.

    So
    Code:
    31 = 18 + 13
    18 = 13 + 5
    13 = 2*5 + 3
    5 = 1*3 + 2
    3 = 1*2 + 1
    2 = 2*1 + 0
    As you can can see the gcd(18,31) = 1

    And by the theorem of the gcd, you can find integers u,v such that
    1 = u*31 + v*18

    So, the algorithm now in reverse:
    Code:
    3 = 1 * (2) + 1
    rearranging
    
    1 = (3) - 1(2) and from the line before that 2 = 5 - 3
    1 = (3) - 1(5 -3)
    1 = 2*(3)  - 1*(5) and from the line before that 3 = 13 - 2*5
    1 = 2*(13 - 2*5) - 1*5
    1 = 2*13 -5*5 and from the line before that 5 = 18 - 13
    1 = 2 * 13 - 5*(18 -13)
    1 = 7*13 - 5 * 18 and from the line before that 13 = 31 - 18
    1 = 7*31 - 12 * 18
    1 = 7*31 + ( -12)*(18)
    Now in modulo 31,
    1= (-12) * 18
    1 = 19 * 18

    which is the same answer as before.

    The hardest part of modulo arithmetic is realizing that there is no such thing as division, but only multiplicative inverse.

    and that 18^-1 is not 0.05555555.
    It is true if you consider the real numbers, but not in this case.
    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. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 24th 2010, 09:54 PM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  5. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM

Search Tags


/mathhelpforum @mathhelpforum