Number theoryDifficulty 6.7National OlympiadProve itIran
a > k are two positive integers and two strictly increasing sequences r1<r2<⋯<rn and s1<s2<⋯<sn of positive integers have the following property, (ar1+k)(ar2+k)…(arn+k)=(as1+k)(as2+k)…(asn+k). Prove that these two sequences are equals, which means for each 1≤i≤n, ri=si.
Solution
Without loss of generality, suppose s1≥r1+1. Let d=gcd(a,k), a=da1 and k=dk1. By using this equation and rewriting the problem's equality it is obtained that i=1∏n(dria1ri+dk1)⟹i=1∏n(dri−1a1ri+k1)=i=1∏n(dsia1si+dk1)=i=1∏n(dsi−1a1si+k1) Now consider the latest two equations modulo dr1a1r1+1. Since the sequences are strongly ascending, it is deduced that ⟹dr1a1r1+1(moddr1−1a1r1k1n−1)da1(modk1n−1)(dr1−1a1r1+k1)k1n−1≡k1n(moddr1a1r1+1) So a1∣k1n−1, but gcd(a1,k1)=1. Therefore a1=1 that results in a∣k and it's in contradiction with a>k. Therefore s1=r1. After removing s1, r1 from the assumption and continuing the same thing for r2, s2 we take r2=s2. So for each i there is ri=si. ■
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.