Why is it impossible for phi(n) = 14?

Question

My notes state that if phi (n) were to exist then since 7 divides phi(n), 49 must divide phi(n). I understand why 49 can't divide phi(n) but i don't get how the implication from 7 divides phi(n) to 49 divides phi(n) was reached.

Furthermore, my notes say since 7 divides phi(n) then 7 must divide p-1. Why does this statement hold true?

Answer 1

First of all, if $\gcd(a,b) = 1$, then $\phi(ab) = \phi(a)\phi(b)$.

So if we factor some number $n$ into prime powers, it clearly suffices to determine $\phi(p_i^k)$ for each prime $p_i|n$, to completely determine $\phi(n)$.

So, let's look at $\phi(p^k)$, for some prime $p$. It's pretty clear that if $\gcd(a,p^k) \neq 1$, that $a$ must have a (positive) power of $p$ in its factorization.

This happens if and only if $a = pt$, for some integer $t$. And how many such multiples of $p$ are there that are less than $p^k$? Clearly, we have $p^{k-1} - 1$. Therefore, all the rest of the $p^k - 1$ positive integers less than $p^k$ are co-prime to $p^k$, giving us:

$\phi(p^k) = p^k - 1 - (p^{k-1} - 1) = p^k - p^{k-1} = (p-1)p^{k-1}$.

So let us now consider the special question: can $\phi(n) = 7$?

Suppose $n = 7^km$, where $\gcd(7,m) = 1$.

Then $\phi(n) = \phi(7^k)\phi(m) = 6\cdot 7^{k-1}\phi(m)$.

If this equals $7$, we must have $6\phi(m) = 1$ and $k = 2$. But this is clearly impossible, since $\phi(m)$ is a positive integer, so that $6\phi(m) > 1$.

So, what about $\phi(n) = 14$?

If $7|\phi(n)$, then as we saw above $49|n$ (since $k \geq 2$). Thus $6|\phi(n)$, but $6\not\mid 14$.

So we conclude $7\not\mid n$. But then no powers of $7$ appear in the factorization of $\phi(n)$, since there is no prime $p$ for which $p-1 = 7$ ($8$ is not prime). Since $7|14$, no such $n$ can exist.

Answer 2

My take on the problem is not so different from David’s, making use of the multiplicativity of $\phi$ when two numbers are relatively prime. But I’d look at the divisibility of $n$ and $\phi(n)$ by $2$. Let me use the standard notation that $v_2(a)$ is the exponent to which $2$ appears in the expression of $a$ as a product of prime powers.

For odd primes $p$, we have $v_2(\phi(p))\ge1$, so that if $n$ is divisible by $m$ primes, we have $v(\phi(n))\ge m$. Our mystery number $n$ has $v_2(\phi(n))=v_2(14)=1$, so that $n$ is divisible by at most one odd prime. Furthermore, $v(4)=1$, so that $n$ can not be divisible by $4$ and an odd prime either. Thus either $n$ is prime or $n=2p$ for $p$ an odd prime. But for such $p$, $\phi(2p)=v(p)$, and as we know, $14$ is not of form $p-1=\phi(p)$, and so can not be the totient of any number at all.