Say $\phi(n)=k$ is the number of integers less than n relatively prime to n. Then prove that any integer a relatively prime to n $a^{\phi(n)}=1 \quad mod\quad n$.

My proof

U(n) be the group of integers coprime to n less than n. Then a belongs to this group and order of group is k. Hence $a^k=1$.

This proof is correct right.


If a (finite) group has order $k$ then of course every element $x$ of the group satisfies $x^k=1$; this is pure group theory.

However to apply this theorem one has to first show that U(n) is a group in the first place. SO one has to do some number-theoretic proof, there is no way to avoid it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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