Consecutive Residues

Pick a prime p and call n an 8th-power residue if n ≡ x⁸ (mod p) for some x. Sooner or later two consecutive numbers r and r + 1 are both residues. How long can that first pair be put off? Lehmer, Lehmer, Mills and others answered this for squares through 7th powers between 1962 and 1964. For 8th powers the answer is a(8) = 1,508,324. It is reached by infinitely many primes, and no prime does better.

1,508,324

a(8): the longest possible wait

1,229,269

pairs cited by the impossibility proof

9 → 1.5M

a(2) … a(8): squares to 8th powers

Figure 1

One and a half million numbers, no two residues in a row

Every square below is one number, read left to right and top to bottom, starting at 1. Dark squares are residues. In the extremal case for 8th powers about one number in eight is a residue, yet no two of them touch until 1,508,324 = 2²·47·71·113 and 1,508,325 = 3·5²·7·13²·17, ringed at the end.

Hover or drag over the grid to move the lens. In the lens each cell shows χ(n), the index of n mod k (explained below); residues are the cells with χ(n) = 0. Your browser computes the whole grid from the character's values on primes and checks where the first pair lands.

Power

residue, χ(n) = 0 non-residue first consecutive pair past the pair

Figure 2

The whole game is choosing values on primes

For a prime p = km + 1, fix a primitive root g. Every n has an index: g^{ind n} ≡ n (mod p). Then n is a k-th power residue exactly when ind n ≡ 0 (mod k). Write χ(n) = ind n mod k. Indices add when numbers multiply, so χ is fixed by its values on the primes. Any choice of values on finitely many primes is realized by infinitely many p; for k = 8, χ(2) must be even, because 2 is a square mod every p = 8m + 1. So a(k) is a puzzle: give each prime a value mod k so that the first r with χ(r) = χ(r + 1) = 0 comes as late as possible.

Each strip shows one maximal choice, the primes on a log scale up to the last one that needed a value. Most primes get χ = 1 (left blank); the colored ticks are the exceptions. Primes beyond the strip are given a value that makes all their multiples non-residues, which is possible because a large prime q only appears as j·q with j < q.

χ(q) = 0, q is itself a residue χ(q) = 2 χ(q) = 3 blank: χ(q) = 1

k	a(k)	first pair	values on primes	found by

Figure 3

Ordinary primes never get close

The extremal values come from primes that agree with the special character on every prime up to about 1.5 million, so they are astronomically large. A typical prime finds its first pair quickly. Each dot is a prime p ≡ 1 (mod k), plotted at the first r where r and r + 1 are both k-th power residues; your browser computes these by modular exponentiation. Records are highlighted. The dashed line is a(k).

A handful of small primes have no consecutive pair at all, because they have so few residues. These exceptional primes (29, 71, 113 and 491 for k = 7) are marked × at the top.

Power Primes up to

a prime p new record × exceptional (no pair)

Figure 4

Why 1,508,325 is impossible

To show that no character avoids a pair below 1,508,325, a program tries values for the primes in order (2, 3, 5, …). Each time a choice would create a residue pair, it cuts that branch. A branch also dies when a later prime has no safe value left. The whole search tree has 78,438 nodes, and every dead end is witnessed by one explicit pair (r, r + 1). An independent checker re-derives all of them by factoring.

Search nodes by the prime being decided

Pairs used to close branches, by size of r

The pairs the proof leans on most

Pairs of very smooth neighbors close the most branches. The top one, 6560 = 2⁵·5·41 next to 6561 = 3⁸, is the same pair Brillhart and the Lehmers singled out in 1964.

Method

How a(8) was settled

The search is the 1964 Brillhart–Lehmer–Lehmer "case vector" method, with forward checking added. When a number's only undecided prime is its largest, values for that prime that would pair it with a known residue neighbor are crossed off in advance. The search also treats characters that differ by a unit multiple mod 8 as the same, and it stops at primes above √N, which can always be made harmless. Each yes/no run takes about 30 seconds. The same program reproduces a(2) through a(7).

Don Reble had shown 1,499,876 ≤ a(8) ≤ 1,508,324 in 2019. The new computation finds a character whose first pair is exactly 1,508,324, so his upper bound is the value. It also writes a proof tree showing that nothing reaches 1,508,325. Both were checked by separate Python code. The code, the certificate and the logs are in oeis-results/A000445.