Maths Olympiad Prep

Library / /4 of 31

Number theory Difficulty 5.5 AIME, harder Prove it Italy

Problem:

Prove that there exist infinitely many prime numbers that divide at least one integer of the form 2n3+13n2+1+5n+12^{n^{3}+1}-3^{n^{2}+1}+5^{n+1} with nn a positive integer.

Solution

Solution:

Suppose that the set SS of primes that divide integers of the form an=2n3+13n2+1+5n+1a_{n}=2^{n^{3}+1}-3^{n^{2}+1}+5^{n+1} is finite. We will find a contradiction by exhibiting an integer nn such that ana_{n} possesses at least one prime factor that does not belong to SS.

Let nn be the product of all the numbers p1p-1 as pp ranges over SS (that is, nn is Euler's totient function of the product of the primes in SS). Since a1=2232+52=20=225a_{1}=2^{2}-3^{2}+5^{2}=20=2^{2} \cdot 5, then 4=514=5-1 divides nn. Moreover, for every pSp \in S, except possibly the cases p=2,3,5p=2,3,5, we have, by Fermat's little theorem, 2n3n5n1(modp)2^{n} \equiv 3^{n} \equiv 5^{n} \equiv 1(\bmod p), from which
an=2n3+13n2+1+5n+123+54(modp)pS,p2,3,5 a_{n}=2^{n^{3}+1}-3^{n^{2}+1}+5^{n+1} \equiv 2-3+5 \equiv 4 \quad(\bmod p) \quad \forall p \in S, p \neq 2,3,5
None of the primes in SS can therefore divide ana_{n}, except possibly 2, 3 and 5. On the other hand ana_{n} is not divisible by 3: indeed, since nn is even, we have an20+21(mod3)a_{n} \equiv 2-0+2 \equiv 1(\bmod 3). Moreover ana_{n} is not divisible by 5 either: indeed, since nn is a multiple of 44, an23+01(mod5)a_{n} \equiv 2-3+0 \equiv -1(\bmod 5). If, for contradiction, ana_{n} had only prime factors belonging to SS, then ana_{n} would necessarily have to be a power of 2. Since n2n \geq 2, we have 0<3n2+15n+1<2n30<3^{n^{2}+1}-5^{n+1}<2^{n^{3}}, from which
2n3=2n3+12n3<an<2n3+1. 2^{n^{3}}=2^{n^{3}+1}-2^{n^{3}}<a_{n}<2^{n^{3}+1}.
It follows that ana_{n} lies between two consecutive powers of 2, and therefore cannot itself be a power of 2; this contradiction gives the thesis.

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 translated into English from it; metadata (topic, difficulty) added by this project.