# Properties of Z_{n}

• Oct 1st 2009, 04:21 PM
platinumpimp68plus1
Properties of Z_{n}
I want to show that the elements of $\displaystyle \mathbb{Z}_n$ under multiplication that have inverses are also the generators of $\displaystyle \mathbb{Z}_n$ under addition.

My answer so far: The only integers with multiplicative inverses are -1 and 1; and these are generators of ($\displaystyle \mathbb{Z}_n, +_{n}$).

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 $\displaystyle \phi(x)$=(1)x, $\displaystyle \phi(x)$=(-1)x, generates $\displaystyle \mathbb{Z}_n$? Or am I interpreting this question completely wrong?
• Oct 1st 2009, 04:45 PM
Jose27
An element $\displaystyle a \in \mathbb{Z}_n$ has multiplicative inverse iff $\displaystyle (a,n)=1$ which happens iff $\displaystyle <a>= \mathbb{Z}_n$, which means not only $\displaystyle -1$ and $\displaystyle 1$ have multiplicative inverses.
• Oct 1st 2009, 05:00 PM
platinumpimp68plus1
Quote:

Originally Posted by Jose27
An element $\displaystyle a \in \mathbb{Z}_n$ has multiplicative inverse iff $\displaystyle (a,n)=1$ which happens iff $\displaystyle <a>= \mathbb{Z}_n$, which means not only $\displaystyle -1$ and $\displaystyle 1$ have multiplicative inverses.

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 $\displaystyle \mathbb{Z}$ with $\displaystyle \mathbb{Z}_n$, I think.

So does the fact that $\displaystyle (a,n)=1$ iff a generates $\displaystyle \mathbb{Z}_n$ sufficiently answer this question? Or do you think there is more I need to show?
• Oct 1st 2009, 05:05 PM
Jose27
Quote:

Originally Posted by platinumpimp68plus1

So does the fact that $\displaystyle (a,n)=1$ iff a generates $\displaystyle \mathbb{Z}_n$ sufficiently answer this question? Or do you think there is more I need to show?

You would have to prove: $\displaystyle a$ has inverse iff $\displaystyle (a,n)=1$ and then $\displaystyle <a>= \mathbb{Z}_n$ iff $\displaystyle (a,n)=1$ (notice there are two iff's to be proven) but yes, this would finish it, since by transitivity you would be saying that $\displaystyle a$ has an inverse iff $\displaystyle a$ generates the whole additive group.
• Oct 1st 2009, 06:14 PM
platinumpimp68plus1
I think I have the first statement proven, but I'm unsure about how to prove the second... any tips on where to start?
• Oct 1st 2009, 06:47 PM
Bruno J.
If $\displaystyle (a,n)=1$ then you can find integers $\displaystyle x,y$ such that $\displaystyle xa + yn = 1$; clearly $\displaystyle x$ is the multiplicative inverse of $\displaystyle a$ (mod n).

To show that $\displaystyle a$ generates $\displaystyle \mathbb{Z}_n$ as an additive group, consider the elements $\displaystyle a,2a,3a,...,na$. I claim that they are all distinct; because if $\displaystyle ja\equiv ka \mod n$, then $\displaystyle a(j-k)\equiv 0 \mod n$. Since $\displaystyle a$ is invertible we can multiply by its inverse on both sides which yields $\displaystyle j \equiv k \mod n$. Hence $\displaystyle \{a,2a,...,na\}=\mathbb{Z}_n$.

(Cool)
• Oct 2nd 2009, 06:08 AM
platinumpimp68plus1
Thank you!!! (Clapping)