Maths Olympiad Prep

Library / /18 of 105

Number theory Difficulty 5.0 AIME, harder Prove it JBMO

Problem:
Determine whether there is a natural number nn for which 8n+478^{n}+47 is prime.

Solution

Solution:
The number m=8n+47m = 8^{n} + 47 is never prime.

If nn is even, say n=2kn = 2k, then m=64k+471+20(mod3)m = 64^{k} + 47 \equiv 1 + 2 \equiv 0 \pmod{3}. Since also m>3m > 3, then mm is not prime.

If n1(mod4)n \equiv 1 \pmod{4}, say n=4k+1n = 4k + 1, then m=8(8k)4+473+20(mod5)m = 8 \cdot (8^{k})^{4} + 47 \equiv 3 + 2 \equiv 0 \pmod{5}. Since also m>3m > 3, then mm is not prime.

If n3(mod4)n \equiv 3 \pmod{4}, say n=4k+3n = 4k + 3, then m=8(642k+1+1)8((1)2k+1+1)0(mod13)m = 8(64^{2k+1} + 1) \equiv 8((-1)^{2k+1} + 1) \equiv 0 \pmod{13}. Since also m>13m > 13, then mm is not prime.

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.