Maths Olympiad Prep

Library / /23 of 54

Number theory Difficulty 6.0 AIME, harder Prove it China

Prove that for any given positive integer kk, there exist infinitely many positive integers nn, such that the numbers
2n+3n−1,2n+3n−2,…,2n+3n−k 2^n + 3^n - 1, 2^n + 3^n - 2, \dots, 2^n + 3^n - k
are all composite.

Solution

For any given positive integer kk, choose positive integer mm sufficiently large such that 2m+3m−k>12^m + 3^m - k > 1. Consider the following kk integers:
2m+3m−1,2m+3m−2,…,2m+3m−k, 2^m + 3^m - 1, 2^m + 3^m - 2, \dots, 2^m + 3^m - k,
all of which are larger than 11. From each of these integers, pick a prime factor: p1,p2,…,pkp_1, p_2, \dots, p_k, and let
nt=m+t(p1−1)(p2−1)⋯(pk−1), n_t = m + t(p_1 - 1)(p_2 - 1)\cdots(p_k - 1),
where tt is an arbitrary positive integer. For any fixed integer ii (1≤i≤k1 \le i \le k), one has 2nt≡2m(modpi)2^{n_t} \equiv 2^m \pmod{p_i}. In fact, if pi=2p_i = 2, then the result is obvious. Assuming that pi≠2p_i \ne 2, it follows from Fermat's little theorem that
2nt=2m⋅2t(p1−1)(p2−1)⋯(pk−1)≡2m⋅1=2m(modpi). 2^{n_t} = 2^m \cdot 2^{t(p_1-1)(p_2-1)\cdots(p_k-1)} \equiv 2^m \cdot 1 = 2^m \pmod{p_i}.
Similarly, one has 3nt≡3m(modpi)3^{n_t} \equiv 3^m \pmod{p_i}. Observe that
2nt+3nt−i≡2m+3m−i≡0(modpi), 2^{n_t} + 3^{n_t} - i \equiv 2^m + 3^m - i \equiv 0 \pmod{p_i},
2nt+3nt−i>2m+3m−i. 2^{n_t} + 3^{n_t} - i > 2^m + 3^m - i.
Hence, 2nt+3nt−i2^{n_t} + 3^{n_t} - i is a composite number.
Therefore, ntn_t is one of the positive integers nn such that
2n+3n−1,2n+3n−2,…,2n+3n−k 2^n + 3^n - 1, 2^n + 3^n - 2, \dots, 2^n + 3^n - k
are all composite. As tt is arbitrarily chosen, there are infinitely many such positive integers satisfying the conditions above.

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.