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