Problem:
Prove that for each positive integer , there are pairwise relatively prime integers , , all strictly greater than 1 , such that is the product of two consecutive integers.
Solution:
First solution: We proceed by induction. The case is clear, since we may pick and .
Let us assume now that for a certain there are pairwise relatively prime integers such that , for some positive integer . Then choosing yields
so is the product of the two consecutive integers and . Moreover,
hence are pairwise relatively prime. This completes the proof.
Second solution: Write the relation to be proved as
There are infinitely many primes for which -3 is a quadratic residue. Let be such primes. Using the Chinese Remainder Theorem to specify modulo , we can find an integer such that for some positive integer . Grouping the factors of appropriately with the 's, we obtain with pairwise relatively prime. We then have , as desired.
Third solution: We are supposed to show that for every positive integer , there is a positive integer such that has at least distinct prime divisors. We can actually prove a more general statement.
Claim. Let be a polynomial of degree with integer coefficients. Then for every positive integer , there is a positive integer such that has at least distinct prime divisors.
The proof follows from the following two lemmas.
Lemma 1. The set
{ a prime for which there is an integer such that divides } is infinite.
Proof. The proof is analogous to Euclid's proof that there are infinitely many primes. Namely, if we assume that there are only finitely many primes in , then for each integer is an integer with no prime factors, which must equal 1 or -1 . However, since has degree , it takes each of the values 1 and -1 at most times, a contradiction.
Lemma 2. Let be primes in . Then there is a positive integer such that is divisible by .
Proof. For , since we can find an integer such that is divisible by whenever . By the Chinese Remainder Theorem, the system of congruences has positive integer solutions. For every positive integer that solves this system, is divisible by .
This problem was suggested by Titu Andreescu.
The problems on this page are the property of the MAA's American Mathematics Competitions