1995 NT #1: Let be a positive integer. Show that there are infinitely many perfect squares of the form where is a positive integer.
_______

Clearly, for each if there is one perfect square that is then there are infinitely many perfect squares. We proceed with induction on . When we have Suppose that the result holds for some Then we have for some If we try to find such that It is clear that such a exists because we need for which has roots, such as Our induction is complete. Therefore, the result holds for all

1999 NT #3: Prove that there exists two strictly increasing sequences and such that divides for every natural n.
_______

Note that for each if there exists a such that or equivalently, if is a quadratic residue mod then we can find a such that Additionally, it is clear that if is a quadratic residue of and then it is a quadratic residue of It claim that this is true for all In fact, we can generalize this to all primes not just Clearly, is now a quadratic residue of We now prove the stronger statement that is a quadratic residue of all We proceed by induction on It is true for Assume that it holds for some It follows that for some If we find such that Let Then we have or Since we can obviously find such an our induction is complete, and we are done.

Main point(s): These problems demonstrate a trick in using induction to determine the existence of certain quadratic residues for powers.