# Thread: stuck on congruence proof

1. ## 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 $\displaystyle a,m \epsilon Z$ such that $\displaystyle gcd(a,m)=1$, with $\displaystyle m>1$ there is a $\displaystyle b \epsilon Z$ such that $\displaystyle ab \equiv 1 (\bmod m)$. Show therefore, that we can "divide" by a by multiplying the congruence by the corresponding b:

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

2. Hello,

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 $\displaystyle a,m \epsilon Z$ such that $\displaystyle gcd(a,m)=1$, with $\displaystyle m>1$ there is a $\displaystyle b \epsilon Z$ such that $\displaystyle 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 $\displaystyle d=gcd(x,y)$. There exist $\displaystyle u~,~v~\in \mathbb{Z}$ such that :

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

Bézout's theorem/lemma :
$\displaystyle 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 :

$\displaystyle 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) :

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

$\displaystyle \boxed{u=b}$

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

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

Multiplying by b each side :

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

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

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

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

You can do the reverse implication exactly the same way.

Whew!

3. 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!

4. You're welcome You know, I'm happy that you understand !

Another point I forgot to mention...
b is called the "inverse" of a modulo m, in $\displaystyle (\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 :
$\displaystyle 46 \equiv 6 (\bmod 10)$, 6 has no inverse... because it's not coprime with 10.

To simplify the thing, you can do it :

$\displaystyle 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 !!

$\displaystyle 23 \equiv 3 (\bmod 5)$

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

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

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

$\displaystyle 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

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