Maths Olympiad Prep

Library / /60 of 92

Number theory Difficulty 6.7 National olympiad Prove it Iran

a >> k are two positive integers and two strictly increasing sequences r1<r2<<rnr_1 < r_2 < \dots < r_n and s1<s2<<sns_1 < s_2 < \dots < s_n of positive integers have the following property,
(ar1+k)(ar2+k)(arn+k)=(as1+k)(as2+k)(asn+k). (a^{r_1} + k)(a^{r_2} + k)\dots(a^{r_n} + k) = (a^{s_1} + k)(a^{s_2} + k)\dots(a^{s_n} + k).
Prove that these two sequences are equals, which means for each 1in1 \le i \le n, ri=sir_i = s_i.

Solution

Without loss of generality, suppose s1r1+1s_1 \ge r_1 + 1. Let d=gcd(a,k)d = \gcd(a, k), a=da1a = da_1 and k=dk1k = dk_1. By using this equation and rewriting the problem's equality it is obtained that
i=1n(dria1ri+dk1)=i=1n(dsia1si+dk1)    i=1n(dri1a1ri+k1)=i=1n(dsi1a1si+k1) \begin{align*} \prod_{i=1}^{n} (d^{r_i} a_1^{r_i} + dk_1) &= \prod_{i=1}^{n} (d^{s_i} a_1^{s_i} + dk_1) \\ \implies \prod_{i=1}^{n} (d^{r_i-1} a_1^{r_i} + k_1) &= \prod_{i=1}^{n} (d^{s_i-1} a_1^{s_i} + k_1) \end{align*}
Now consider the latest two equations modulo dr1a1r1+1d^{r_1} a_1^{r_1+1}. Since the sequences are strongly ascending, it is deduced that
(dr11a1r1+k1)k1n1k1n(moddr1a1r1+1)    dr1a1r1+1(moddr11a1r1k1n1)da1(modk1n1) \begin{align*} & (d^{r_1-1} a_1^{r_1} + k_1) k_1^{n-1} \equiv k_1^n \pmod{d^{r_1} a_1^{r_1+1}} \\ \implies \begin{aligned} & d^{r_1} a_1^{r_1+1} \pmod{d^{r_1-1} a_1^{r_1} k_1^{n-1}} \\ & da_1 \pmod{k_1^{n-1}} \end{aligned} \end{align*}
So a1k1n1a_1 \mid k_1^{n-1}, but gcd(a1,k1)=1\gcd(a_1, k_1) = 1. Therefore a1=1a_1 = 1 that results in aka \mid k and it's in contradiction with a>ka > k. Therefore s1=r1s_1 = r_1. After removing s1s_1, r1r_1 from the assumption and continuing the same thing for r2r_2, s2s_2 we take r2=s2r_2 = s_2. So for each ii there is ri=sir_i = s_i. ■

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 and solution reproduced as published; topic and difficulty added by this site.