I came across Lehmer's problem in Wikipedia:
https://en.wikipedia.org/wiki/Lehmer%27s_totient_problem
and do not grasp why it may be of any interest. Are there any serious consequences or insights if it is really confirmed ? I suppose people who struggle(d) for the overwhelming results cited in Wikipedia did not spend their valuable time when there is no deeper consequence/implication.
So I suppose a solution to this problem cited from Wikipedia : "The top line in the graph, $y = n − 1$, is a true upper bound. It is attained whenever n is prime."
Did Lehmer want to prove that the line is only attained by primes ?
But this seems not so difficult and probably is known already !?
Lehmer is famous for finding large prime numbers. He did that using theorems about primes, rather than trial division. (Rather than testing $n/3,n/5,n/7$ and so on.)
For example, Fermat's Little Theorem $$a^{p-1} \equiv 1 \bmod p \text{ for } a \text{ coprime to }p$$ generalizes to Euler's Theorem $$a^{\varphi(n)} \equiv 1 \bmod n \text{ for } a \text{ coprime to }n.$$ If $\varphi(n)$ is a factor of $n-1$, then it follows that $a^{n-1} \equiv 1 \bmod n.$ Lehmer calculated huge powers $a^k\bmod p$, with tests that only prime numbers passed. This totient problem is related, and if no non-primes have $\varphi(n)|n-1$, then different primality tests may be possible.