![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
joshuazelinskyI've mentioned before that there are a lot of simple to state but not so incredibly famous open problems. I want to talk about two thematically related problems, Lehmer's Totient Problem, and Carmichael's Conjecture. These problems are well known to number theorists but don't have the same general fame as say Goldbach's Conjecture or the existence of odd perfect numbers.
Recall two numbers are relatively prime when their greatest common divisor is 1. For example, 15 and 8 are relatively prime. But 21 and 15 are not relatively prime because their GCD is 3. We'll define phi(n) to be the number of positive integers which are less than or equal to n and relatively prime to n. This function is known as the Euler phi function. For example, phi(9) =6 because under 9 we have 1,2,4,5,7 and 8 as numbers which are relatively prime to 9. Note that if p is a prime, then phi(p)=p-1. For example, phi(5) =4 since the numbers which are less than or equal to 5 and relatively prime to 5 are everybody: 1,2,3 and 4. (If you haven't seen the phi function before, it might be worth playing around with. Can you find phi(20)? What is phi of a power of 2? What is phi of a prime power in general?)
For a given positive integer a and another integer n we want to understand how big the smallest positive integer k is so that a^k leaves a remainder of 1 when we divide by n. For example, if a =2 and n =5, then one may take k=4, since 2^4 = 16 which leaves a remainder of 1 when we divide by 5. Similarly, if a=4 and n=7, then k = 3, since 4^3 = 64 which leaves a remainder of 1 when divided by 7.
Such a k doesn't always exist for a given n. If a and n share a common factor greater than 1, then so will a^k and n, and so the remainder of a^k when divided by n will also share the common factor, and so the remainder cannot be 1. For example, let's look at powers of 2 and their remainder when we divide by 10. We have 2,4, 8, 16, 32,64, 128, 256. When we divide by 10, we get as remainders 2,4,8, 6, 2,4,8, 6 ... And it keeps repeating this way.
But maybe there always is such a k as long as a and n are relatively prime. This turns out to be the case.
The first step towards proving this was due to Fermat. He proved what is now often called "Fermat's Little Theorem" (to contrast it with "Fermat's Last Theorem" but confusingly also abbreviated as FLT) which was that if p is prime, and a is not divisible by p (hence they must be relatively prime) then a^(p-1) leaves a remainder of 1 when one divides by p. So when n=p, we can in this situation always take p-1. The number p-1 may remind you of something, which we had earlier. When p was prime we had phi(p)=p-1. (A good exercise is to verify this works with p=7. That is, check that a^6 always leaves a remainder o 1 when you divide by 7 for a=1,2,3,4,5 or 6.)
And this is in fact the proper generalization! Euler proved a much stronger result: Recall we defined phi(n) be the number of positive integers which are less than or equal to n, and which share no common factor greater than 1 with n. Then Euler proved that if a and n share no common factor, then aphi(n) leaves a remainder of 1 when I divide by n. So, for k we care about is always at most phi(n). One might be interested in given an a and n what is the least value of k, and that's a delicate question that my own PhD work touched on. But that's a separate question. Phi(n) also shows up in some practical cryptographic applications, but that's not our emphasis today.
D. H. Lehmer in the 1930s was interested in how if p is a prime, then phi(p)=p-1. Lehmer noted that if n is composite then obviously phi(n) has to be strictly smaller than n-1, but maybe it fits in neatly to n-1. That is, maybe there is a composite number where phi(n) divides n-1? Lehmer conjectured that this was not the case. We don't know, but we do know that if there is such a number it needs to be pretty big (greater than 10^22 ), and it needs to have at least 15 distinct prime factors. If someone has the time and effort with some decent amount of computing power, they could likely improve this substantially. The technique used to obtain that bound is a little more clever than just checking every number under 10^22, but it doesn't involve deeply subtle number theory. My suspicion is that someone who is a good algorithmist and with some access to decent computing power should be able to improve that bound.
The other conjecture worth talking about in this context is Carmichael's Conjecture. Carmichael noticed that some numbers never arise as the value of phi(n). For example, phi(n) is always even if n >2. To see this note that if b is relatively prime to n, then so n-b, so after 2, numbers relatively prime to n and less than n always come in pairs. So any odd number other than 1 is never the value of the phi function. With a bit more work one can show that some other numbers don't arise either. For example, phi(x)=14 has no solutions.
But, Carmichael noticed that when there was a solution to phi(x)=k, there always seemed to be another y such that x was not equal to y and phi(y)=k. For example, we saw earlier that phi(5)=4. But phi(8) =4 also, since 1, 3,5 and 7 are the numbers which are less than or equal to 8 and relatively prime to 8. Carmichael conjectured that this was always true. That is, if phi(x)=k had a solution, then there was always more than one solution. Another similar example is how we saw that phi(9)=6, but it is also the case that phi(7)=6. (A good exercise: There are two other m such that phi(m)=6. Can you find them?). In this case, we also have very large bounds. In particular, we know that any counterexample to Carmichael's conjecture must be greater than 10^(10^10). That's pretty big.
