$ϕ(n)$ and $p(n)$

It's easy to check that there are $\fbox{10}$ integers $\le 30$ that satisfy the condition: $1,2,3,4,6,8,12,18,24,30.$ We'll show that these are the only ones.

For $n > 1,$ the condition is equivalent to the statement that if $m < n$ is relatively prime to $n,$ then $m$ is prime or $m=1.$ Suppose $n > 30$ satisfies the condition. Clearly $2|n,$ as otherwise $m=4$ violates the condition. Similarly, $3|n$ and $5|n.$ So $30|n.$ Now let $p$ be the smallest prime not dividing $n.$

If $p=7,$ then $m=49$ violates the condition, because $n \ge 60.$

If $p=11,$ then $m=121$ violates the condition, because $n \ge 2\cdot 3 \cdot 5 \cdot 7 = 210.$

For larger values of $p,$ to show that $m=p^2$ violates the condition, we need to show that $p^2 \le n,$ and it is enough to show that $2 \cdot 3 \cdot 5 \cdots q \ge p^2$ where $q$ is the largest prime less than $p.$ But we can use Bertrand's postulate : the left side is greater than $30 (q/2) q,$ and the right side is less than $(2q)^2,$ so the left side is greater than $15q^2$ and the right side is less than $4q^2,$ and the result follows.

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

Hence, if $p$ is the smallest prime which isn't a factor of $n$ , $n < p^2$ .

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

$(p-1)?$ must be a factor of $n$ , so $(p-1)? < p^2$ , and $p < 11$ .

---

Cases:

$p = 2$ : $1, 3$ ,

$p = 3$ : $2, 4, 8$ ,

$p = 5$ : $6, 12, 18, 24$ ,

$p = 7$ : $30$ .

Euler's totient function $\phi(n)$ represents the number of numbers less than $n$ relatively prime (do not share a factor in common with) to $n$ .

Think of $p(n)$ as the number of primes less than $n$ that are relatively prime to $n$ .

Define a new function $q(n)$ which represents the number of composites less than $n$ that are relatively prime to $n$ .

We can now create the equivalence relation $p(n) + q(n) + 1 = \phi(n)$ or $p(n) + q(n) = \phi(n) - 1$ (since $\phi(n)$ includes one in its counting, we must add one in our equivalence relation). Since we are trying to find values of $n$ such that $p(n) = \phi(n) - 1$ , we conclude that $q(n) = 0$ . This means that all composite numbers less than $n$ must share a factor with $n$ .

This leads to several conclusions:

• (1) $n$ must be non-prime except for $n \leq 3$ . This is because $q(1)$ , $q(2)$ , and $q(3)$ are all equal to zero and $q(p) > 0$ for a prime $p$ greater than 4.

• (2) If $n = p_1^{k_1}p_2^{k_2}...p_N^{k_N}$ where $p$ is a prime, then $n < q^2$ where $q$ is a prime not equal to $p_1$ , $p_2$ , ..., $p_N$ and $q < n$ . This is because if $n$ was greater than or equal to $q^2$ then $q$ would have to be a factor of $n$ if $q(n)$ is to equal zero.

• (3) All $n \geq 4$ must be even. All $n \geq 9$ must be multiples of 3. All $n \geq 25$ must be multiples of 5. In generall, all $n \geq p^2$ must be multiples of $p$ . This conclusion is easy to verify because we already verified it in proving (2) - "if $n$ was greater than or equal to $q^2$ then $q$ would have to be a factor of $n$ if $q(n)$ is to equal zero".

Using these conclusions, we can figure out that 30 is the last number which satisfies $q(n) = 0$ since the next number after 30 which satisfies (3) is 60 which is greater than 49, violating (2). If we were to include 7 (yielding the number 210), we would also have to include 11 (since 210 > 121). You would then start having to include more and more primes, making it impossible to include any more primes after 5.

Searching through the numbers between 1 and 30 which satisfy $q(n) = 0$ yields $\boxed{10}$ numbers: 1, 2, 3, 4, 6, 8, 12, 18, 24, and 30.