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

  • 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

3

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.

1

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$.