# Why is the order of an element in the group of units mod n , $U(n)$, equal to the totient of n?

I came across this statement in an abstract algebra textbook, I am looking for a proof.

EDIT: I guess I was not clear, what I meant was

If $k\ \epsilon\ U(n)$ and $m\ \epsilon\ \mathbb{Z}^+$ and

$k^m \equiv 1\ mod\ n$ ,

why is the smallest value of $m$ that satisfies the congruence for all $k$ equal to $\varphi(n)$ ?

-
Dear Vivek, The answer below explains why the order of the group $U(n)$ itself is equal to $\varphi(n)$. Do you know why the order of an element in a group divides the order of the group? (Note by the way that in general it doesn't equal that order, just divides it, so the statement in the title of your question is not literally true.) Regards, –  Matt E Dec 16 '12 at 7:19
Should the equation $k^m\equiv 1 \bmod n$ hold for all $k$? For one $k$? It is again not clear what is meant. –  Hans Giebenrath Dec 16 '12 at 8:01
It should hold for all $k$. –  Vivek Dec 16 '12 at 8:11
What you say is false: take $n=8$ and see that $m=2$ and $\phi(8)=4$. –  user26857 Dec 16 '12 at 8:19
Your $m$ is then the exponent of the group $U(n)$. I don't think it is always equal to $\varphi(n)$ (totient of $n$). Are you sure the book is talking about every $n$? Or just $n$ prime? Or some other assumption? –  Hans Giebenrath Dec 16 '12 at 8:19

Your statement is false. For example, $U(35)$ has $\varphi(35) = 24$ elements. However, the smallest choice of $m$ is 12.

Proof: For every $x$ relatively prime to both 5 and 7,

$$x^{12} = (x^3)^4 \equiv 1 \mod 5$$ $$x^{12} = (x^2)^6 \equiv 1 \mod 7$$

and therefore, by the Chinese remainder theorem,

$$x^{12} \equiv 1 \mod 35$$

for every $x$ relatively prime to 35. Of course, this implies

$$x^{\varphi(35)} = x^{24} = (x^2)^{12} = 1 \mod 35$$

as it should.

-

You are thinking of the Carmichael function $\lambda$. You are right that $\lambda(n)\mid \varphi(n)$, but $\lambda(n)= \varphi(n)$ is not necessarily true. The smallest counterexample is $n=8$.

-