For any positive integer , we define to be the number of positive integers less than and relatively prime to .
Question: Does there exist an infinite sequence of positive integers , satisfying:
Solution
No such sequence exists. We use proof by contradiction, assuming such an infinite sequence exists, we express each as , where is odd. Then by properties of the -function, we have .
Note that cannot be , otherwise we would get , , and finally , which obviously contradicts . In this case we have is even. Comparing shows that .
Since are all nonnegative integers, they cannot keep decreasing forever, so there must exist some positive integer after which (below we always assume the variable ) we have . Comparing the above equation shows that , and
.
By properties of the -function, if is not a multiple of 4, then must be a power of some odd prime, denote , where is a prime. Now consider , we have
Hence or .
If (for some ), then has only the two prime factors 2 and 3, and it is easy to check that subsequently will also only have prime factors 2 and 3, but , a contradiction, so we must have , that is, (for all ).
Thus, for all , we have , and these are all primes. We note that for any positive integer , . Let , then by Fermat's Little Theorem, , hence , which contradicts being prime. This completes the proof.