# stuck on congruence proof

• June 22nd 2008, 11:33 AM
SaxyTimmy
stuck on congruence proof
Hey guys (and gals),

I was wondering if you could help me out. I am stuck on this proof I know a bunch of the basic steps but can't put them together properly. If I could get your help it would be great the question is:

Prove that for every $a,m \epsilon Z$ such that $gcd(a,m)=1$, with $m>1$ there is a $b \epsilon Z$ such that $ab \equiv 1 (\bmod m)$. Show therefore, that we can "divide" by a by multiplying the congruence by the corresponding b:

$ax \equiv c (\bmod m) \Leftrightarrow x \equiv bc (\bmod m)$
• June 22nd 2008, 11:46 AM
Moo
Hello,

Quote:

Originally Posted by SaxyTimmy
Hey guys (and gals),

I was wondering if you could help me out. I am stuck on this proof I know a bunch of the basic steps but can't put them together properly. If I could get your help it would be great the question is:

Prove that for every $a,m \epsilon Z$ such that $gcd(a,m)=1$, with $m>1$ there is a $b \epsilon Z$ such that $ab \equiv 1 (\bmod m)$.

This has to do with Bézout's theorem (I don't know if you are allowed to use it).

Bézout's identity :
Let $d=gcd(x,y)$. There exist $u~,~v~\in \mathbb{Z}$ such that :

$u \cdot x+v \cdot y=d$.

Bézout's theorem/lemma :
$gcd(x,y)=1 \Longleftrightarrow \exists u~,~v~\in \mathbb{Z} \text{ such that } u \cdot x+v \cdot y=1$.

--------------------------
Going back to the problem :

$gcd(a,m)=1 \implies \exists u~,~v~\in \mathbb{Z} \text{ such that } u \cdot a+v \cdot m=1 \quad (1)$

Rewriting (1) :

$au=1-{\color{red}m}v \equiv 1 (\bmod {\color{red}m})$

$\boxed{u=b}$

Quote:

Show therefore, that we can "divide" by a by multiplying the congruence by the corresponding b:

$ax \equiv c (\bmod m) \Leftrightarrow x \equiv bc (\bmod m)$
$ax \equiv c (\bmod m)$

Multiplying by b each side :

$abx \equiv {\color{blue}bc} (\bmod m)$

But we know that $ab \equiv 1 (\bmod m)$

Therefore $abx \equiv {\color{blue}x} (\bmod m)$

--> $x \equiv bc (\bmod m)$

You can do the reverse implication exactly the same way.

Whew!
• June 22nd 2008, 12:35 PM
SaxyTimmy
Thanks Moo, you are my hero. You make the things that I get stuck on look so trivial. I was almost there, but missed the one thing that made it all come together into a cohesive proof. You are my HERO! :)
• June 22nd 2008, 02:35 PM
Moo
You're welcome (Wink) You know, I'm happy that you understand !

Another point I forgot to mention...
b is called the "inverse" of a modulo m, in $(\mathbb{Z}/m \mathbb{Z},+)$.

This means that [maht]ab \equiv 1 (\bmod m)[/tex].

So basically, you can "divide" the stuff by b because it has an inverse. Whereas if you had, for example :
$46 \equiv 6 (\bmod 10)$, 6 has no inverse... because it's not coprime with 10.

To simplify the thing, you can do it :

$2 \cdot 23 \equiv 2 \cdot 3 (\bmod 2 \cdot 5)$

There you can divide by 2, but don't forget to divide the modulo too !!

$23 \equiv 3 (\bmod 5)$

Justification :
$46 \equiv 6 (\bmod 10) \longleftrightarrow 46=6+10k$
--> $23=3+5k \longleftrightarrow 23 \equiv 3 (\bmod 5)$

If you had $46 \equiv 6 (\bmod 5)$, you can see that 2 and 5 are coprime. Therefore, there exists b such that $2b \equiv 1(\bmod 5)$

Multiplying by b :
--> $23 \cdot (2 \cdot b) \equiv 3 \cdot 2 \cdot b (\bmod 5)$

$23 \equiv 3 (\bmod 5)$

So you can see that if you want to divide by a number :
- if it is coprime with the modulus, it doesn't affect it
- if it isn't coprime with the modulus, it affects it

This was just some extra (Thinking)
• June 22nd 2008, 08:22 PM
SaxyTimmy
hmmm... thats pretty interesting. Our prof was like this is true just believe me... but seeing the justification behind it is always nice. thanks for the info Moo.

The definition of the congruence you used is also nice (the 23=3+5k or something like that) also nice to see things like that. The definition we were taught is slightly different, but seeing it that way makes things look much better for certain instances.

Anyways, I would have "thanked" you for that useful post moo but it won't let me :(. So, thanks a ton for all your help again.

Edit: Now for some reason it will let me thank you :D