A question on Euler Phi Function

73 Views Asked by At

Let $p$ be a fixed odd prime. If $n$ is an integer such that $p | \phi(n)$, how much could be said about $n$? Can you think of any relations between $p$ and $n$? Any input would be appreciated!

2

There are 2 best solutions below

1
On

The formula for Euler's function gives most of the answers: $$n=p^aq^br^c...$$ $$\phi(n)=p^{a-1}(p-1)q^{b-1}(q-1)r^{c-1}(r-1)=n(1-\frac1 p)(1-\frac1 q)(1-\frac1 r)$$

If p|$\phi(n)$ then we must have:

(a) p must be one of the prime factors of n, and

(b) The index "a" of p in $n=p^aq^br^c...$, must be greater than 1.

1
On

3 is obviously NOT a factor of 14 but if you look at the formula for $\phi(14)$ the index of each prime factor, 2 and 7, is only 1. So, condition (b) does not apply.