Maths Olympiad Prep

Library / /32 of 69

Number theory Difficulty 5.9 AIME, harder Prove it Mongolia

Let m>2m > 2 be a natural number and if iji \neq j then aiaj(modm)a_i \neq a_j \pmod{m}. Prove that if (ai,m)=1(a_i, m) = 1, i=1,φ(m)i = 1, \varphi(m) then there exists the permutation b1,b2,...,bφ(m)b_1, b_2, ..., b_{\varphi(m)} of numbers a1,a2,...,aφ(m)a_1, a_2, ..., a_{\varphi(m)} such that a1b1+a2b2+...+aφ(m)bφ(m)a_1^{b_1} + a_2^{b_2} + ... + a_{\varphi(m)}^{b_{\varphi(m)}} is divisible by mm.

Solution

This is an extension of G.11.4.

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.