Results 1 to 5 of 5

Math Help - How to calculate the

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    5

    How to calculate the

    ...solution of a congruence with modulo notation from the reciprocal



    Hey guys, new to the forum. I have been looking through my notes and I am stuck on an area of my number theory module.

    I understand the modulo notation and for example that 14 ≡ 2 mod 12, etc etc.

    I have the reciprocals (modulo 15):

    1bar = 1
    2bar = 8
    3bar = No such x, also 5bar, 6bar, 9bar, 10bar, 12bar do not exist
    4bar = 4
    7bar = 13
    8bar = 2
    11bar = 11
    13bar = 7
    14bar = 14

    I know this is just the reverse process but if someone could explain to me step by step how these solutions are found that would be great.

    Thanks
    Last edited by Hamster Jam; December 30th 2009 at 01:40 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     (a,m)=1 \Longleftrightarrow \exists \; x,y \in \mathbb{Z} \text{ s.t. } ax+my=1 .

    Hence  (a,m)=1 \Longleftrightarrow \exists \; x \in \mathbb{Z} \text{ s.t. } ax \equiv 1 \mod{m} .

    So your example demonstrates this fact and notice the reciprocal of  a can be found through the Euclidean algorithm.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,865
    Thanks
    744
    Hello, Hamster Jam!

    Here's a primitive (but very simple) approach . . .


    Finding reciprocals in modulo notation.

    I have the reciprocals (mod 15):

    . . \begin{array}{ccc}\overline 1 &=& 1 \\<br />
\overline 2 &=& 8 \\ \overline 4 &=& 4 \\ \overline7 &=&13 \\ \overline 8 &=& 2 \\ \overline{11} &=& 11 \\ \overline{13} &=& 7 \\ \overline{14} &=& 14 \end{array}

    No reciprocals for 3, 5, 6, 9, 10, or 12.

    If someone could explain to me step by step
    how these solutions are found, that would be great.

    Let's find the reciprocal of 7.

    We want a number x such that: . 7\!\cdot\! x \:\equiv\:1 \;\text{(mod 15)}

    That is: . 7x \:=\:15a + 1 for some integer a.

    Solve for x\!:\quad x \:=\:\frac{15a+1}{7} \quad\Rightarrow\quad x \:=\:2a + \frac{a+1}{7}

    Since x is an integer, a\!+\!1 must be a multiple of 7.

    The first time this happens is: . a = 6

    Hence: . x \:=\:2(6)+\frac{6+1}{7} \:=\:13

    . . Therefore, the reciprocal of 7 is 13 (in mod 15).

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,234
    Thanks
    1795
    I would do this slightly differently from Soroban. To find the reciprocal of 7 (mod 15) we need, as Soroban said, 7x= 15a+ 1 for some integers x and a. That is the same as the Diophantine equation 7x- 15a= 1. Now, 7 divides into 15 twice with remainder 1: 15= 2(7)+ 1 which is the same as (-2)(7)- (-1)15= 1 so that x= -2 is a solution. But we want a number between 0 and 14 so add 15: 15-2= 13 is between 0 and 15 and is equivalent to -2 (mod 15). As I said, only slightly different from Soroban.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2009
    Posts
    5
    Thanks for the replies! Using HallsofIvy's method, when I apply the method to an actual problem I am having trouble. please state where I am going wrong! Im guessing it's in calculating the reciprocals. Sorry about the poor notation!

    x ≡ 3 (mod 4)
    x ≡ 4 (mod 5)
    x ≡ 2 (mod 7)

    is the set of congruences I have to solve.

    M = (4x5x7) = 140
    M1 = (7x5) = 35
    M2 = (4x7) = 28
    M3 = (4x5) = 20

    Now the reciprocals:

    M1bar = 35bar ≡ 3bar (mod 4)

    3x = 4a +1
    3x - 4a =1
    4 = 1(3) + 1
    (-1)(3) - (-1)(4) =1
    x = -1 is a solution. but we need a solution in between 0 and 2. so add 3,

    M1bar = 2

    now calculate M2bar = 28bar ≡ 3bar (mod 5)

    3x = 5a +1
    3x - 5a = 1
    5 = 1(3) + 2
    (-1)(3) - (-1)(5) = 2
    x = -1 is a solution. add 5

    M2bar = 4

    now calculate M3bar = 20bar ≡ 6bar (mod 7)

    6x = 7a +1
    6x - 7a = 1
    7 = 1(6) + 1
    (-1)(6) - (-1)(7) = 1
    x = -1 is a solution, but we add 7

    M3bar = 6

    using the formula
    x ≡ a1*M1*M1bar+...+an*Mn*Mnbar (mod M)

    I get x = (3*35*2) + (4*28*4) +(2*20*6)

    x = 898 ≡ 58 (mod 140).

    This answer is incorrect however.

    A little bit more help required!

    Thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is it possible to calculate x and y....
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 29th 2010, 02:16 PM
  2. calculate
    Posted in the Algebra Forum
    Replies: 5
    Last Post: April 27th 2010, 10:35 AM
  3. Calculate
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 14th 2010, 03:11 AM
  4. Calculate M4
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 29th 2010, 09:44 PM
  5. Calculate this sum
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 29th 2009, 12:50 AM

Search Tags


/mathhelpforum @mathhelpforum