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, 06:11 PMChrisBickleshowing 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 PMoldguynewstudent
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. - Nov 10th 2009, 08:59 PMChrisBickle
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 PMDrexel28
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.