Number theoryDifficulty 8.3ShortlistProve itSingapore
Let a1,a2,… be a non-constant sequence of positive integers such that m−n∣am−an for all distinct pairs of positive integers m,n. Prove that there is an infinite set of primes such that each divides an for some n.
Solution
Let P be the union of the sets of the prime divisors of an, n≥1. Denote by vp(n) the highest power of p that divides n. Suppose on the contrary, that ∣P∣ is finite. Let A={∏p∈Ppk:k∈Z,k>vp(a1)∀p∈P}. Then ∣A∣=∞. Let t∈A. Assume that at+1=a1. Then there exists q∈P such that vq(at+1)=vq(a1). Thus vq(at+1−a1)=min(vq(at+1),vq(a1))≤vq(a1)<vq(t). But this contradicts the fact that n∣(at+1−a1). Thus we must have at+1=a1. Now for any positive integer m, we have (t+1−m)∣(at+1−am)=(a1−am). Since this is true for all t∈A and ∣A∣=∞, a1=am for all m, 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.