Maths Olympiad Prep

Library / /470 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Prove it

6. Suppose m>1m>1 is a positive integer, (a,m)=1(a, m)=1, and assume b1,b2,b_{1}, b_{2}, \cdots, bq(m)b_{q(m)} is a reduced residue system modulo mm, and abi=ri(modm)(0a b_{i}=r_{i}(\bmod m)(0 \leqslant ri<m,1iφ(m)r_{i}<m, 1 \leqslant i \leqslant \varphi(m) ), then
1m(r1+r2++rq(m))=12φ(m)\frac{1}{m}\left(r_{1}+r_{2}+\cdots+r_{q(m)}\right)=\frac{1}{2} \varphi(m)

Solution

6. Proof: Let 1<a2<<aφ(m)1<a_{2}<\cdots<a_{\varphi(m)} be all positive integers not greater than mm and coprime with mm. Since b1,b2,,bp(m)b_{1}, b_{2}, \cdots, b_{p(m)} is a reduced residue system modulo mm, and (a,m)=1(a, m)=1, by Lemma 13, we know that ab1,ab2,,abq(m)a b_{1}, a b_{2}, \cdots, a b_{q(m)} is also a reduced residue system modulo mm. And abiri(modm),0ri<ma b_{i} \equiv r_{i}(\bmod m), 0 \leqslant r_{i}<m, so r1,r2,,rq(m)r_{1}, r_{2}, \cdots, r_{q(m)} and 1,a2,,aq(m)1, a_{2}, \cdots, a_{q(m)} may only differ in order.
Therefore,
r1+r2++rq(m)=1+a2++aϕ(m)r_{1}+r_{2}+\cdots+r_{q(m)}=1+a_{2}+\cdots+a_{\phi(m)}

By the result of Question 5,
1+a2++aφ(m)=12mφ(m)1+a_{2}+\cdots+a_{\varphi(m)}=\frac{1}{2} m \cdot \varphi(m)

So,
1m(r1+r2++rφ(m))=1m(1+a2++aφ(m))=12φ(m)\begin{array}{l} \frac{1}{m}\left(r_{1}+r_{2}+\cdots+r_{\varphi(m)}\right) \\ \quad=\frac{1}{m}\left(1+a_{2}+\cdots+a_{\varphi(m)}\right)=\frac{1}{2} \varphi(m) \end{array}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.