On Lehmer's Totient Conjecture 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 !?
 A: 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.
A: D. H. Lehmer made this conjecture in 1932, a couple of years after he had published his Ph.D. thesis, "On an Extended Theory of Lucas' Functions," in which he extended the theory of the Lucas (and companion Lucas) sequences to a larger family of sequences which now bear his name. In addition, he corrected some of the mistakes in the theory developed by E. Lucas.
In Lehmer's extended theory of the Lucas sequences, we find a theorem that asserts if an integer $n$ has maximal rank of apparition in the underlying (Lehmer) sequence, then $n$ must be prime. The rank of apparition of $n$, $\omega(n)$, is the value of the index that contains $n$ as a divisor; $\omega(n)$ is maximal if it is either $n-1$ or $n+1$.
Of course, in the case of primes $p$, Euler's totient $\phi(p) = p - 1$; and moreover, $p$ always divides the $(p-1)st$ term of the underlying sequence. Hence, $\phi(p) | p - 1$.
Therefore, it is only natural to ask---what happens if $n$ turns out to be composite?
Well, given a particular Lehmer sequence, $\lbrace U_{k} \rbrace$, if $n | U_{n-1}$, then $n$ is acting like a prime; and so, we call it a pseudoprime (of sorts) because generally speaking, $n$ does not usually divide the $(n-1)st$ term of the underlying sequence. 
Note: If such pseudoprimes did not exist, then we would have some very nice and very simple primality tests at our disposal: We could choose a Lehmer sequence we like, take an integer $n$, divide it into $U_{n-1}$, and if the remainder is $0$ then $n$ is prime. Otherwise, $n$ is composite. I furthermore add that I am quite sure that there is no non-trivial Lehmer sequence that is currently known to be free of such pseudoprimes, for if there was one, we could easily use it to test arbitrary integers $n$ for primality in the manner alluded to.
That being said, we ask, what is the significance of knowing if $\phi(n) | (n - 1)$?
Well, how do we usually obtain $\phi(n)$?
We factor $n$ and then compute $\phi(n)$.
But suppose it is not feasible to factor $n$?
Well, it then might be very helpful to know the order of $n$ (i.e., \omega(n)) in the underlying sequence. If we can obtain this value, then knowing that it divides $\phi(n)$, we can check all multiples of $\omega(n)$ up to $n-1$. One of them has to be $\phi(n)$. In the case of a semiprime $pq$, once you have $\omega(n),$ then $\phi(n)$ is just $n + 1 - (p + q)$. But it gets more difficult if you don't know ahead of time how many factors $n$ has. Besides, $\omega(n)$ is equivalent to the discrete logarithm problem, which computational speaking, is solved in exponential time.
So, with Lehmer's Totient Conjecture, if we were given a composite $n$ for which $\phi(n) | n - 1$, then not only is $\phi(n)$ a factor of $n-1$, but so also is $\omega(n)$. It doesn't necessarily make the problem of ascertaining $\phi(n)$ easy, but it likely makes it somewhat easier. For instance, in the case of semiprimes, we expect that it will be somewhat less difficult to factor $pq-1$ than $pq$ (although semiprimes are not a type of composite number that potentially can satisfy the Lehmer Totient Conjecture.)
In conclusion, it seems to me that this important conjecture might have been a serious afterthought of D.H. Lehmer. If I recall correctly from reading parts of Lehmer's 1930 paper, he did not treat composite $n$ to the extent that he did for primes. It seems certain that he would have thought about the problem that formed the subject of his 1932 paper, but he probably didn't mention it because he had not given it sufficient thought---for as it turns out, it is a problem of great complexity as evidenced by its having remained open for almost ninety years now. 
Finally, I note that in his musing on the problem, it was he who discovered that if there does exist a composite solution to his conjecture, then it must be odd, square-free, and divisible by at least seven distinct prime divisors.
