Results 1 to 10 of 10

Math Help - [SOLVED] Linear Congruence Theory

  1. #1
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32

    [SOLVED] Linear Congruence Theory

    I have a question on the calculations in linear congruences if somebody could please clear up for me?

    Say for example, the linear congruence: 9x \equiv 21 (mod 30)

    We check that there are solutions: (9,30)=1 & 3|21 \Rightarrow 3 incongruent solutions.

    Then simplify to: 3x \equiv 7 (mod10)

    Then check if they are relatively prime s.t. there exists a multiplicative inverse, \overline{3}, such that 3 \cdot \overline{3} \equiv 1 (mod 10):
    (3,10) = 1 \Rightarrow \exists \overline{3}, such that 3 \cdot \overline{3} \equiv 1 (mod 10).

    The we use the Euclidean Algorithm to find \overline{3}:
    10 = 3 \cdot 3 + 1
     3 = 1 \cdot 3
     \overline{3} \equiv (-3) \equiv 7 (mod 10)
    \Rightarrow 3 \cdot 7 \equiv 1 (mod 10)

    Then going back to the original question:
     3x \equiv 7 (mod 10)
    \Leftrightarrow x \equiv 7 \cdot 3x \equiv 7 \cdot 7 \equiv 9 (mod 10)
    \Rightarrow x \equiv 9,19,29 (mod 30)

    This was an example in class, but I do believe the last line should say: \Rightarrow x = 9,19,29 \equiv 9 (mod 30)

    My question is:
    1. - How do we get the multiplicative inverse from the Euclidean Algorithm?
    - Specifically, how does one get \overline{3} \equiv (-3) (mod 10) from the Euclidean Algorithm?
    - Which 3 are we looking at in the algorithm?

    2. - How does the original question of  3x \equiv 7 (mod 10) translate to x \equiv 7 \cdot 3x \equiv 7 \cdot 7?
    - Why is 3x suddenly changed to 7?

    Other than that, I think I understand all of the other steps. Just couple of small hiccups in the theory I don't understand. Any help would be much appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by star_tenshi View Post
    I have a question on the calculations in linear congruences if somebody could please clear up for me?

    Say for example, the linear congruence: 9x \equiv 21 (mod 30)
    Let (9,30) = 3 and 3|21 so there is a solution.
    If x is a solution the other non-congruence solutions are: x+\tfrac{30}{3}\cdot 0, x + \tfrac{30}{3}\cdot 1, x + \tfrac{30}{3}\cdot 2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Quote Originally Posted by ThePerfectHacker View Post
    Let (9,30) = 3 and 3|21 so there is a solution.
    If x is a solution the other non-congruence solutions are: x+\tfrac{30}{3}\cdot 0, x + \tfrac{30}{3}\cdot 1, x + \tfrac{30}{3}\cdot 2.
    Sorry ThePerfectHacker, I know the form of the answers, and how many there are, but it's the theory and the calculation that I don't understand. Could you please clarify my two questions at the bottom of my original post?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I help you find one solution . If 9x\equiv 21(\bmod 30) if and only if 9x\equiv 21(\bmod 3) and 9x\equiv 21(\bmod 10). The first congruence, 9x\equiv 21(\bmod 3), is true for any x\in \mathbb{Z} - so it does not tell us anything. The second congruence, 9x\equiv 21(\bmod 10) can be simplified to -x\equiv 1(\bmod 10)\implies x\equiv 9(\bmod 10). Therefore, x=9 is an example of a solution to the congruence.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Quote Originally Posted by ThePerfectHacker View Post
    I help you find one solution . If 9x\equiv 21(\bmod 30) if and only if 9x\equiv 21(\bmod 3) and 9x\equiv 21(\bmod 10). The first congruence, 9x\equiv 21(\bmod 3), is true for any x\in \mathbb{Z} - so it does not tell us anything. The second congruence, 9x\equiv 21(\bmod 10) can be simplified to -x\equiv 1(\bmod 10)\implies x\equiv 9(\bmod 10). Therefore, x=9 is an example of a solution to the congruence.
    How can the second congruence 9x\equiv 21(\bmod 10) be simplified to -x\equiv 1(\bmod 10)?

    (I believe your method to the solution is different from the way I was taught in class to solve linear congruences.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by star_tenshi View Post
    How can the second congruence 9x\equiv 21(\bmod 10) be simplified to -x\equiv 1(\bmod 10)?

    (I believe your method to the solution is different from the way I was taught in class to solve linear congruences.)
    Because 9\equiv -1(\bmod 10) so I replaced 9x with -x and 21\equiv 1(\bmod 10) so I replaced 21 by 1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Quote Originally Posted by ThePerfectHacker View Post
    Because 9\equiv -1(\bmod 10) so I replaced 9x with -x and 21\equiv 1(\bmod 10) so I replaced 21 by 1.
    Oh. I was never taught that way, so I didn't understand. I'm still lost, but thanks for trying to help though.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    (1) Recall that: (a,b) = 1 \ \Leftrightarrow \ ax + by = 1 \ \Leftrightarrow \ ax \equiv 1 \ (\text{mod b})

    So by using the algorithm, we have: 1 = 10(1) + 3(-3)

    This is equivalent to saying: 3(-3) \equiv 1 \ (\text{mod } 10)

    Thus, -3 is the multiplicative inverse of 3. But since we usually work with least residues, we consider: -3 \equiv 7 \ (\text{mod } 10) to be the inverse.

    _____________________

    (2) We're just using the fact that the multiplicative inverse of 3 is 7 (modulo 10), i.e. 7 \cdot 3 \equiv 1 \ (\text{mod } 10):
    \begin{array}{rcll} 3x & \equiv & 7 & (\text{mod } 10) \\ {\color{red}7} \cdot 3x & \equiv & {\color{red}7} \cdot 7 & (\text{mod } 10) \\ x & \equiv & 49 & (\text{mod } 10) \\ x & \equiv & 9 & (\text{mod } 10) \end{array}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Quote Originally Posted by o_O View Post
    (1) Recall that: (a,b) = 1 \ \Leftrightarrow \ ax + by = 1 \ \Leftrightarrow \ ax \equiv 1 \ (\text{mod b})

    So by using the algorithm, we have: 1 = 10(1) + 3(-3)

    This is equivalent to saying: 3(-3) \equiv 1 \ (\text{mod } 10)

    Thus, -3 is the multiplicative inverse of 3. But since we usually work with least residues, we consider: -3 \equiv 7 \ (\text{mod } 10) to be the inverse.

    _____________________

    (2) We're just using the fact that the multiplicative inverse of 3 is 7 (modulo 10), i.e. 7 \cdot 3 \equiv 1 \ (\text{mod } 10):
    \begin{array}{rcll} 3x & \equiv & 7 & (\text{mod } 10) \\ {\color{red}7} \cdot 3x & \equiv & {\color{red}7} \cdot 7 & (\text{mod } 10) \\ x & \equiv & 49 & (\text{mod } 10) \\ x & \equiv & 9 & (\text{mod } 10) \end{array}
    Thank you very much o_O for clearing things up for me again.

    (1) We are just using GCD theorem to find x & y for (a,b) = 1 = ax + by, so whatever b is, that should be the multiplicative inverse since the GCD is 1, right?

    (2) The purpose of multiply both sides of the congruence by the multiplicative inverse is to isolate x so that we can find its congruence modulo m to find all solutions?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    (1) Yes. Remember, a number has a multiplicative inverse if and only if it is coprime with the modulus, i.e. (a,m) = 1. And we know that "GCD theorem" of yours (i.e. Bézout's identity).

    (2) Exactly. They just wrote it on one line so it may have been a bit confusing that way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Group theory problem with congruence relations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2010, 01:02 PM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 06:11 AM
  3. Congruence Theory Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 2nd 2009, 04:48 AM
  4. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 06:48 AM
  5. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 3rd 2008, 11:04 AM

Search Tags


/mathhelpforum @mathhelpforum