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 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 ?
Problem: Prove that for some .
Lemma: For the linear Diophantine equation is only solvable if
Proof: Suppose that but such that . Then clearly and so which is a contradiction.
This proves the leftward facing arrow. I'm tired, so I'l leave the other half to you.