Properties of Z_{n}

Printable View

October 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?
October 1st 2009, 04:45 PM
Jose27

An element $a \in \mathbb{Z}_n$ has multiplicative inverse iff $(a,n)=1$ which happens iff $<a>= \mathbb{Z}_n$ , which means not only $-1$ and $1$ have multiplicative inverses.
October 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 $<a>= \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?
October 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 $<a>= \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.
October 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?
October 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)
October 2nd 2009, 06:08 AM
platinumpimp68plus1

Thank you!!! (Clapping)