In number theory, Størmer's theorem, named after Carl Størmer, gives a finite bound on the number of consecutive pairs of smooth numbers that exist, for a given degree of smoothness, and provides a method for finding all such pairs using Pell equations. It follows from the Thue–Siegel–Roth theorem that there are only a finite number of pairs of this type, but Størmer gave a procedure for finding them all.
Statement
If one chooses a finite set of prime numbers then the -smooth numbers are defined as the set of integers
that can be generated by products of numbers in . Then Størmer's theorem states that, for every choice of , there are only finitely many pairs of consecutive -smooth numbers. Further, it gives a method of finding them all using Pell equations.
The procedure
Størmer's original procedure involves solving a set of roughly 3k Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to D. H. Lehmer, is described below; it solves fewer equations but finds more solutions in each equation.
Let P be the given set of primes, and define a number to be P-smooth if all its prime factors belong to P. Assume p1 = 2; otherwise there could be no consecutive P-smooth numbers, because all P-smooth numbers would be odd. Lehmer's method involves solving the Pell equation
for each P-smooth square-free number q other than 2. Each such number q is generated as a product of a subset of P, so there are 2k − 1 Pell equations to solve. For each such equation, let xi, yi be the generated solutions, for i in the range from 1 to max(3, (pk + 1)/2) (inclusive), where pk is the largest of the primes in P.
Then, as Lehmer shows, all consecutive pairs of P-smooth numbers are of the form (xi − 1)/2, (xi + 1)/2. Thus one can find all such pairs by testing the numbers of this form for P-smoothness.
Example
To find the ten consecutive pairs of { 2,3,5}-smooth numbers (in music theory, giving the superparticular ratios for just tuning) let P = { 2,3,5}. There are seven P-smooth squarefree numbers q (omitting the eighth P-smooth squarefree number, 2): 1, 3, 5, 6, 10, 15, and 30, each of which leads to a Pell equation. The number of solutions per Pell equation required by Lehmer's method is max(3, (5 + 1)/2) = 3, so this method generates three solutions to each Pell equation, as follows.
For q = 1, the first three solutions to the Pell equation x2 − 2y2 = 1 are (3,2), (17,12), and (99,70). Thus, for each of the three values xi = 3, 17, and 99, Lehmer's method tests the pair (xi − 1)/2, (xi + 1)/2 for smoothness; the three pairs to be tested are (1,2), (8,9), and (49,50). Both (1,2) and (8,9) are pairs of consecutive P-smooth numbers, but (49,50) is not, as 49 has 7 as a prime factor. For q = 3, the first three solutions to the Pell equation x2 − 6y2 = 1 are (5,2), (49,20), and (485,198). From the three values xi = 5, 49, and 485 Lehmer's method forms the three candidate pairs of consecutive numbers (xi − 1)/2, (xi + 1)/2: (2,3), (24,25), and (242,243). Of these, (2,3) and (24,25) are pairs of consecutive P-smooth numbers but (242,243) is not. For q = 5, the first three solutions to the Pell equation x2 − 10y2 = 1 are (19,6), (721,228), and (27379,8658). The Pell solution (19,6) leads to the pair of consecutive P-smooth numbers (9,10); the other two solutions to the Pell equation do not lead to P-smooth pairs. For q = 6, the first three solutions to the Pell equation x2 − 12y2 = 1 are (7,2), (97,28), and (1351,390). The Pell solution (7,2) leads to the pair of consecutive P-smooth numbers (3,4). For q = 10, the first three solutions to the Pell equation x2 − 20y2 = 1 are (9,2), (161,36), and (2889,646). The Pell solution (9,2) leads to the pair of consecutive P-smooth numbers (4,5) and the Pell solution (161,36) leads to the pair of consecutive P-smooth numbers (80,81). For q = 15, the first three solutions to the Pell equation x2 − 30y2 = 1 are (11,2), (241,44), and (5291,966). The Pell solution (11,2) leads to the pair of consecutive P-smooth numbers (5,6). For q = 30, the first three solutions to the Pell equation x2 − 60y2 = 1 are (31,4), (1921,248), and (119071,15372). The Pell solution (31,4) leads to the pair of consecutive P-smooth numbers (15,16).
Counting solutions
Størmer's original result can be used to show that the number of consecutive pairs of integers that are smooth with respect to a set of k primes is at most 3k − 2k. Lehmer's result produces a tighter bound for sets of small primes: (2k − 1) × max(3,(pk+1)/2).