# problem about Euler function $\phi$.

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