![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
joshuazelinskyI mentioned Lehmer's Conjecture in an earlier post. Recently, someone asked me how one goes about proving something like the sort of result that a couunterexample needs to have a lot of distinct prime factors. I wrote an answer to them, and this is a version of that answer which may be of interest to people who read the earlier post. This post is slightly more technical than most of the other math posts currently here.
The primary technique used is the following. In what follows, I'll write capital N for a counterexample to Lehmer's conjecture, and use n for a generic integer where we aren't necessarily making that assumption. I'll implicitly assume that you've seen the Euler phi function a bit before. If not, the Wikipedia article is a good place to start . But the main takeaway we need about it is that if I have n=p^a for some prime p, then I can write phi(n) = (p-1)p^(a-1), I can multiply together the phi values at each highest prime power which divide n. For example, if n = 360, 180 =2^3 * 3^2 * 5 I can write phi(360)= phi(2^3) phi(3^2) phi(5) = (2-1)2^2 * (3-1)3^1 * (5-1) = 4*2*3*4=96. This formula will come in handy below. We won't need any other properties beyond what was mentioned in the previous post about Lehmer's Conjecture.
In the below, we'll write a|b to mean that a is a divisor of b. For example, 3|6 is true but 4|6 is false. We'll need two preliminary remarks:
First, note that any such N must be odd. To see this, note that since phi(n) is even for n>2, if N is a counterexample, then N must be odd, since if N were even, N-1 would not be divisible by phi(N).
Second, note that any such N must be squarefree (that is not divisible by the square of a prime). To see this, note that from the standard formula for phi(n), if p^2 |n, then p|phi(n).
So if N is divisible by p^2 for some prime p, then since p|phi(n), we'll have p|N-1 and p|N which is impossible.
We'll define H(n) as the product of p/(p-1) over all primes which divide n. For example, H(60)= (2/1)(3/2)(5/4) = 15/4.
Important things to note about H(n). First, H(n) is multiplicative; that H(ab)= H(a)H(b) whenever a and b have greatest common divisor 1. Second, since x/(x-1) is a decreasing function, so if we replace a prime in the factorization of n with a larger prime, the value of H goes down. For example, H(3) > H(5) and H(20) > H(45).
Notice that H(n) = n/phi(n). Now, if phi(N)|N-1 for some composite N, then k phi(N) = n-1 for some k >1, and therefore we have H(n) = n/phi(n) > (n-1)/phi(n) = k. In particular, for any such N one must have H(N) > 2.
From this one immediately has that any such N has to have at least three distinct prime factors. To see this, note that H(15) = (3/2)(5/4) = 15/8 < 2, and again replacing any prime with a larger prime would result in H being even smaller.
To give a flavor of the general method, let's sketch a proof that N needs to have at least five distinct prime factors.
One Lemma that will be helpful first:
Lemma 1: If N is a counterexample to Lehmer's conjecture and p|N for some prime p, and q|N for some prime q then we cannot have p|q-1.
Proof: Assume we had such, then by the formula for phi(n) we'd have p-1|N-1 and hence q|N-1 since q|p-1. But we cannot q|N and q|n-1.
(For example, this Lemma shows that we cannot have both 3|N and 7|N. Very handy little bit.)
Theorem: There is no such N with three distinct prime factors.
Proof: Assume that N is such an N. Note that (5/4)(7/6)(11/10) < 2. So our smallest prime factor must be 3. So 7 does not divide N by our Lemma. Similarly, since (3/2)(11/10)(13/12)< 2, our second largest prime factor must be 5, and thus by our Lemma our third prime factor cannot be 11. It also cannot be 13 by our Lemma. We now need a prime p (3/2)(5/4)(p/(p-1) > 2. But solving this inequality one will find that one needs p<17, so there are no primes which remain to check.
Now we'll sketch the same technique for the slightly harder case of four distinct prime factors. But the above shows most of the central ideas. Below will be essentially just an elaboration of the same technique.
Theorem: No such N has four distinct prime factors.
Proof:We'll break this down into two cases, based on whether 3 is a prime factor of N.
Case I:Assume 3|N. By our Lemma, we cannot have 7, 13 or 19 as divisors of N. Now, we'll break this down into two subcases based on whether 5|N.
Case Ia: 5|N. In that case, by our Lemma we have that 11 does not divide N. Let's break this down slightly further. Note that if the second largest prime factor of N is 29 then since (3/2)(5/4)(29/28)(47/46)< 2 we have a contradiction. (Exercise: Why was I able to get away with skipping 31, 37, 40 and 43 as possible prime divisors?). So we have some subcases where the third prime factor is 17, 23 or 29. If the third prime factor is 17, then we must have for the fourth prime factor p, that (3/2)(5/4)(17/16)(p/(p-1)) > 2. Solving for this, one will find that one must have p <= 257. Now, checking all primes which are at most 257 will find that none of them work. Similarly, one can do the same thing if the third prime is 23 or 29. (If one is lazy and is doing this with a computer one doesn't even need to calculate the precise largest bound for when (3/2)(5/4)(23/22)(p/(p-1)) > 2, since we know it must be no higher than 257. The same remark applies to 29.)
Case Ib, where 5 is not a divisor of N. Then we have (3/2)(11/10)(17/16)(23/22) < 2 so we're done. (Note that if this hadn't been less than 2 we could have used that we can't actually have both 11|N and 23|N so we could have broken this down further but we didn't need to).
Case II: We've assumed that 3 doesn't divide N. Note that (5/4)(7/6)(11/10)(13/12) < 2, so we're done. (Again note that if this had been too large we could have broken down into subcases depending on whether 5 divides N and then thrown 11 out in one of them.)
That's the basic technique. In practice, one wants to do as much of this as one can via computers and there are a few other ideas and tweaks which one can do to save on case checking.
