3
$\begingroup$

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) $ ?

  • 3
    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,2012-12-16
  • 0
    Should the equation $k^m\equiv 1 \bmod n$ hold for all $k$? For one $k$? It is again not clear what is meant.2012-12-16
  • 0
    It should hold for all $k$.2012-12-16
  • 2
    What you say is false: take $n=8$ and see that $m=2$ and $\phi(8)=4$.2012-12-16
  • 1
    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?2012-12-16
  • 0
    It talks about all $n$, and uses this statement to prove Euler's theorem.2012-12-16
  • 0
    Thanks to all the answers and comments here, I finally understood what the book was talking about. Thank you all.2012-12-16

2 Answers 2