56. Разбейте множество целых чисел на классы по их остаткам от деления на: а) 2; б) 3; в) 5; г) 6. Изобразите с помощью диаграммы Эйлера — Венна получившиеся классы. Сколько классов у вас получилось? Сформулируйте гипотезу и докажите её.

При делении целого числа на n возможны остатки от 0 до n − 1. Обозначим класс чисел с остатком r через Cᵣ = {k ∈ ℤ : k ≡ r (mod n)}. Каждый целый элемент попадает ровно в один класс.

а) Деление на 2: C₀ = {…; −4; −2; 0; 2; 4; …}, C₁ = {…; −3; −1; 1; 3; 5; …}. Получилось 2 класса.

б) Деление на 3: C₀ = {…, −6; −3; 0; 3; 6; …}, C₁ = {…, −5; −2; 1; 4; 7; …}, C₂ = {…, −4; −1; 2; 5; 8; …}. Получилось 3 класса.

в) Деление на 5: классы остатков 0, 1, 2, 3 и 4. Например, C₀ = {…, −5; 0; 5; …}, C₁ = {…, −4; 1; 6; …}, C₂ = {…, −3; 2; 7; …}, C₃ = {…, −2; 3; 8; …}, C₄ = {…, −1; 4; 9; …}. Получилось 5 классов.

г) Деление на 6: классы остатков 0, 1, 2, 3, 4 и 5. Например, C₀ = {…, −6; 0; 6; …}, C₁ = {…, −5; 1; 7; …}, C₂ = {…, −4; 2; 8; …}, C₃ = {…, −3; 3; 9; …}, C₄ = {…, −2; 4; 10; …}, C₅ = {…, −1; 5; 11; …}. Получилось 6 классов.

Гипотеза: при делении множества целых чисел на n по остаткам получается n классов.

Доказательство: по теореме о делении с остатком для любого целого числа a существуют единственные целые q и r, такие что a = nq + r и 0 ≤ r < n. Поэтому каждый элемент принадлежит одному из классов C₀, …, Cₙ₋₁, а единственность остатка гарантирует, что классы не пересекаются. Все n остатков 0, 1, …, n − 1 возможны, значит, классов ровно n.

Ответ: для делителей 2, 3, 5 и 6 получаются соответственно 2, 3, 5 и 6 классов.