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

• Nov 9th 2009, 06:11 PM
ChrisBickle
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
• Nov 9th 2009, 07:59 PM
oldguynewstudent
Quote:

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 $\displaystyle \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.
• Nov 10th 2009, 08:59 PM
ChrisBickle
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.
• Nov 10th 2009, 09:53 PM
Drexel28
Quote:

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 $\displaystyle ab\equiv1\text{ mod }n$?

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

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

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

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