[SOLVED] Linear Congruence Theory

**star_tenshi** · February 8th 2009, 07:02 PM

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.

**ThePerfectHacker** · February 8th 2009, 08:16 PM

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: $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$ .

**star_tenshi** · February 8th 2009, 08:30 PM

Originally Posted by ThePerfectHacker

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?

**ThePerfectHacker** · February 8th 2009, 08:40 PM

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.

**star_tenshi** · February 8th 2009, 08:56 PM

Originally Posted by ThePerfectHacker

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

**ThePerfectHacker** · February 8th 2009, 09:02 PM

Originally Posted by star_tenshi

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

**star_tenshi** · February 8th 2009, 09:24 PM

Originally Posted by ThePerfectHacker

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.

**o_O** · February 8th 2009, 11:05 PM

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

**star_tenshi** · February 9th 2009, 07:34 AM

Originally Posted by o_O

(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?

**o_O** · February 9th 2009, 07:40 AM

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

Thread: [SOLVED] Linear Congruence Theory

LinkBack

Thread Tools

Display

[SOLVED] Linear Congruence Theory

Similar Math Help Forum Discussions

Group theory problem with congruence relations

Linear Congruence

Congruence Theory Proof

Linear congruence

Linear Congruence

Search Tags