Maths Olympiad Prep

Library / /236 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Theorem 3 (i) Among any given m+1m+1 integers, there must be two numbers that are congruent modulo mm;
(ii) There exist mm numbers that are pairwise incongruent modulo mm.

Solution

Proof: Since there are mm congruence classes modulo mm given by (1), there must be two numbers among the m+1m+1 numbers that belong to the same congruence class modulo mm. These two numbers are congruent modulo mm. This proves (i). By selecting a number xrx_{r} as a representative in each congruence class rmodm(0r<m)r \bmod m (0 \leqslant r < m), we obtain mm numbers x0,x1,,xm1x_{0}, x_{1}, \cdots, x_{m-1} that are pairwise incongruent modulo mm. This proves (ii).

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.