Maths Olympiad Prep

Library / Cesenatico /4 of 29

Cesenatico

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+1−3n2+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+1−3n2+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 p−1p-1 as pp ranges over SS (that is, nn is Euler's totient function of the product of the primes in SS). Since a1=22−32+52=20=22⋅5a_{1}=2^{2}-3^{2}+5^{2}=20=2^{2} \cdot 5, then 4=5−14=5-1 divides nn. Moreover, for every p∈Sp \in S, except possibly the cases p=2,3,5p=2,3,5, we have, by Fermat's little theorem, 2n≡3n≡5n≡1( mod p)2^{n} \equiv 3^{n} \equiv 5^{n} \equiv 1(\bmod p), from which
an=2n3+1−3n2+1+5n+1≡2−3+5≡4( mod p)∀p∈S,p≠2,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 an≡2−0+2≡1( mod 3)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, an≡2−3+0≡−1( mod 5)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 n≥2n \geq 2, we have 0<3n2+1−5n+1<2n30<3^{n^{2}+1}-5^{n+1}<2^{n^{3}}, from which
2n3=2n3+1−2n3<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,604 problems in a working order, from Junior Challenge 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.