Maths Olympiad Prep

Library / /9 of 120

Number theory Difficulty 4.5 AIME Prove it Croatia

Prove that there are infinitely many positive integers nn such that 2n82^n - 8 is divisible by nn. (Kristina Ana Škreb)

Solution

We will prove that for all positive integers of the form n=3pn = 3p (where p>3p > 3 is a prime number)
n2n8. n \mid 2^n - 8.
By Fermat's little theorem we have 2p2(modp)2^p \equiv 2 \pmod{p}, so it follows that
23p8=(2p)38238=0(modp).(9) 2^{3p} - 8 = (2^p)^3 - 8 \equiv 2^3 - 8 = 0 \pmod{p}. \quad (9)
Analogously, since 3p3p is an odd number, we have
23p8(1)3p230(mod3).(10) 2^{3p} - 8 \equiv (-1)^{3p} - 2 \equiv -3 \equiv 0 \pmod{3}. \quad (10)
Since 33 and pp are relatively prime, from (9) and (10) we conclude that
23p80(mod3p). 2^{3p} - 8 \equiv 0 \pmod{3p}.
There are infinitely many prime numbers greater than 33, hence the assertion follows.

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.