stuck on congruence proof

**SaxyTimmy** · June 22nd 2008, 11:33 AM

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

**Moo** · June 22nd 2008, 11:46 AM

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

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!

**SaxyTimmy** · June 22nd 2008, 12:35 PM

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!

**Moo** · June 22nd 2008, 02:35 PM

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

**SaxyTimmy** · June 22nd 2008, 08:22 PM

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

Thread: stuck on congruence proof

LinkBack

Thread Tools

Display

stuck on congruence proof

Similar Math Help Forum Discussions

A Congruence Proof

Congruence Proof

Congruence Proof

Congruence proof

Proof congruence

Search Tags