Maths Olympiad Prep

Library / /9 of 9

Number theory Difficulty 8.3 Shortlist Prove it Singapore

Let a1,a2,a_1, a_2, \dots be a non-constant sequence of positive integers such that mnamanm-n \mid a_m - a_n for all distinct pairs of positive integers m,nm, n. Prove that there is an infinite set of primes such that each divides ana_n for some nn.

Solution

Let PP be the union of the sets of the prime divisors of ana_n, n1n \ge 1. Denote by vp(n)v_p(n) the highest power of pp that divides nn. Suppose on the contrary, that P|P| is finite. Let A={pPpk:kZ,k>vp(a1) pP}A = \{\prod_{p \in P} p^k : k \in \mathbb{Z}, k > v_p(a_1) \ \forall p \in P\}. Then A=|A| = \infty. Let tAt \in A. Assume that at+1a1a_{t+1} \ne a_1. Then there exists qPq \in P such that vq(at+1)vq(a1)v_q(a_{t+1}) \ne v_q(a_1). Thus vq(at+1a1)=min(vq(at+1),vq(a1))vq(a1)<vq(t)v_q(a_{t+1} - a_1) = \min(v_q(a_{t+1}), v_q(a_1)) \le v_q(a_1) < v_q(t). But this contradicts the fact that n(at+1a1)n \mid (a_{t+1} - a_1). Thus we must have at+1=a1a_{t+1} = a_1. Now for any positive integer mm, we have (t+1m)(at+1am)=(a1am)(t+1-m) \mid (a_{t+1} - a_m) = (a_1 - a_m). Since this is true for all tAt \in A and A=|A| = \infty, a1=ama_1 = a_m for all mm, a contradiction.

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