# Thread: [SOLVED] Linear Congruence Theory

1. ## [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.

2. Originally Posted by star_tenshi
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$.

3. Originally Posted by ThePerfectHacker
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?

4. 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.

5. Originally Posted by ThePerfectHacker
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.)

6. Originally Posted by star_tenshi
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$.

7. Originally Posted by ThePerfectHacker
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.

8. (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}$

9. Originally Posted by o_O
(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?

10. (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.