Maths Olympiad Prep

Library / /46 of 82

Number theory Difficulty 5.6 AIME, harder Prove it Croatia

Prove that there exist infinitely many positive integers nn such that the largest prime divisor of n4+n2+1n^4 + n^2 + 1 is equal to the largest prime divisor of (n+1)4+(n+1)2+1(n+1)^4 + (n+1)^2 + 1. (IMO Shortlist 2013)

Solution

Let pnp_n be the largest prime divisor of n4+n2+1n^4 + n^2 + 1 and let qnq_n be the largest prime divisor of n2+n+1n^2 + n + 1. Then pn=qn2p_n = q_{n^2}, and from
n4+n2+1=(n2+1)2n2=(n2n+1)(n2+n+1)=((n1)2+(n1)+1)(n2+n+1) n^4 + n^2 + 1 = (n^2 + 1)^2 - n^2 = (n^2 - n + 1)(n^2 + n + 1) = ((n-1)^2 + (n-1) + 1)(n^2 + n + 1)
it follows that pn=max{qn,qn1}p_n = \max\{q_n, q_{n-1}\} for n2n \ge 2. Keeping in mind that n2n+1n^2 - n + 1 is odd, we have
gcd(n2+n+1,n2n+1)=gcd(2n,n2n+1)=gcd(n,n2n+1)=1. \gcd(n^2 + n + 1, n^2 - n + 1) = \gcd(2n, n^2 - n + 1) = \gcd(n, n^2 - n + 1) = 1.
Therefore, qnqn1q_n \ne q_{n-1}.
To prove the result, it suffices to show that the set
S={nZ2qn>qn1 and qn>qn+1} S = \{n \in \mathbb{Z}_{\ge 2} \mid q_n > q_{n-1} \text{ and } q_n > q_{n+1}\}
is infinite, since for each nSn \in S one has
pn=max{qn,qn1}=qn=max{qn,qn+1}=pn+1. p_n = \max\{q_n, q_{n-1}\} = q_n = \max\{q_n, q_{n+1}\} = p_{n+1}.
Suppose on the contrary that SS is finite. Since q2=7<13=q3q_2 = 7 < 13 = q_3 and q3=13>7=q4q_3 = 13 > 7 = q_4, the set SS is non-empty. Since it is finite, we can consider its largest element, say mm.
Note that it is impossible that qm>qm+1>qm+2>q_m > q_{m+1} > q_{m+2} > \dots because all these numbers are positive integers, so there exists a kmk \ge m such that qk<qk+1q_k < q_{k+1} (recall that qkqk+1q_k \ne q_{k+1}).
Next observe that it is impossible to have qk<qk+1<qk+2<q_k < q_{k+1} < q_{k+2} < \dots, because
q(k+1)2=pk+1=max{qk,qk+1}=qk+1, q_{(k+1)^2} = p_{k+1} = \max\{q_k, q_{k+1}\} = q_{k+1},
so let us take the smallest lk+1l \ge k+1 such that ql>ql+1q_l > q_{l+1}. By the minimality of ll we have ql1<qlq_{l-1} < q_l, so lSl \in S. Since lk+1>kml \ge k+1 > k \ge m, this contradicts the maximality of mm, and hence SS is indeed infinite.

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 and solution reproduced as published; topic and difficulty added by this site.