$\phi(n)$ and $p(n)$ 2

Let $p_1,p_2,p_3,...$ be a listing, in order, of the primes. We have the following result:

If $N \ge 5$ , then $p_1p_2\,\cdots\,p_N > p_{N+1}^3$ .

This is readily proved by induction. If $N=5$ then $2.3.5.7.11 = 2310 > 2197 =13^3$ . If $N \ge 5$ and $p_1p_2\cdots p_N > p_{N+1}^3$ , then $p_1p_2 \cdots p_N p_{N+1} \,>\, p_{N+1}^4 \,>\, 8p_{N+1}^3 = (2p_{N+1})^3 > p_{N+2}^3$ by Bertrand's Postulate.

The condition $p(M) = \varphi(M) - 2$ states that there is exactly one integer between $2$ and $M-1$ (inclusive) which is coprime to $M$ and yet not prime. Thus any integer $M$ which is not divisible by a prime $q$ and which is greater than $q^3$ cannot satisfy this condition, since then $q^2$ and $q^3$ would be two such integers.

Thus, if $M$ is a positive integer such that $p(M) = \varphi(M) - 2$ , and if $q$ is a prime which does not divide $M$ , then $M \le q^3$ .

Suppose now that $M$ is a positive integer such that $p(M) = \varphi(M) - 2$ , and suppose that $N$ is the smallest integer such that $p_N$ does not divide $M$ . Then $M \le p_N^3$ . Since $p_1p_2 \cdots p_{N-1} \le M \le p_N^3$ , we deduce that $N-1 \le 4$ , so that $N \le 5$ . Thus $M \le 11^3 = 1331$ .

It is easy enough to run a computer check of the numbers between $1$ and $1331$ to find the integers $M$ such that $p(M) = \varphi(M) - 2$ . They are $5, 10, 14, 20, 42, 60$ . Thus there are $\boxed{6}$ such integers.

$p(n) = \phi (n) - 2$ iff all but one totients of $n$ are 1 or prime.

Hence, if $p_1, p_2$ are the smallest primes which are not factors of $n$ , $p_1^2 < n < p_1^3$ and $n < p_1 p_2$ .

(Letting $q?$ be the product of all primes less than or equal to $q$ )

$(p_1-1)?$ must be a factor of $n$ , so $(p_1-1)? < p_1 p_2$ , and $p_1 < 11$ .

---

Cases:

$\begin{matrix} p_1 & p_2 & solutions & \\ 2 & 3 & 5\\ &5\\ 3&5&14\\ &7&10&20\\ 5&7\\ &11&42\\ 7&11&60 \end{matrix}$