Maths Olympiad Prep

Library / /271 of 520

Number theory Difficulty 6.1 National olympiad Prove it

Lemma 8 If a1,a2,⋯ ,an,b1,b2,⋯ ,bna_{1}, a_{2}, \cdots, a_{n}, b_{1}, b_{2}, \cdots, b_{n} are all integers, and mm and nn are positive integers, then when
a1≡b1( mod m)a2≡b2( mod m)an≡bn( mod m)\begin{array}{r} a_{1} \equiv b_{1} \quad(\bmod m) \\ a_{2} \equiv b_{2} \quad(\bmod m) \\ a_{n} \equiv b_{n} \quad(\bmod m) \end{array}

all hold, we have
a1+a2+⋯+an≡b1+b2+⋯+bn( mod m)a_{1}+a_{2}+\cdots+a_{n} \equiv b_{1}+b_{2}+\cdots+b_{n} \quad(\bmod m)

Solution

Given a1≡b1( mod m),a2≡b2( mod m)a_{1} \equiv b_{1}(\bmod m), a_{2} \equiv b_{2}(\bmod m) and Lemma 4, we have
a1+a2≡b1+b2( mod m)a_{1}+a_{2} \equiv b_{1}+b_{2}(\bmod m)

Thus, the lemma holds when n=2n=2. Now suppose n⩾3n \geqslant 3. By a3≡b3( mod m)a_{3} \equiv b_{3}(\bmod m), equation (10), and Lemma 4, we have
a1+a2+a3≡b1+b2+b3( mod m)a_{1}+a_{2}+a_{3} \equiv b_{1}+b_{2}+b_{3}(\bmod m)

Thus, the lemma also holds when n=3n=3. If n⩾4n \geqslant 4, then by Lemma 4 and repeatedly using this method, we obtain
a1+a2+⋯+an≡b1+b2+⋯+bn( mod m)a_{1}+a_{2}+\cdots+a_{n} \equiv b_{1}+b_{2}+\cdots+b_{n}(\bmod m)

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.