Maths Olympiad Prep

Library / /67 of 169

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it United States

Prove that for each positive integer nn, there are pairwise relatively prime integers k0,k1,,knk_0, k_1, \dots, k_n, all strictly greater than 1, such that k0k1kn1k_0 k_1 \cdots k_n - 1 is the product of two consecutive integers.

Solutions — 3

Solution 1

We proceed by induction. The case n=1n=1 is clear, since we may pick k0=3k_0 = 3 and k1=7k_1 = 7. Let us assume now that for a certain nn there are pairwise relatively prime integers 1<k0<k1<<kn1 < k_0 < k_1 < \cdots < k_n such that k0k1kn1=an(an1)k_0 k_1 \cdots k_n - 1 = a_n(a_n - 1), for some positive integer ana_n. Then choosing kn+1=an2+an+1k_{n+1} = a_n^2 + a_n + 1 yields
k0k1kn+1=(an2an+1)(an2+an+1)=an4+an2+1, k_0 k_1 \cdots k_{n+1} = (a_n^2 - a_n + 1)(a_n^2 + a_n + 1) = a_n^4 + a_n^2 + 1,
so k0k1kn+11k_0 k_1 \cdots k_{n+1} - 1 is the product of the two consecutive integers an2a_n^2 and an2+1a_n^2 + 1. Moreover,
gcd(k0k1kn,kn+1)=gcd(an2an+1,an2+an+1)=1, \gcd(k_0 k_1 \cdots k_n, k_{n+1}) = \gcd(a_n^2 - a_n + 1, a_n^2 + a_n + 1) = 1,
hence k0,k1,,kn+1k_0, k_1, \dots, k_{n+1} are pairwise relatively prime. This completes the proof.

Solution 2

Write the relation to be proved as
4k0k1kn=4a(a+1)+4=(2a+1)2+3. 4k_0 k_1 \cdots k_n = 4a(a+1) + 4 = (2a+1)^2 + 3.
There are infinitely many primes for which 3-3 is a quadratic residue. Let 2<p0<p1<<pn2 < p_0 < p_1 < \dots < p_n be such primes. Using the Chinese Remainder Theorem to specify aa modulo pnp_n, we can find an integer aa such that (2a+1)2+3=4p0p1pnm(2a+1)^2 + 3 = 4p_0 p_1 \cdots p_n m for some positive integer mm. Grouping the factors of mm appropriately with the pip_i's, we obtain (2a+1)2+3=4k0k1kn(2a+1)^2 + 3 = 4k_0 k_1 \cdots k_n with kik_i pairwise relatively prime. We then have k0k1kn1=a(a+1)k_0 k_1 \cdots k_n - 1 = a(a+1), as desired.

Solution 3

We are supposed to show that for every positive integer nn, there is a positive integer xx such that x(x+1)+1=x2+x+1x(x+1)+1 = x^2+x+1 has at least nn distinct prime divisors. We can actually prove a more general statement.

Claim. Let P(x)=adxd++a1x+1P(x) = a_d x^d + \cdots + a_1 x + 1 be a polynomial of degree d1d \ge 1 with integer coefficients. Then for every positive integer nn, there is a positive integer xx such that P(x)P(x) has at least nn distinct prime divisors.

The proof follows from the following two lemmas.

Lemma 1. The following set is infinite:
Q={pp a prime for which there is an integer x such that p divides P(x)}. Q = \{p \mid p \text{ a prime for which there is an integer } x \text{ such that } p \text{ divides } P(x)\}.
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 p1,p2,,pkp_1, p_2, \dots, p_k in QQ, then for each integer mm, P(mp1p2pk)P(m p_1 p_2 \cdots p_k) is an integer with no prime factors, which must equal 1 or 1-1. However, since PP has degree d1d \ge 1, it takes each of the values 1 and 1-1 at most dd times, a contradiction. \square

Lemma 2. Let p1,p2,,pnp_1, p_2, \dots, p_n, n1n \ge 1 be primes in QQ. Then there is a positive integer xx such that P(x)P(x) is divisible by p1p2pnp_1 p_2 \cdots p_n.
Proof. For i=1,2,,ni = 1, 2, \dots, n, since piQp_i \in Q we can find an integer cic_i such that P(x)P(x) is divisible by pip_i whenever xci(mod pi)x \equiv c_i(\text{mod } p_i). By the Chinese Remainder Theorem, the system of nn congruences xci(mod pi)x \equiv c_i(\text{mod } p_i), i=1,2,,ni = 1, 2, \dots, n has positive integer solutions. For every positive integer xx that solves this system, P(x)P(x) is divisible by p1p2pnp_1 p_2 \cdots p_n. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.