1. ## Reducing the modulo

Sorry about the title, I can't remember how this works and after an hour on the internet I still have no clue what to call it. I would like to check my method on the following equations.

Solve $6x \equiv 3~\text{(mod 9)}$

Since $gcd(6, 9) = 3 \neq 1$ we can divide through and get
$2x \equiv 1~\text{(mod 3)}$

This is the line I am not sure of, but it does give a correct answer (x = 2) for the original equation.

again,
Solve $6x \equiv 3~\text{(mod 7)}$

Now in this case gcd(6, 7) = 1, so we can't "reduce" the mod by dividing.

How far off base am I? I could swear I've seen some way to reduce the mod to make the equation simpler, but I cannot for the life of me remember what the circumstances were.

-Dan

2. Originally Posted by topsquark
Solve $6x \equiv 3~\text{(mod 9)}$

Since $gcd(6, 9) = 3 \neq 1$ we can divide through and get
$2x \equiv 1~\text{(mod 3)}$
By definition: $6x \equiv 3 (\bmod.9)$ if and only if $9$ divides $(6x-3) = 3\cdot ( 2x - 1)$, and this happens if and only if $3$ divides $2x-1$ -since we need another factor of 3- i.e. $2x\equiv 1 (\bmod.3)$ indeed.

(note then that it is true that if both sides have a common factor that divides the module we can divide everything - both sides and the module - by that number )

Originally Posted by topsquark

Solve $6x \equiv 3~\text{(mod 7)}$

Now in this case gcd(6, 7) = 1, so we can't "reduce" the mod by dividing.
Yes, but in this case since $\text{gcd}(6, 7) = 1$ it follows that 6 has a multiplicative inverse module 7 .
In fact $6\equiv -1 (\bmod.7)$ so you have $-x\equiv 3 (\bmod.7)$ ...

More generally, if you wanted to find the modular inverse here are a couple of ways:
1. Use the extended euclidean algorithm -this works always.
2. If the module were a prime $p$, note that by Fermat's Little Theorem, since $a^{p-1}\equiv 1 (\bmod. p)$ then $a$ and $a^{p-2}$ are modular inverses, and so you compute $a^{p-2}(\bmod.p)$ by repeatedly squaring and taking modules at each step.

3. So if I understand this:

Solve $4x \equiv 6 ~\text{(mod 10)}$

We have gcd(4, 10) = 2. Thus we know that if 4x - 6 = 2(2x - 3) is divisible by 10 then 2x - 3 is divisible by 5.

Thus we can solve $2x \equiv 3 ~\text{(mod 5)}$

which has x = 4 as its only solution (mod 5), thus x = 4 is the only solution (mod 10) to the original problem as well. (check!)

-Dan

4. Almost correct , $x \equiv 4 (\bmod.5)$ means that either $x\equiv 4 (\bmod.10)$ or $x\equiv 9 (\bmod.10)$

Note that you have a degree of freedom in what $x$ is in module 2 . This happnes because fixing the values of $x(\bmod. b_1)$ and $x (\bmod.b_2)$ determines uniquely $x (\bmod.b_1\cdot b_2)$ and viceversa, when $(b_1,b_2)=1$. (this is a particular case of the Chinese Remainder Theorem )

5. Originally Posted by PaulRS
Almost correct , $x \equiv 4 (\bmod.5)$ means that either $x\equiv 4 (\bmod.10)$ or $x\equiv 9 (\bmod.10)$

Note that you have a degree of freedom in what $x$ is in module 2 . This happnes because fixing the values of $x(\bmod. b_1)$ and $x (\bmod.b_2)$ determines uniquely $x (\bmod.b_1\cdot b_2)$ and viceversa, when $(b_1,b_2)=1$. (this is a particular case of the Chinese Remainder Theorem )
Thanks. That's actually explains something I had found. In mod 5 the only answer was x = 4. But in mod 10 I could construct a general solution x = 5n + 4 (mod 10) for integer n, but I couldn't find a way to do that in mod 5.

-Dan