Congrences

• Jul 19th 2008, 03:29 AM
free_to_fly
Congrences
Could someone please explain to me how to do this question:

3x=5(mod 7)
The answer is 4 but I'm not sure how to get there.

Help would be appreciated.
• Jul 19th 2008, 03:56 AM
Moo
Hello,

Quote:

Originally Posted by free_to_fly
Could someone please explain to me how to do this question:

3x=5(mod 7)
The answer is 4 but I'm not sure how to get there.

Help would be appreciated.

You have to perform a division :

$x=5 \cdot 3^{-1} \bmod 7$

But you have to calculate $a=3^{-1}$, which is a such that $3a=1 \bmod 7$

One can see that $15=3*5=1 \bmod 7$

So $a=5 \bmod 7$

Therefore :

$3x=5 \bmod 7 \Longleftrightarrow \overbrace{3a}^{1}x=5a \bmod 7$

$\implies x=5a \bmod 7 \implies x=25 \bmod 7 \implies x=4 \bmod 7$
• Jul 19th 2008, 04:36 AM
free_to_fly
Ok, I think I more or less follow the previous explanation, but for this question I'm a little confused still:
Q: 6x=2 (mod 8)

$x=2 \cdot 6^{-1} \bmod 8$

but this cancels to:
$
x=1 \cdot 3^{-1} \bmod 8$
(not sure if I can cancel like that)
So $
a=3^{-1}
$

$
3a=1 \bmod 8$

But 3*3=9=1 (mod 8) so
$
a=3 \bmod 8
$

This gives x=3 (mod 8)
I know the answer is suppose to be x=3(mod 8) please can you show me where I went wrong.
• Jul 19th 2008, 04:54 AM
Moo
Yes, I forgot to mention it. There is an inverse if and only if they are coprime.

What I mean is that a has an inverse modulo n, if and only if a and n are coprime.

Why ?

Here, $6x=2 \bmod 8$

Going back to the definition of the congruence, we have : $6x-2=8k$, where $k \in \mathbb{Z}$.

That is to say $3x-1=4k$.
So this is the same as $3x=1 \bmod 4$.

When there is a common factor in $a=b \bmod n$, divide a,b, and n by this factor.

---------------------------
In a general case, how to find an inverse ?

- observe : for example, what number is divisible by 3 and such that it is 1 added to a multiple of 4 ? Answer is 9. It's easy by trial and error when it's small number.

- use the euclidian algorithm... I can give you links where I've done such things, or you can read that : Extended Euclidean algorithm - Wikipedia, the free encyclopedia

:)