A trick related to Thue's lemma
by randomusername, Feb 22, 2015, 2:44 PM
A simple proof that all primes 
are of the form 
:
Since
is a quadratic residue mod all primes 
(due to the Reciprocity Rule), for all , there is a 
such that 
, so if we take 
such that 
(this always exists because 
is odd), we get 
, whence 
.
OK. Now recall Thue's lemma. It basically says that if
and 
are numbers such that 
, then there are 
with 
and 
such that 
. This is almost trivial to prove. Consider the two sets ![$\{0,1,\dots,[\alpha]\}$](//latex.artofproblemsolving.com/4/0/a/40a5cb7c1df3abf1fc1c4b02313d18af24346aa8.png)
and ![$\{0,1,\dots,[\beta]\}$](//latex.artofproblemsolving.com/f/2/5/f25077f6e97aef429bf440c82fb4bbb5df0d5bc9.png)
. We can compose ![$([\alpha]+1)([\beta]+1)>\alpha\beta\ge p$](//latex.artofproblemsolving.com/0/6/1/06145628628a4d3110dc43809ec4f7e96c1af625.png)
different pairs 
with 
in the first and 
in the second group. Hence there will be two different pairs 
and 
for which 
. Note that 
if and only if 
because 
, hence 
and 
if the pairs are different, and now we may take 
and 
.
Suppose we have chosen in the way described above. Then we have 
. But additionally, 
.
Now let's choose
(I've seen cases where different choices work better, but this suffices in our case.) We find that 
is a number divisible by in the interval 
. But then it is either equal to and we're done, or it is 
, in which case cannot be both odd, and if one is even then the other is even, so all in all, if 
, then 
, which contradicts the fact that is odd. This means only 
is possible.
are of the form 
:Since
is a quadratic residue mod all primes 
(due to the Reciprocity Rule), for all , there is a 
such that 
, so if we take 
such that 
(this always exists because 
is odd), we get 
, whence 
.OK. Now recall Thue's lemma. It basically says that if
and 
are numbers such that 
, then there are 
with 
and 
such that 
. This is almost trivial to prove. Consider the two sets ![$\{0,1,\dots,[\alpha]\}$](http://latex.artofproblemsolving.com/4/0/a/40a5cb7c1df3abf1fc1c4b02313d18af24346aa8.png)
and ![$\{0,1,\dots,[\beta]\}$](http://latex.artofproblemsolving.com/f/2/5/f25077f6e97aef429bf440c82fb4bbb5df0d5bc9.png)
. We can compose ![$([\alpha]+1)([\beta]+1)>\alpha\beta\ge p$](http://latex.artofproblemsolving.com/0/6/1/06145628628a4d3110dc43809ec4f7e96c1af625.png)
different pairs 
with 
in the first and 
in the second group. Hence there will be two different pairs 
and 
for which 
. Note that 
if and only if 
because 
, hence 
and 
if the pairs are different, and now we may take 
and 
.Suppose we have chosen
in the way described above. Then we have 
. But additionally, 
.Now let's choose
(I've seen cases where different choices work better, but this suffices in our case.) We find that 
is a number divisible by in the interval 
. But then it is either equal to and we're done, or it is 
, in which case cannot be both odd, and if one is even then the other is even, so all in all, if 
, then 
, which contradicts the fact that is odd. This means only 
is possible.This post has been edited 1 time. Last edited by randomusername, Feb 22, 2015, 2:52 PM
January 2024
December 2023