Maths Olympiad Prep

Library / /24 of 116

Number theory Difficulty 8.0 Shortlist Prove it United States

Consider the sequence a1,a2,a_1, a_2, \dots defined by
an=2n+3n+6n1. a_n = 2^n + 3^n + 6^n - 1.
for all positive integers nn. Determine all positive integers that are relatively prime to every term of the sequence.

Solution

The answer is that 11 is the only such number. It suffices to show that every prime pp divides ana_n for some positive integer nn. Note that both p=2p=2 and p=3p=3 divide a2=22+32+621=48a_2 = 2^2 + 3^2 + 6^2 - 1 = 48.

Now we assume that p5p \ge 5. By Fermat's Little Theorem, we have 2p13p16p11(modp)2^{p-1} \equiv 3^{p-1} \equiv 6^{p-1} \equiv 1 \pmod{p}. Then
32p1+23p1+6p13+2+16(modp), 3 \cdot 2^{p-1} + 2 \cdot 3^{p-1} + 6^{p-1} \equiv 3 + 2 + 1 \equiv 6 \pmod{p},
or, 6(2p2+3p2+6p21)0(modp)6(2^{p-2} + 3^{p-2} + 6^{p-2} - 1) \equiv 0 \pmod{p}; that is, 6ap26a_{p-2} is divisible by pp. Because pp is relatively prime to 66, ap2a_{p-2} is divisible by pp, as desired.

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.