Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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, –  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
2  
What you say is false: take $n=8$ and see that $m=2$ and $\phi(8)=4$. –  user26857 Dec 16 '12 at 8:19
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? –  Hans Giebenrath Dec 16 '12 at 8:19

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.