Q: Let $n$ be an integer not divisble by 3. Suppose that $p=n^2+n+1$ is a prime and $2^{n+1}\equiv 1 \pmod{p}$. Is $n$ a power of $2$?

A solution to this problem would imply that every finite flag-transitive projective plane is Desarguesian. Walter Feit obeserved this in his 1990 paper in the Proceedings of the American Mathematical Society, and he confirmed by computer that it is true for $n\le 14,400,008$. Since then, there has been some review and survey of this problem by various authors, and I’m surprised to see that none have sat at the computer and tried to extend Feit’s computation.

So I gave it a crack myself:

The answer is “Yes” for $n \le 30,000,000$.

This can definitely be extended by far better programmers than me … any advance on this bound?

## 9 thoughts on “Yet another interesting number theory question”

1. Is there any reason to suspect this is true? Heuristically, one might expect that p=n^2+n+1 is prime with probability 1/2log(n). If p is indeed prime then 2^(n+1) is a n-th root of 1 mod p, which should happen with probability 1/n. So expected number of solutions becomes sum_n (n log n)^(-1), and so one might expect to have C log(log x) solutions n to your system with n at most x.

Of course a more sophisticated argument may invalidate this heuristic. But my first inclination is that the answer to your question is no, but that a computer search is not guaranteed to find a counterexample, due to the very slow groth of the loglog function.

2. Heh, that’s the sort of thing I sometime enjoy.

I got from 0 to 60,000,000 in about *16 seconds* (using 24 cores).
Here’s the code I’m running:

I’m output the data for each range of 10^7 values of n in the files in
the data directory. I’m including multiples of 3 as a sort of
consistency check on the code and to see if that suggests any other
structure. Also, I’m using a fairly weak primality test —
fortunately this is the sort of computation for which that is fine —
if the test fails then that just means there would be a spurious n in
our table, so we could double check it later.

In writing the above… my program got past 400,000,000. I set it
going for what should take about one day, and go up to 30*10^10 =
300,000,000,000.

1. My calculation completed up to 3*10^11, found no new examples, and took 22.38 hours walltime (hence probably about 20 days CPU time).

1. This just exceeds the Thas-Zagier computational result in their paper of $2 \times 10^{11}$. I should look more closely at your code, but have you used some of the other info such as $n\equiv 0\pmod 8$? (See Thas and Zagier’s paper for more).

2. Hi. My code’s completely straightforward (I think), and I didn’t use any extra information. In fact, I even included the n that are divisible by 3. One slightly clever idea is that I use a fast primality test in MPIR (GMP) that could pronounce p prime even though p is composite. That’s fine, since after the fact if this ever happens, one just checks more carefully.

3. Hi,

I pushed my computation up to 10^12 (instead of merely 3*10^11). I found no new examples.

— William

3. A short program in Sage indicates the answer to the question is “yes” for $n <= 1,000,000,000$.

4. Sonia Balagopalan says:
5. Thanks Sonia; I just realised that Koen and Don had extended the numerical computations, but it seems the folk on this comment list might be able to exceed the bounds they got. I too used sage and easily got up to $4\times 10^7$. But I agree with Peter, a solution will be hard to find considering the growth of log(log(x)) (which is an optimistic expected value function).