Maths Olympiad Prep

Library / /76 of 120

Number theory Difficulty 5.7 AIME, harder Prove it Croatia

Prove that there are infinitely many positive integers nn such that nn has more than two distinct prime divisors and 2n82^n - 8 is divisible by nn.

Solution

We will prove that for all positive integers of the form n=22p1n = 2^{2p} - 1 (where p>3p > 3 is a prime number) n2n8n \mid 2^n - 8 and nn has at least three distinct prime divisors.

Since 2n8=8(2n31)2^n - 8 = 8(2^{n-3} - 1), to prove n2n8n \mid 2^n - 8 it is sufficient to prove
2pn3. 2^p \mid n - 3.
Namely, in this case n3=2pkn - 3 = 2pk for some positive integer kk, so
2n31=22pk1=(22p)k1=(22p1)(22p(k1)+22p(k2)++22p+1), 2^{n-3} - 1 = 2^{2pk} - 1 = (2^{2p})^k - 1 = (2^{2p} - 1)(2^{2p(k-1)} + 2^{2p(k-2)} + \dots + 2^{2p} + 1),
i.e. 22p1=n2n31n2n82^{2p} - 1 = n \mid 2^{n-3} - 1 \Rightarrow n \mid 2^n - 8.

By Fermat's little theorem we have 2p2(modp)2^p \equiv 2 \pmod p, so it follows that
n3=22p4=(2p)24224=0(modp). n - 3 = 2^{2p} - 4 = (2^p)^2 - 4 \equiv 2^2 - 4 = 0 \pmod p.
Obviously n3n-3 is an even number and since 22 and pp are relatively prime we conclude that
n3=22p40(mod2p). n - 3 = 2^{2p} - 4 \equiv 0 \pmod{2p}.

Now we will show that nn has at least three distinct prime divisors. Note that
n=22p1=(2p1)(2p+1). n = 2^{2p} - 1 = (2^p - 1)(2^p + 1).
Since 2p12^p - 1 and 2p+12^p + 1 are two consecutive odd numbers they are relatively prime, so they don't have any common prime divisor. 2p12^p - 1 has at least one prime divisor so it is sufficient to show that 2p+12^p + 1 has at least two distinct prime divisors. Since p>3p > 3 we can write p=3k+rp = 3k + r, where k1k \ge 1 and r{1,2}r \in \{1, 2\}.

Since pp is odd, we have:
2p+1(1)p+1=1+1=0(mod3) 2^p + 1 \equiv (-1)^p + 1 = -1 + 1 = 0 \pmod{3}
and
2p+1=(23)k2r+1(1)k2r+10(mod9). 2^p + 1 = (2^3)^k \cdot 2^r + 1 \equiv (-1)^k 2^r + 1 \neq 0 \pmod{9}.
We have proved that 2p+12^p + 1 is divisible by 33, but it's not divisible by 99 which means that 2p+12^p + 1 can not be a power of 33, i.e. 2p+12^p + 1 has at least one prime divisor different from 33.

This proves the assertion of the problem.

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.