Show that there are arbitrarily long intervals of positive integers that cannot be expressed as sums of two squares.
I know already the result of Fermat's theorem on sums of two squares - Wikipedia, the free encyclopedia
Anyone has a proof?
Show that there are arbitrarily long intervals of positive integers that cannot be expressed as sums of two squares.
I know already the result of Fermat's theorem on sums of two squares - Wikipedia, the free encyclopedia
Anyone has a proof?
Nice problem!
Let be distinct primes of the form , and let ; using the Chinese Remainder Theorem, we can solve the congruences
simultaneously. Now suppose for where , and for where . Let where
(set if ). I claim that for all . First, suppose for some ; since , we must have which is clearly false. On the other hand, if for some , since we have we must have which is also false.
Thus the consecutive integers are each divisible by a prime of the form only once, and hence none of them is a sum of two squares. By taking to be as large as we wish, we solve the problem.
It should be noted that one would expect this to hold also for sums of two cubes, for examples. Given that the cubes are less dense than the squares, such sequences would be even more common than in our case. However, a completely different method would be required to prove it.
Note also that a little bit of extra work can easily yield an (albeit bad) maximum bound on the size of the smallest which is the first term of a sequence of consecutive integers none of which is the sum of two squares.
Let be the number of sums of two squares less than . Then there is a constant such that . (See Landau-Ramanujan constant.)
I tried but I dont understnad the proof. What is S, is it an arbitrary subset of the first n integers? And you suppose something here, but where do you contradict it, or where do you handle the case if its false?
Please tell me the general idea as well, as your proof looks quite nice.
First, recall that an integer is a sum of two squares if and only if its squarefree part is divisible by no prime of the form . So I constructed a sequence of integers, each of which is divisible by a prime of the form only once.
Once we have the solution to the original system of congruences, we obtain consecutive integers, each of which is divisible by a prime of the form . However we want to make sure that the squares of these primes do not divide the given integers; so we find another solution to the system. Remember that any solutions of a system of the type I gave is determined only modulo the product of the moduli of the equations. So we translate the given solution by . The choice of is crucial if we want to make sure that for all ; we partition the set of primes as , where the primes in the first of the two sets are those which are problematic (those for which , which we don't want to happen). You can convince yourself by reading my proof again that the choice of yields a solution to the problem.
Note also that I suppose that there are infinitely many primes of the form (which is a very specific case of Dirichlet's theorem on primes in arithmetic progressions).