For a positive $m$, let $\phi(m)$ denotes the number of integers $k$ such that $1\leq k\leq m$ and $GCD(k,m)=1.$ Then which are necessarily true?

(1) $\phi(n)$ divides $n$ for all $n>0$

(2) $n$ divides $\phi(a^n-1)$ for all positive integer $a,n$

(3) $n$ divides $\phi(a^n-1)$ for all positive integer $a $ and $n$ such that $GCD(a,n)=1$

(4) $a$ divides $\phi(a^n-1)$ for all positive integer $a$ and $n$ such that $GCD(a,n)=1.$

I took $n=7$, then $\phi(7)=6$ and $6$ does not divide 7, hence option 1 is false. Next i took $a=3$ and $n=5$, then i get $a^n-1=242$ and $\phi(242)=110$ but $3$ does not divide $110$. Also the option (2) and (3) are true. I not able to prove this. Please help me!


We must assume $a\ge2$. Clearly (2) implies (3). To prove (2), note that $a^n\equiv1\pmod{a^n-1}$, but $a^j\not\equiv1\pmod{a^n-1}$ for all $1\le j<n$ because $a^j-1$ is too small to be a multiple of $a^n-1$. Therefore the order of $a$ modulo $a^n-1$ is exactly $n$. By Euler's theorem (valid because $a$ and $a^n-1$ are always relatively prime), we know that $a^{\phi(a^n-1)}\equiv1\pmod{a^n-1}$, and therefore $\phi(a^n-1)$ must be a multiple of the order $n$.

  • $\begingroup$ Fantastic explanation! Thank you so much! $\endgroup$ – Beginner Jan 3 '17 at 3:57

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.