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.
Solutions — 3
Solution 1
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.
Solution 2
Write the relation to be proved as
There are infinitely many primes for which 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.
Solution 3
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 following set 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 . However, since has degree , it takes each of the values 1 and 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 .