An element has multiplicative inverse iff which happens iff , which means not only and have multiplicative inverses.
I want to show that the elements of under multiplication that have inverses are also the generators of under addition.
My answer so far: The only integers with multiplicative inverses are -1 and 1; and these are generators of ( ).
I feel like this answer is too simple though... Can I show this more rigorously? Besides saying that (obviously) the gcd(1,n)=1, and =(1)x, =(-1)x, generates ? Or am I interpreting this question completely wrong?
OOOOOOOOOH. Doh. Thank you. Bear with my stupidity, I'm in an abstract algebra course and did not take the recommended prereq so I'm a little lost at the moment. I was confusing the infinite with , I think.
So does the fact that iff a generates sufficiently answer this question? Or do you think there is more I need to show?
If then you can find integers such that ; clearly is the multiplicative inverse of (mod n).
To show that generates as an additive group, consider the elements . I claim that they are all distinct; because if , then . Since is invertible we can multiply by its inverse on both sides which yields . Hence .