Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /70 of 270

Iranian Mathematical Olympiad

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 p∣aiajak−1p \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 aiajak−1a_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>(p1p2…pn)k+1a_i > (p_1 p_2 \dots p_n)^k + 1
It's easy to see for every jj, 1≤l≤n1 \le l \le n exists such that plk+1∣aiajan+2−1p_l^{k+1} \mid a_i a_j a_{n+2} - 1.
Therefore, due to the pigeonhole principle, there exists a pair 1≤m<t≤n+11 \le m < t \le n+1 such that for one ll, plk+1∣(aiaman+2−1,aiakan+2−1)p_l^{k+1} \mid (a_i a_m a_{n+2} - 1, a_i a_k a_{n+2} - 1).
  ⟹  plk+1∣aiaman+2−1−(aiakan+2−1)=aian+2(am−ak) \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∣(am−ak) \implies p_l^{k+1} \mid (a_m - a_k)
  ⟹  M>∣am−ak∣≥plk+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.