Maths Olympiad Prep

Library / /288 of 520

Number theory Difficulty 6.2 National olympiad Prove it

Theorem 2 For a given modulus mm, there are exactly mm distinct congruence classes modulo mm, which are
0 mod m,1 mod m,⋯ ,(m−1) mod m0 \bmod m, 1 \bmod m, \cdots,(m-1) \bmod m

We denote the set composed of these congruence classes as
Z/mZ=Zm={j mod m:0⩽j⩽m−1}\boldsymbol{Z} / m \boldsymbol{Z}=\boldsymbol{Z}_{m}=\{j \bmod m: 0 \leqslant j \leqslant m-1\}

Solution

Proof: By Theorem 1 (ii), we know that these are mm pairwise distinct congruence classes. For each integer aa, by Theorem 1 in Chapter 1 § 3, we know that
a=qm+r,0⩽r<m.a=q m+r, \quad 0 \leqslant r<m.

Therefore, by Theorem 1 (i), we know that a∈j mod ma \in j \bmod m, i.e., aa must belong to one of the congruence classes in (1). Proof completed.

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.