Maths Olympiad Prep

Library / China Western Mathematical Olympiad /22 of 51

China Western Mathematical Olympiad

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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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