How do I show that $n$ is prime if and only if $\phi(n) = n − 1$?

Question

I am trying to construct a proof that shows both the 'forward' and 'backward' directions for the statement

$n$ is prime if and only if $\phi(n) = n − 1$,

however I cannot figure out what specific proof type to use for both directions.

Thanks.

Answer 1

For the forward direction, you need to show that if $n$ is prime then $\phi(n)=n-1$, i.e. the only number in $\{1,\ldots,n\}$ which has a nontrivial common factor with $n$ is $n$ itself.

For the backward direction, you need to check that whenever $n$ is not prime, either there are at least two numbers in $\{1,\ldots,n\}$ which have a nontrivial common factor with $n$, or there are none. (These correspond to the two cases $n$ composite and $n=1$.)

Answer 2

If $n$ is prime then any number less than $n$ is coprime to $n$. There are $n-1$ such numbers.

Conversely if $\phi(n)=n-1$, then all of the numbers less than $n$ are coprime to $n$, which means $n$ is prime.

Answer 3

I'm assuming that by $\phi(n)$, with $n$ a positive integer, you mean Euler's totient function, which counts how many integers from 1 to $n$ are coprime to $n$. Algebraically: $$\phi(n) = \sum_{i = i}^n \delta_1^{\gcd(i, n)},$$ where $\delta_b^a$ is the Kronecker delta function.

Except for $n = 1$, no positive integer $n$ is coprime to itself. So if you don't know whether $n$ is prime or not, you can provisionally write down $¿ \phi(n) = n - 1 ?$. Then check if $n$ is divisible by 2. If it is, then that means $n$ is not coprime to even integers and we now have $$¿ \phi(n) = \frac{n}{2} ?$$ If $n$ is a positive composite even number, then clearly $$\phi(n) \leq \frac{n}{2} < (n - 1).$$

If instead $n$ is a positive composite odd number, it must be divisible by some positive odd prime $p < n$. Then $$\phi(n) \leq \left(n - \frac{n}{p}\right) < (n - 1).$$

Well, I think you get the idea.

---

Here's a little tidbit you might find interesting: $\phi(6) < \sqrt 6$. Generally $\phi(n) > \sqrt n$.