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+3n1,2n+3n2,,2n+3nk 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+3mk>12^m + 3^m - k > 1. Consider the following kk integers:
2m+3m1,2m+3m2,,2m+3mk, 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(p11)(p21)(pk1), 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 (1ik1 \le i \le k), one has 2nt2m(modpi)2^{n_t} \equiv 2^m \pmod{p_i}. In fact, if pi=2p_i = 2, then the result is obvious. Assuming that pi2p_i \ne 2, it follows from Fermat's little theorem that
2nt=2m2t(p11)(p21)(pk1)2m1=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 3nt3m(modpi)3^{n_t} \equiv 3^m \pmod{p_i}. Observe that
2nt+3nti2m+3mi0(modpi), 2^{n_t} + 3^{n_t} - i \equiv 2^m + 3^m - i \equiv 0 \pmod{p_i},
2nt+3nti>2m+3mi. 2^{n_t} + 3^{n_t} - i > 2^m + 3^m - i.
Hence, 2nt+3nti2^{n_t} + 3^{n_t} - i is a composite number.
Therefore, ntn_t is one of the positive integers nn such that
2n+3n1,2n+3n2,,2n+3nk 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 and solution reproduced as published; topic and difficulty added by this site.