# Suppose that $n$ is a positive integer with $\phi(n)=8$. Show that if $p$ is an odd prime divisor of $n$ then $p=3$ or $p=5$

I'm working on some exam practice questions. I feel like I am close here, but just need a hint in the right direction. Many thanks in advance!

Suppose $a$ is co-prime to $n$. Then by FLT,

$$a^8 \equiv 1 \pmod n$$

So if $p|n$ then, $$a^{p-1} \equiv a^8 \equiv 1 \pmod p$$

Therefore $ord_p(a)|p-1$ and $ord_p(a)|8$. But then now I am a bit stuck. I can't seem to be able to manipulate an expression to show that either $p=3$ or $p=5$.

Any help would be greatly appreciated!

• Note that if $p \mid n$, then $\phi(p) \mid \phi(n)$. In particular, $\phi(p) \leqslant \phi(n)$. That reduces the possibilities a bit. – Daniel Fischer Nov 12 '13 at 11:49
• ahh yes. Many thanks! – JackReacher Nov 12 '13 at 11:51

You don't need FLT. Just use the formula $\phi(n)=\prod_{p\mid n} p^{v_p(n)-1}(p-1)$. Now $\phi(n)=8$ implies that $p-1\in \{1,2,4,8\}$ and so $p\in \{2,3,5,9\}$. But $9$ is not prime.
• Using this, you should be able to find all $n$ such that $\phi(n)=8$. – lhf Nov 12 '13 at 12:00