Show that no integer $n$ can have exactly 26 primitive roots.
I know that if $n$ has primitive roots then it has exactly $\phi(\phi(n))$ primitive roots. I think the proof has to use contradiction. Suppose $n$ is an integer and has exactly 26 primitive roots then $\phi(\phi(n))=26$. How do I carry on and show that $\phi(\phi(n))$ is not 26. Please explain me.
On
$\phi(m)=26$ is impossible.
We have for prime $p$, $\phi(p^a)=p^a-p^{a-1}=(p-1)\cdot p^{a-1}$. Also $\phi$ is multiplicative (that is, for $\gcd(j,k)=1$, $\phi(jk)=\phi(j)\phi(k)$).
From these two facts, we have that $\phi(j)$ is even except for $\phi(1)=\phi(2)=1$.
Thus to have any hope of $\phi(m)=26$, we'd need $m=p^a$ for some prime $p$ and positive integer $a$. Then $p-1$ would have to be a factor of $26$: namely $1, 2, 13$, or $26$. Then $p$ would have to be $2$ or $3$ (the other two possibilities don't yield prime values for $p$. But you can easily check that neither $\phi(2^a)$ nor $\phi(3^a)$ ever gives $26$.
On
Because 26 is what is called a "nontotient." With only two exceptions, $\phi(n)$ is never odd. There are also some even values that never occur as $\phi(n)$, and 26 is one of them.
Remember that $\phi(p) = p - 1$ if $p$ is prime. But $27 = 3^3$, so 26 is not a totient this way. How about $\phi(p^\alpha) = (p - 1)p^{\alpha - 1}$? Or some combination of primes and powers of primes? Since $26 = 2 \times 13$, we're looking for $n$ a multiple of 3 or 4. But what to make of the 13? If you're still not convinced, you can try testing $\phi(n)$ for $26 < n < 162$ by brute force, e.g., Select[Range[27, 161], EulerPhi[#] == 26 &].
So, if $\phi(n) = 26$ has no solution, then $\phi(\phi(n)) = 26$ is absolutely hopeless.
If $n=\smash{\displaystyle\prod_{i=1}^r p_i^{e_i}}$, then $$\varphi(n)=\smash{\prod_{i=1}^r p_i^{e_i-1}}(p_i-1).$$. The only factors of $n$ that might end up in $\varphi(n)$ divisible by $13$ are $13^e$ for some $e\ge 1$. However $13^e$ can't be a factor, as it would give a contribution of $13^{e-1}\cdot 12$.