Классы целых чисел по остаткам от деления

  • 5 мин чтения
  • Послушать — 4 мин
  • 11 карточек

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова · § 2. Развитие теории делимости

Классификация — это разбиение множества на непересекающиеся подмножества (классы), объединение которых — всё множество. Множество 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.

  1. (3k)² = 3 · 3k² — делится на 3;
  2. (3k + 1)² = 9k² + 6k + 1 = 3(3k² + 2k) + 1 — остаток 1;
  3. (3k + 2)² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1 — остаток 1.

Определение

1 / 11

Классификация

Классификация — разбиение множества A на подмножества (классы) A₁, A₂, …, A_n, которые не пересекаются и вместе дают всё A:

A_i ∩ A_j = ∅ (i ≠ j)

A₁ ∪ A₂ ∪ … ∪ A_n = A

Проверь себя

2 / 11

Это классификация?

Классы не пересекаются и вместе дают всё множество.

Какое разбиение множества Z — классификация?

чётные и нечётныекратные 2 и кратные 3положительные и отрицательные
Ответ и объяснение

Каждое целое число либо чётное, либо нечётное, и только одно из двух: классы не пересекаются и дают всё Z.

Правило

3 / 11

Классы по остаткам

При делении на натуральное m остатков всего m:

0, 1, …, m - 1

Поэтому Z делится на m классов. Z_m(r) — класс чисел с остатком r, это числа вида

mk + r, k ∈ Z

Пример

4 / 11

Классы по модулю 4

Z₄(0): 4k — …; -8; -4; 0; 4; 8; …

Z₄(1): 4k + 1 — …; -7; -3; 1; 5; …

Z₄(2): 4k + 2 — …; -6; -2; 2; 6; …

Z₄(3): 4k + 3 — …; -5; -1; 3; 7; …

Свойство

5 / 11

Почему это классификация

  • Классы не пересекаются: остаток у числа единственный.
  • Классы дают всё Z: остаток есть у каждого целого числа.

Z₄(0) ∪ Z₄(1) ∪ Z₄(2) ∪ Z₄(3) = Z

Проверь себя

6 / 11

Найди класс

Число a лежит в Z_m(r), если a = mk + r, 0 ≤ r < m.

В каком классе лежит число -7?

Z₄(1)Z₄(3)ни в каком
Ответ и объяснение

-7 = 4 · (-2) + 1, остаток 1, поэтому -7 ∈ Z₄(1).

Правило

7 / 11

Зачем нужны классы

Утверждение о бесконечном множестве целых чисел можно доказать перебором конечного числа классов.

Делим на 3 — разбираем три вида чисел:

3k, 3k + 1, 3k + 2

Разбор

8 / 11

Квадрат при делении на 3

Докажем: квадрат целого числа либо делится на 3, либо даёт остаток 1.

  1. Случай 1

    (3k)² = 3 · 3k² — делится на 3.

  2. Случай 2

    (3k + 1)² = 9k² + 6k + 1 = 3(3k² + 2k) + 1 — остаток 1.

  3. Случай 3

    (3k + 2)² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1 — остаток 1.

  4. Ответ

    Других классов нет: остаток квадрата — 0 или 1, остатка 2 не бывает.

Частая ошибка

9 / 11

Пропущенный класс

«n(n + 1) делится на 3»: при n = 3k и n = 3k + 2 это верно.

Но n = 1 из класса 3k + 1: 1 · 2 = 2 — не делится.

Доказательство перебором — это все m классов, без пропусков.

Проверь себя

10 / 11

Сколько случаев?

Классов столько же, сколько остатков: 0, 1, …, m - 1.

Сколько случаев разобрать, чтобы доказать утверждение об остатках при делении на 5?

452
Ответ и объяснение

Остатки 0, 1, 2, 3, 4 — пять классов: 5k, 5k + 1, …, 5k + 4.

Главное

11 / 11

Главное

  • Классификация: классы не пересекаются и вместе дают всё множество.
  • По остаткам от деления на m — m классов Z_m(0), …, Z_m(m - 1).
  • Z_m(r) — числа вида mk + r, k ∈ Z.
  • Утверждение о всех целых числах доказывают перебором всех классов.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест