Maths Olympiad Prep

Library / /238 of 397

Algebra Difficulty 6.1 National Olympiad Prove it Taiwan

Let c1c \ge 1 be an integer. Define a sequence of positive integers by a1=ca_1 = c and
an+1=an34c×an2+5c2×an+c a_{n+1} = a_n^3 - 4c \times a_n^2 + 5c^2 \times a_n + c
for all n1n \ge 1. Prove that for each integer n2n \ge 2 there exists a prime number pp dividing ana_n but none of the numbers a1,,an1a_1, \dots, a_{n-1}.

Solution

Let x0=0x_0 = 0 and xn=an/cx_n = a_n/c. It is easy to see that x1=1x_1 = 1, x2=2c2+1x_2 = 2c^2 + 1, and
xn+1=c2(xn34xn2+5xn)+1.(1) x_{n+1} = c^2(x_n^3 - 4x_n^2 + 5x_n) + 1. \quad (1)
It is clear that xnx_n is an increasing sequence. To prove the original statement, it suffices to prove the corresponding statement for the sequence xnx_n.

We first prove three lemmas:

(1) Lemma 1: If i=j(modm)i = j \pmod m, then xi=xj(modxm)x_i = x_j \pmod{x_m}.
This lemma is equivalent to xi+m=xi(modxm)x_{i+m} = x_i \pmod{x_m}. Fix mm; this is clearly true for i=0i = 0. If xi+m=xi(modxm)x_{i+m} = x_i \pmod{x_m}, then we have
xi+m+1=c2(xi+m34xi+m2+5xi+m)+1=c2(xi34xi2+5xi)+1=xi+1(modxm) \begin{aligned} x_{i+m+1} &= c^2(x_{i+m}^3 - 4x_{i+m}^2 + 5x_{i+m}) + 1 = c^2(x_i^3 - 4x_i^2 + 5x_i) + 1 \\ &= x_{i+1} \pmod{x_m} \end{aligned}
Hence by mathematical induction, the proof is complete.

(2) Lemma 2: If i,j2i, j \ge 2 and i=j(modm)i = j \pmod m, then xi=xj(modxm2)x_i = x_j \pmod{x_m^2}.
This lemma is equivalent to xi+m=xi(modxm2)x_{i+m} = x_i \pmod{x_m^2}. Fix mm, and note that this holds for i=2i = 2. Proceeding by induction in a manner similar to the previous item yields the result.

(3) Lemma 3: For all n2n \ge 2, we have xn>x1x2xn2x_n > x_1x_2\cdots x_{n-2}.
Note that the lemma is clearly true for n=2,3n=2,3. For n>3n>3, by monotonicity we know xn>7x_n > 7, so
xn+1>xn34xn2+5xn>7xn24xn2>xn2>xnxn1, x_{n+1} > x_n^3 - 4x_n^2 + 5x_n > 7x_n^2 - 4x_n^2 > x_n^2 > x_n x_{n-1},
hence by mathematical induction, the proof is complete.

Returning to the original problem. By Lemma 3, there exists a prime pp and a positive integer tt such that ptp^t divides xnx_n but does not divide x1x2xn2x_1x_2\cdots x_{n-2}. We will now show that this pp is the pp required by the problem.
If not, let kk be the smallest positive integer satisfying pxkp|x_k. By Eq. (1), xn1x_{n-1} and xnx_n are coprime, and x1=1x_1 = 1, so we have 2kn22 \le k \le n-2. Write n=qk+rn = qk+r, where q0q \ge 0 and 0r<k0 \le r < k. By Lemma 1, we know that xnx_n and xrx_r are congruent modulo xkx_k, so pxrp|x_r; but by the minimality of kk, this means r=0r=0, and hence knk|n.
Now, by Lemma 2, we have that xnx_n and xkx_k are congruent modulo xk2x_k^2. Let α1\alpha \ge 1 be the maximum value such that pαxkp^\alpha|x_k. By the argument above, we know pα+1xnp^{\alpha+1}|x_n, while p2αxk2p^{2\alpha}|x_k^2. But this forces pα+1xkp^{\alpha+1}|x_k, contradicting the maximality of α\alpha. Contradiction! 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.