Results 1 to 7 of 7

Math Help - Modulo calculation and Euclid's algorithm

  1. #1
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170

    Modulo calculation and Euclid's algorithm

    Hi,

    im having some difficulties when trying to calculate the modulo inverse.

    for example:
    X = 12 mod 31
    X = 20 mod 41 (I don't know how to write that in LaTex =/)

    So we need to find u and v such that 31u + 41v = 1

    They're both co-prime. My problem is that i don't understand how to run the Euclid's algorithm "backwards"

    /Best regards Jones
    Last edited by Jones; October 8th 2008 at 07:40 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by Jones View Post
    Hi,

    im having some difficulties when trying to calculate the modulo inverse.

    for example:
    X = 12 mod 31
    X = 20 mod 41 (I don't know how to write that in LaTex =/)

    So we need to find u and v such that 31u + 41v = 1

    They're both co-prime. My problem is that i don't understand how to run the Euclid's algorithm "backwards"

    /Best regards Jones
    Here is how I do.

    You know that when you finish the Euclidian algorithm, you'll get the gcd of 41 and 31 as a remainder, namely 1.

    Start from the greatest integer :
    41=31+10 ----> 10=41-31
    In each step, write what the remainder is. Then continue the Euclidian algorithm :
    31=10x3+1
    Write the remainder :
    1=31-10x3

    But you know what 10 is. So substitute it in 1 :
    1=31-3x(41-31) = 31-3x41+3x31=4x31-3x41
    What's the point of all of this ? It's that you can express any remainder in terms of 41 and 31.

    So from 1=4x31-3x41, you have u and v.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Thank you so much Moo!

    Now, are -3 and 4 the inverse of [LaTeX ERROR: Convert failed] and
    [LaTeX ERROR: Convert failed] ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Jones View Post
    Thank you so much Moo!

    Now, are -3 and 4 the inverse of [LaTeX ERROR: Convert failed] and
    [LaTeX ERROR: Convert failed] ?
    Hmmm no !!!

    You have x=4 \times 31-3 \times 41

    The inverse of 12 mod 31 can be calculated this way :
    we need to find a such that 12a \equiv 1 \bmod 31

    ---------------------------------------
    But looking further into your problem, I don't see why you need to find u and v in 31u+41v=1.. is there an explanation on this in your notes ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Hi,

    Well i need to solve the equation [LaTeX ERROR: Convert failed]
    [LaTeX ERROR: Convert failed] and i am not sure how to do it. My book states that you need to find the largest common divider, which is 1 and run the Euclid's algorithm backwards to find the inverse....Sigh, isn't there an easier way?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2008
    Posts
    64
    Quote Originally Posted by Jones View Post
    Hi,



    So we need to find u and v such that 31u + 41v = 1

    /Best regards Jones

    41=1\cdot 31+10\\31
    31=3\cdot 10+1
    10=10\cdot 1+0

    From the second equation we have
    1=31-3\cdot 10
    1 =31-3(41-31) by the first eq.
     <br />
1=4\cdot 31-3\cdot 41<br />
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Are there any general formula for the solutions, if there are more than one solution?

    Could you please show me one more time. For example this modulo congruence system:
    <br />
\begin{array}{rcll} x & \equiv & 6 & \text{mod } 9 \\ x & \equiv & 3 & \text{mod } 13 \\ x & \equiv & 5 & \text{mod } 16 \end{array}<br />



    /Jones
    Last edited by Jones; October 11th 2008 at 04:03 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 11:32 AM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum