Maths Olympiad Prep

Library / /79 of 299

Number theory Difficulty 6.1 National Olympiad Prove it Iran

Let a1,a2,a3,a_1, a_2, a_3, \dots be an infinite sequence of distinct integers. Prove that there are infinitely many prime numbers like pp that distinct positive integers i,j,ki, j, k can be found such that paiajak1p \mid a_i a_j a_k - 1.

Solution

For the sake of contradiction, let p1,p2,,pnp_1, p_2, \dots, p_n be all the prime divisors of numbers in form of aiajak1a_i a_j a_k - 1. Moreover, let pp be the smallest of these primes, and M=max(a1,,an+1)M = \max(a_1, \dots, a_{n+1}) (mind that nn is fixed.). Let kk be a positive integer number satisfying pk>Mp^k > M. There are infinitely many aia_i's, therefore one satisfies the following properties:
1. i>n+2i > n + 2
2. ai>(p1p2pn)k+1a_i > (p_1 p_2 \dots p_n)^k + 1
It's easy to see for every jj, 1ln1 \le l \le n exists such that plk+1aiajan+21p_l^{k+1} \mid a_i a_j a_{n+2} - 1.
Therefore, due to the pigeonhole principle, there exists a pair 1m<tn+11 \le m < t \le n+1 such that for one ll, plk+1(aiaman+21,aiakan+21)p_l^{k+1} \mid (a_i a_m a_{n+2} - 1, a_i a_k a_{n+2} - 1).
    plk+1aiaman+21(aiakan+21)=aian+2(amak) \implies p_l^{k+1} \mid a_i a_m a_{n+2} - 1 - (a_i a_k a_{n+2} - 1) = a_i a_{n+2} (a_m - a_k)
    plk+1(amak) \implies p_l^{k+1} \mid (a_m - a_k)
    M>amakplk+1>pk>M \implies M > |a_m - a_k| \geq p_l^{k+1} > p^k > M
which is clearly a contradiction. Hence, the claim of the problem. ■

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.