is the sequence of all natural numbers that can be written as the sum of squares of two natural numbers. Prove that for infinitely many natural numbers , .
Solution
We prove that for any odd integer , there are infinitely many positive integers , such that . For sake of this reason we will use the following lemma.
Lemma 1. Let be a positive integer which is not a perfect square. There exist infinitely many primes such that is quadratic non-residue modulo them.
Proof. Let be the square free part of integer , where 's are distinct primes. Now choose the quadratic non-residue modulo and set as quadratic residues modulo , respectively. Now by Chinese Remainder Theorem and Dirichlet's Theorem one can find infinitely many primes satisfying
Note that if one of the primes named is equal to , then omit the first congruence and just add the criterion and we are done.
Now set and consider the sequence . In this sequence the first and the last term are represented as sum of two squares. We will prove that there are infinitely many integers such that only these two terms could be representable as sum of two squares. According to the lemma, there exist primes such that for each , is quadratic non-residue modulo . Now we establish the following lemma.
Lemma 2. Let be a quadratic residue modulo prime and . Then there is integer such that , and .
Proof. Let us note that . Then one of and satisfies the desired conditions.
Now by this lemma there exist positive integers such that () and we have
Next, let for . Then, the numbers are all divisible by and not . Now, since , cannot be written as sum of two squares. So we are done.