Maths Olympiad Prep

Library / /318 of 397

Number theory Difficulty 6.7 National Olympiad Prove it Taiwan

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.

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.
It is easy to see that pn=qn2p_n = q_{n^2}. Also, 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)
we know that for all n2n \ge 2, pn=max{qn,qn1}p_n = \max\{q_n, q_{n-1}\}. Also since n2n+1n^2 - n + 1 is odd,
gcd((n1)2+(n1)+1,n2+n+1)=gcd(2n,n2n+1)=gcd(n,n2n+1)=1. \text{gcd}((n-1)^2+(n-1)+1, n^2+n+1) = \text{gcd}(2n, n^2-n+1) = \text{gcd}(n, n^2-n+1) = 1.
Hence qnqn1q_n \neq q_{n-1}.
Returning to the original problem. Consider the set
S:={nZ2qn>qn1,qn>qn+1}. S := \{n \in \mathbb{Z}_{\ge 2} \mid q_n > q_{n-1}, q_n > q_{n+1}\}.
Note that for all nSn \in S, we have
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},
so the original problem is equivalent to proving that SS has infinitely many elements. Here note that q2=7<13=q3q_2 = 7 < 13 = q_3 and q3=13>7=q4q_3 = 13 > 7 = q_4, so SS is nonempty.
We now argue by contradiction: suppose SS has a largest element mm. Since all qiq_i are positive integers, it is impossible that qm>qm+1>qm+2>q_m > q_{m+1} > q_{m+2} > \dots, so there must exist kmk \ge m such that qk<qk+1q_k < q_{k+1} (note that it has already been shown that qkqk+1q_k \ne q_{k+1}). Also, note that since q(k+1)2=pk+1=max{qk,qk+1}=qk+1q_{(k+1)^2} = p_{k+1} = \max\{q_k, q_{k+1}\} = q_{k+1}, it is likewise impossible that qk<qk+1<q_k < q_{k+1} < \dots, so there must exist a smallest lk+1l \ge k+1 such that ql>ql+1q_l > q_{l+1}.

But since ll is smallest, we must have ql>ql1q_l > q_{l-1}, and hence lSl \in S, contradicting the assumption that mm is the largest element. Contradiction! Therefore SS has infinitely many elements. This completes the proof.

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 zh; metadata (topic, difficulty) added by this project.