Maths Olympiad Prep

Library / /459 of 520

Number theory Difficulty 7.0 National olympiad Prove it

Lemma 5 Let mm be an integer greater than 1, and let a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} be mm integers. Suppose that any two integers taken from a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} are incongruent modulo mm, then a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} form a complete residue system modulo mm.

Solution

To prove that for any integer modulo mm, it must be congruent to one of the following mm integers:
0,1,,m10,1, \cdots, m-1

Let rir_{i} (where i=1,2,,mi=1,2, \cdots, m) be an integer satisfying the condition
airi(modm),0rim1,a_{i} \equiv r_{i}(\bmod m), \quad 0 \leqslant r_{i} \leqslant m-1,

Then we have
a1r1(modm),a2r2(modm),,amrm(modm).a_{1} \equiv r_{1}(\bmod m), a_{2} \equiv r_{2}(\bmod m), \cdots, a_{m} \equiv r_{m}(\bmod m) .
where 0r1m1,0r2m1,,0rmm10 \leqslant r_{1} \leqslant m-1,0 \leqslant r_{2} \leqslant m-1, \cdots, 0 \leqslant r_{m} \leqslant m-1. Since (3) and the assumption that any two integers chosen from a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} are not congruent modulo mm, it follows that any two integers chosen from r1,r2,,rmr_{1}, r_{2}, \cdots, r_{m} are also not congruent modulo mm. Therefore, r1,r2,,rmr_{1}, r_{2}, \cdots, r_{m} and 0,1,,m10,1, \cdots, m-1 differ only in order, meaning that a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} form a complete residue system modulo mm.

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.