Lemma 5 Let be an integer greater than 1, and let be integers. Suppose that any two integers taken from are incongruent modulo , then form a complete residue system modulo .
Solution
To prove that for any integer modulo , it must be congruent to one of the following integers:
Let (where ) be an integer satisfying the condition
Then we have
where . Since (3) and the assumption that any two integers chosen from are not congruent modulo , it follows that any two integers chosen from are also not congruent modulo . Therefore, and differ only in order, meaning that form a complete residue system modulo .
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.