Классификация — это разбиение множества на непересекающиеся подмножества (классы), объединение которых — всё множество. Множество A разбито на подмножества A₁, A₂, …, A_n, если
A_i ∩ A_j = ∅ (i ≠ j) и A₁ ∪ A₂ ∪ … ∪ A_n = A.
Целые числа удобно классифицировать по остаткам от деления на число m: остатков всего m — это 0, 1, …, m - 1. Например, при делении на 4 получаем четыре класса (k ∈ Z):
- Z₄(0) — числа вида 4k: {…; -8; -4; 0; 4; 8; …};
- Z₄(1) — числа вида 4k + 1: {…; -7; -3; 1; 5; …};
- Z₄(2) — числа вида 4k + 2;
- Z₄(3) — числа вида 4k + 3: {…; -5; -1; 3; 7; …}.
Классы не пересекаются (остаток единственный) и вместе дают всё Z (остаток всегда есть).
Зачем это нужно. Утверждение о бесконечном множестве целых чисел можно доказать перебором конечного числа классов.
Пример. Квадрат любого целого числа либо делится на 3, либо даёт при делении на 3 остаток 1. Числа бывают трёх видов: 3k, 3k + 1, 3k + 2.
- (3k)² = 3 · 3k² — делится на 3;
- (3k + 1)² = 9k² + 6k + 1 = 3(3k² + 2k) + 1 — остаток 1;
- (3k + 2)² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1 — остаток 1.