# Thread: showing the identity in multiplication mod n only exists with gcd =1

1. ## showing the identity in multiplication mod n only exists with gcd =1

Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing

2. Originally Posted by ChrisBickle
Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing
What you've written doesn't really make sense. However I will try to help.

I suppose you are saying a,b $\epsilon$ Z. Then if a*b = 1, a and b would both have to be 1 or -1 since no other intergers multiplied together = 1.

If a is 1 or -1 then gcd(a,n) is obviously 1.

converse: Assume gcd(a,n) not = 1, then a cannot be 1 or -1.

Therefore b cannot be an integer such that a * b = 1. Proof by contrapositive.

If this is not what you are saying, please restate.

3. ya it didnt make much sense the way i wrote it i figured it out today, if you assume b exists then ab is congruent to 1modn and use definitions to get to ab - nh = 1 then the gcd is 1 and turn it around to go the other way. Thanks for trying sorry i wrote it so confusing.

4. Originally Posted by ChrisBickle
Ok so we defined multiplication mod n and the question is, Let a element of Zn there exists b element Zn such that a * b = 1 iff gcd(a,n) = 1. I know i gotta go both ways but im not sure where to start to attack this thing
I assume you meant there $ab\equiv1\text{ mod }n$?

Problem: Prove that $(a,n)=1\Leftrightarrow ab\equiv1\text{ mod }n$ for some $b\in\mathbb{Z}_n$.

Lemma: For $a,b\in\mathbb{Z}$ the linear Diophantine equation $ax+by=1$ is only solvable if $(a,b)=1$

Proof: Suppose that $(a,b)=c>1$ but $\exists x,y\in\mathbb{Z}$ such that $ax+by=1$. Then clearly $c|ax$ and $c|by$ so $c|ax+by=1$ which is a contradiction. $\blacksquare$

This proves the leftward facing arrow. I'm tired, so I'l leave the other half to you.