Results 1 to 10 of 10

Thread: [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: $\displaystyle 9x \equiv 21 (mod 30)$

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

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

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

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

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

    This was an example in class, but I do believe the last line should say: $\displaystyle \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 $\displaystyle \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 $\displaystyle 3x \equiv 7 (mod 10)$ translate to $\displaystyle x \equiv 7 \cdot 3x \equiv 7 \cdot 7$?
    - Why is $\displaystyle 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: $\displaystyle 9x \equiv 21 (mod 30)$
    Let $\displaystyle (9,30) = 3$ and $\displaystyle 3|21$ so there is a solution.
    If $\displaystyle x$ is a solution the other non-congruence solutions are: $\displaystyle 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 $\displaystyle (9,30) = 3$ and $\displaystyle 3|21$ so there is a solution.
    If $\displaystyle x$ is a solution the other non-congruence solutions are: $\displaystyle 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 $\displaystyle 9x\equiv 21(\bmod 30)$ if and only if $\displaystyle 9x\equiv 21(\bmod 3)$ and $\displaystyle 9x\equiv 21(\bmod 10)$. The first congruence, $\displaystyle 9x\equiv 21(\bmod 3)$, is true for any $\displaystyle x\in \mathbb{Z}$ - so it does not tell us anything. The second congruence, $\displaystyle 9x\equiv 21(\bmod 10)$ can be simplified to $\displaystyle -x\equiv 1(\bmod 10)\implies x\equiv 9(\bmod 10)$. Therefore, $\displaystyle 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 $\displaystyle 9x\equiv 21(\bmod 30)$ if and only if $\displaystyle 9x\equiv 21(\bmod 3)$ and $\displaystyle 9x\equiv 21(\bmod 10)$. The first congruence, $\displaystyle 9x\equiv 21(\bmod 3)$, is true for any $\displaystyle x\in \mathbb{Z}$ - so it does not tell us anything. The second congruence, $\displaystyle 9x\equiv 21(\bmod 10)$ can be simplified to $\displaystyle -x\equiv 1(\bmod 10)\implies x\equiv 9(\bmod 10)$. Therefore, $\displaystyle x=9$ is an example of a solution to the congruence.
    How can the second congruence $\displaystyle 9x\equiv 21(\bmod 10)$ be simplified to $\displaystyle -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 $\displaystyle 9x\equiv 21(\bmod 10)$ be simplified to $\displaystyle -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 $\displaystyle 9\equiv -1(\bmod 10)$ so I replaced $\displaystyle 9x$ with $\displaystyle -x$ and $\displaystyle 21\equiv 1(\bmod 10)$ so I replaced $\displaystyle 21$ by $\displaystyle 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 $\displaystyle 9\equiv -1(\bmod 10)$ so I replaced $\displaystyle 9x$ with $\displaystyle -x$ and $\displaystyle 21\equiv 1(\bmod 10)$ so I replaced $\displaystyle 21$ by $\displaystyle 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,410
    Thanks
    1
    (1) Recall that: $\displaystyle (a,b) = 1 \ \Leftrightarrow \ ax + by = 1 \ \Leftrightarrow \ ax \equiv 1 \ (\text{mod b})$

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

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

    Thus, $\displaystyle -3$ is the multiplicative inverse of 3. But since we usually work with least residues, we consider: $\displaystyle -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. $\displaystyle 7 \cdot 3 \equiv 1 \ (\text{mod } 10)$:
    $\displaystyle \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: $\displaystyle (a,b) = 1 \ \Leftrightarrow \ ax + by = 1 \ \Leftrightarrow \ ax \equiv 1 \ (\text{mod b})$

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

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

    Thus, $\displaystyle -3$ is the multiplicative inverse of 3. But since we usually work with least residues, we consider: $\displaystyle -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. $\displaystyle 7 \cdot 3 \equiv 1 \ (\text{mod } 10)$:
    $\displaystyle \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 $\displaystyle x$ & $\displaystyle y$ for $\displaystyle (a,b) = 1 = ax + by$, so whatever $\displaystyle 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 $\displaystyle 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,410
    Thanks
    1
    (1) Yes. Remember, a number has a multiplicative inverse if and only if it is coprime with the modulus, i.e. $\displaystyle (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: Apr 1st 2010, 12:02 PM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 24th 2010, 05:11 AM
  3. Congruence Theory Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 2nd 2009, 03:48 AM
  4. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 1st 2009, 05:48 AM
  5. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 3rd 2008, 10:04 AM

Search Tags


/mathhelpforum @mathhelpforum