Properties of Z_{n}

Printable View

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

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

Originally Posted by Jose27
An element $a \in \mathbb{Z}_n$ has multiplicative inverse iff $(a,n)=1$ which happens iff $= \mathbb{Z}_n$, which means not only $-1$ and $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 $\mathbb{Z}$ with $\mathbb{Z}_n$, I think.

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

You would have to prove: $a$ has inverse iff $(a,n)=1$ and then $= \mathbb{Z}_n$ iff $(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 $a$ has an inverse iff $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 $(a,n)=1$ then you can find integers $x,y$ such that $xa + yn = 1$; clearly $x$ is the multiplicative inverse of $a$ (mod n).

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

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