Арифметика остатков

«Остатки» играют в нашей жизни большую роль. Мы встречаемся с ними буквально на каждом шагу. Приведем несколько примеров.

1. Говоря «30 год», мы указываем век, так как 30 год может быть и в XX в., и в XIX в., и в XVIII в.; 30 – это остаток от деления полного числа лет на 100.

2. Вы взглянули на часы, которые показывают 8 ч. Но это может быть и 8 ч и 20 ч, так как часы показывают остаток от деления полного времени на 12.

3. Счетчик показывает 0314 кВт • ч. Это может быть и 0314 кВт•ч и 10314 кВт•ч и 20314 кВт•ч, так как счетчик показывает остаток от деления израсходованного числа киловатт-часов на 10 000.

Таких примеров можно привести множество. Иногда найти остаток совсем нетрудно. А как, например, найти остаток от деления числа 1996•1997•1998•1999•2000•2001 на 7? Перемножить и разделить? Представьте себе проблемы, с которыми придется столкнуться.

Эту задачу мы решим немного позже и почти устно, познакомившись с теорией «Арифметика остатков» или «Арифметика сравнений».

Определение. Делитель в теории чисел называется модулем, а числа, дающие при делении на модуль одинаковые остатки, называются сравнимыми по модулю.

Например, 8 = 7•1 + 1, 15 = 7•2 + 1. Числа 8 и 15 при делении на 7 дают одинаковые остатки, равные 1, следовательно, 8 и 15 сравнимы по модулю 7. Это записывают так: 15 є 8 (mod 7), аналогично 22 є 15 (mod 7).

В качестве модуля можно взять любое натуральное число. Например, 20є5 (mod 3), 16є4 (mod 4), 37є7 (mod 10). 

Вообще aєb (mod m), если a = mc + r, b = mc + r, где 0 m r < m.

Заметим, что если 15є8 (mod 7), то (15 – 8) 7. Здесь значок обозначает «кратно» или «делится на...».

Например, если 11є5 (mod 3), то (11 – 5) 3.

Вообще, если aєb (mod m), то a – b = (mc + r) – (md + r) = m(c – d) m.

Мы доказали, что если числа сравнимы по модулю m, то их разность делится на модуль m.

Верно и обратное утверждение: если разность двух чисел делится на m, по эти числа сравнимы по модулю m.

В самом деле, если бы эти числа не были сравнимы по модулю m, то давали бы разные остатки при делении на m, но тогда их разность не могла бы делиться на m. Это свойство сравнений мы будем использовать, например, для доказательства сравнимости чисел:

10є3 (mod 7), так как 10 – 3 = 7 7;
21є13 (mod 4), так как 21 – 13 = 8 4.

Из этого свойства вытекает способ получения сравнимых по модулю чисел: прибавить или вычесть из данного числа кратные модулю числа.

Например, 11є8є5є2 (mod 3). Причем, натуральное число, меньшее модуля и сравнимое с другими числами, служит остатком от деления этих чисел на модуль. В рассмотренном примере остаток равен 2.

Приведем еще один пример: 23є19є15є11є7є3 (mod 4).

Здесь число 3 – остаток от деления указанных чисел на 4.

 Действия над сравнениями

1. Заметим, что

    10є3(mod 7)
+ 12є5(mod 7)
______________
   22є8(mod 7),                              так как 22 – 8 = 14 7.

Вообще,

   aєb(mod m), т. е. (a – b) m
+ cєd(mod m), т. е. (c – d) m
__________________________
a + cєb + d(mod m),                           так как (a + c) – (b + d) = (a – b) + (c – d) m.

Мы доказали, что сравнения по одному и тому же модулю можно складывать.

Задача 1. Найдите остаток от деления суммы  1995 + 1996 + 1997 + 1998 + 1999 на 7.

Решение.

Так как 1995 = 7•285, то 1995є0 (mod 7), то 1995 + 1996 + 1997 + 1998 + 1999є0 + 1 + 2 + 3 + 4 = 10є3 (mod 7).

Остаток равен 3.

Задача 2. Найдите остаток от деления:вашего года рождения, например 1988 г., на 11.

Имеем 1988 = 11•80 + 8, значит, 1998є8 (mod 11); года рождения вашей мамы, например 1953 г., на 11. Получаем

1953 = 11•177 + 6, значит 1953є6 (mod 11);

суммы годов рождений, вашего и маминого, на 11. Находим 1988 + 1953є8 + 6 = 14є3 (mod 11).

2. Заметим, что

   10є3(mod 7)
• 12є5(mod 7)
______________
120є 8(mod 7),               так как 120 – 15 = 105 7.

Сравнения по одному и тому же модулю, можно перемножать, следовательно, и возводить в натуральную степень. (Это утверждение для шестиклассников можно не доказывать, только показать на примерах. Для старшеклассников его следует доказать.)

Итак, пусть aєb (mod m) и cєd (mod m).

Докажем, что acєbd     (mod m).

Доказательство. Рассмотрим разность

ac – bd = ac – bc + bc – bd = c(a – b) + b(c – d) m,    так как (a – b) m и (c – d) m.

Следовательно, acєbd (mod m), что и требовалось доказать.

Задача 3. Найдите остаток от деления на 7 произведения чисел 1995•1996•1997•1998•1999.

Решение. Так как 1995є0 (mod 7), то 1995•1996•1997•1998•1999 Ю 0•1•2•3•4 = 0 (mod 7).

Таким образом, остаток равен 0.

Задача 4. Найдите остаток от деления на 7 числа 1996•1997•1998•1999•2000•2001.

Решение. Имеем   1996•1997•1998•1999•2000•2001є 1•2•3•4•5•6 = 720є20є6 (mod 7).

Остаток равен 7.

Часто встречаются произведения вида 1•2•3•4, 1•2•3•4•5, 1•2•3•4•5•6 и т д.

Их обозначают 1•2•3•4 = 4!, 1•2•3•4•5 = 5!. Читают: 4-факториал, 5-факториал и т. д. Вообще, 1•2•3•...•n = n! (n-факториал).

(Найдите самостоятельно значения выражений 5!, 7!.)

Заметим, что остаток от деления числа на 10 есть последняя цифра этого числа.

Пример. 21є1 (mod 10), 134є4 (mod 10).

Для решения ряда задач на поиски последней цифры числа полезна следующая «таблица», которую следует вывести вместе с учащимися:

1kє1 (mod 10) 42kє6 (mod 10) 24kє6 (mod 10) 24k+1є2 (mod 10) 24k+2є4 (mod 10) 24k+3є8 (mod 10)

5kє5 (mod 10) 42k+1є4 (mod 10) 34kє1 (mod 10) 34k+1є3 (mod 10) 34k+2є9 (mod 10) 34k+3є7 (mod 10)

6kє 6 (mod 10) 92kє 1 (mod 10) 74kє1 (mod 10) 74k+1є 7 (mod 10) 74k+2є 9 (mod 10) 74k+3є3 (mod 10)

92k+1є9 (mod 10) 84kє6 (mod 10) 84k+1є8 (mod 10) 84k+2є4 (mod 10) 84k+3є2 (mod 10)

  Вывод этих сравнений можно показать на примере:

7є7 (mod 10);
7² = 49є9 (mod 10);
7³ = 7²•7є9•7 = 63є3 (mod 10);
7⁴ = 7³•7є3•7 = 21є1 (mod 10).

Далее остатки будут повторяться: остаток 1 имеют все степени числа 7, показатель которых кратен 4; остаток 7 – все степени 7, показатель которых при делении на 4 дает остаток 1; остаток 9 – все степени 7, показатель которых при делении на 4 дает остаток 2; остаток 3 – все степени 7, показатель которых при делении на 4 дает остаток 3.

Задача 5. Какова последняя цифра числа 137100?

Решение. Имеем:  137є7 (mod 10), 137¹⁰⁰є 7¹⁰⁰ = 7^25•4є1 (mod 10).

Последняя цифра равна 1.

Задача 6. Найдите последнюю цифру каждого из следующих чисел: 7⁷, 77⁷⁷, 2¹⁰⁰, 3¹⁹⁹⁹, 19¹⁰⁰, 1999¹⁹⁹⁹.

Решение. Получаем:  

7⁷ = 7^4•1+3є3 (mod 10),
77⁷⁷є7⁷⁷ = 7^4•19+1є7 (mod 10),
2¹⁰⁰ = 2^4•25є6 (mod 10),
3¹⁹⁹⁹ = 3^4•499+3є7 (mod 10),
19¹⁰⁰ є9¹⁰⁰є1 (mod 10).
1999¹⁹⁹⁹є9¹⁹⁹⁹є9 (mod 10).

Последняя цифра соответственно 3, 7, 6, 7, 1, 9.

Задача 7.

а) Найдите остаток от деления на 3 числа 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹.
б) Найдите последнюю цифру числа 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹.

Решение.

а) 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹є0¹⁹⁹⁸ + 1¹⁹⁹⁹ = 0 + 1є1 (mod 3).   Остаток равен 1.
б) 1998¹⁹⁹⁸ + 1999¹⁹⁹⁹є8¹⁹⁹⁸ + 9¹⁹⁹⁹ = 8^4•499+2 + 9^2•999+1є4 + 9 = 13є3 (mod 10).

Последняя цифра равна 3.

Рассмотрим еще ряд задач, решаемых арифметикой сравнений.

Задача 8. Докажите, что n³ – n кратно 6 для любого натурального числа n.

Решение. Истинность утверждения для некоторых n еще не служит доказательством. Рассмотрим для ясности несколько частных случаев. Например,

при n = 1         1³ – 1 = 0 6,
при n = 2        2³ – 2 = 8 – 2 = 6 6,
при n = 10      10³ – 10 = 1000 – 10 = 9906.

Теперь докажем утверждение задачи. При делении на число 6 возможны следующие остатки: 0, 1, 2, 3, 4, 5.

Тогда если

nє0 (mod 6), то  n³ – n = 0³ – 0 = 0 (mod 6),
nє1 (mod 6), то  n³ – n = 1³ – 1 = 0 (mod 6),
nє2 (mod 6), то  n³ – n = 2³ – 2 = 6є0 (mod 6),
nє3 (mod 6), то  n³ – n = 3³ – 3 = 24є0 (mod 6),
nє4 (mod 6), то  n³ – n = 4³ – 4 = 60є0 (mod 6),
nє5 (mod 6), то  n³ – n = 5³ – 5 = 120є0 (mod 6).

Полный перебор показал, что n³ – n кратно 6 для любого натурального числа n.

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

Задача 9. Укажите все возможные остатки при делении чисел вида n² + 3n на 7.

Решение. При делении на 7 возможны остатки 0, 1, 2, 3, 4, 5, 6. Тогда:

nє0 (mod 7),   n² + 3n = 0² + 3•0 = 0 (mod 7),
nє1 (mod 7),   n² + 3n = 1² + 3•1 = 4 (mod 7),
nє2 (mod 7),   n² + 3n = 2² + 3•2 = 10є3 (mod 7),
nє3 (mod 7),   n² + 3n = 3² + 3•3 = 18є4 (mod 7),
nє4 (mod 7),   n² + 3n = 4² + 3•4 = 16 + 12 = 28є0 (mod 7),
nє5 (mod 7),   n² + 3n = 5² + 3•5 = 25 + 15 = 40є5 (mod 7),
nє6 (mod 7),   n2 + 3n = 6² + 3•6 = 36 + 18 = 54є5 (mod 7).

Возможные остатки: 0, 3, 4, 5.

В качестве самостоятельной тренировочной или домашней работы следует предложить упражнения следующего типа:

1. Найдите последнюю цифру числа:

а) 11⁶ + 14⁶ + 16⁶;
б) 11•13•15•17•19.

2. Найдите остаток от деления на 4 числа:

а) 11⁶ + 14⁶ + 16⁶;
б) 11•13•15•17•19.

3. Докажите, что n³ + 2n кратно 3 для любого натурального значения n.

Решения.  

1.

а) 11⁶ + 14⁶ + 16⁶є1⁶ + 4⁶ + 6⁶є1 + 6 + 6 = 13є3 (mod 10);
б) 11•13•15•17•19 = 1•3•5•7•9є5 (mod 10).

2.

а) 11⁶ + 14⁶ + 16⁶є3⁶ + 2⁶ + 0⁶ =3⁴•3² + 64є1•9 + 0 = 9є1 (mod 4);
б) 11•13•15•17•19є3•1•3•1•3 = 27є3 (mod 4).

3.

nє0 (mod 3), n³ + 2nє0³ + 2•0є0 (mod 3),
nє1 (mod 3), n³ + 2nє1³ + 2•1 = 3є0 (mod 3),
nє2 (mod 3), n³ + 2nє2³ + 2•2 = 8 + 4 = 12є0 (mod 3).

Следовательно, n³ + 2n кратно 3 для любого натурального значения n.

Проверку усвоения материала рекомендуется провести следующим образом. Ученики выполняют задания и каждую цифру ответа заменяют буквой, используя таблицу шифра. Если ученик справится с заданием, то в четвертом столбце заполненной таблицы он прочитает слово «верно».

Таблица шифра

Вариант 1 Вариант 2

Укажите последнюю цифру числа:

Найдите остаток от деления:

Ученики сдают свои листки с ответами и, пока учитель просматривает их, они выполняют следующее задание.

Вариант 1

Найдите остаток от деления на 9 числа 1998¹⁹⁹⁹ + 1999¹⁹⁹⁸.

Делится ли это число на 3? Если нет, то какой остаток дает при делении на 3?

Вариант 2

Найдите последнюю цифру числа   1998¹⁹⁹⁹ + 1999¹⁹⁹⁸.

Делится ли это число на 5? на 2?

Несколько задач, объединенных общей идеей

1. Докажите, что n(n + 1) 2.

Способ I.

nє0 (mod 2), n(n + 1)є0(0 + 1) = 0 (mod 2);
nє1 (mod 2), n(n + 1)є1(1 + 1) = 2є2 (mod 2).

Способ II. Из двух последовательных чисел n и (n + 1) одно всегда четно, следовательно, их произведение n(n+1) четно.

2. Докажите, что n(n + 1)(n + 2) 3.

Двое учащихся по очереди проговаривают доказательство показанными выше способами. Учитель предлагает классу составить аналогичные задачи. Ученики формулируют задачи.

Докажите, что

n(n + 1)(n + 2)(n + 3) 4;
n(n + 1)(n + 2)(n + 3)(n + 4) 5;
n(n + 1)(n + 2)(n + 3)(n + 4)(n + 5) 6.

Затем обобщают задачу: n(n + 1)(n + 2)...(n + m) (m + 1).

Вернемся к выражению n(n + 1)(n + 2). Здесь n(n + 1) 2 и n(n + 1)(n + 2) 3,

2 и 3 – взаимно простые числа, значит, n(n + 1)(n + 2) 1•2•3 = 3! = 6.

Докажем, что n(n + 1)(n + 2)(n + 3) 4! = 24.

Способ I. Нужно рассмотреть 24 случая сравнений, так как при делении числа на 24 возможны следующие остатки: 0, 1, 2, ..., 24. Их количество можно уменьшить, так как 24 = 3•8, а 3 и 8 – взаимно простые числа. Таким образом, можно рассмотреть только 3 + 8 = 11 сравнений, три из которых – сравнения по модулю 3 и восемь – по модулю 8.

Способ II. Выше было доказано, что n(n + 1)(n + 2) 3. Среди четырех последовательных чисел n, n + 1, n + 2, n + 3 два четных. Докажем, что если одно из них делится на 2, то другое делится на 4. Эти числа имеют вид 2k и 2(k + 1). Из чисел k и k + 1 одно четное вида 2m, тогда 2•2m = 4m 4. Таким образом, n(n + 1)(n + 2)(n + 3) 1•2•3•4 = 4! = 24.

Теперь можно доказать и следующие утверждения:

n(n + 1)(n + 2)(n + 4) 5!;
n(n + 1)(n + 2)(n + 3)(n + 4)(n + 5) 6!.

Задание на дом

1. Найдите последнюю цифру суммы:

а) 1² + 2² + ... + 10²;      
б) 1² + 2² + ... + 100².

2. Докажите, что:

а) n² + n2;
б) n² – n2.

3. Докажите, что квадрат нечетного числа при делении на 8 дает остаток 1.

4. Докажите, что сумма квадратов двух последовательных натуральных чисел при решении на 4 дает остаток 1.

Решения.

 1.

а) 1² + 2² + 3² + 4² + 5² + 6² + 7² + 8² + 9² + 10² = 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100є
є1 + 4 +  9 + 6 + 5 + 6 + 9 + 4 + 1 + 0 = 45є5 (mod 10). Последняя цифра 5.
б) 1² + 2² + .. + 100²є5•10 = 50є100 (mod 10). Последняя цифра 0.

2.

а) nє0 (mod 2), n² + nє0² + 0 = (mod 2), nє1 (mod 2), n² + nє1² + 1 = 2є0 (mod 2).
б) Доказывается аналогично.

3. Докажем, что (2n + 1)²є1 (mod 8). Имеем: 

nє0 (mod 8), (2•0 + 1)² = 1є1 (mod 8),
nє1 (mod 8), (2•1 + 1)² = 9є1 (mod 8),
nє2 (mod 8), (2•2 + 1)² = 25є1 (mod 8),
nє3 (mod 8), (2•3 + 1)² = 49є1 (mod 8),
nє4 (mod 8), (2•4 + 1)² = 81є1 (mod 8),
nє5 (mod 8), (2•5 + 1)² = 121є1 (mod 8),
nє6 (mod 8), (2•6 + 1)² = 169є1 (mod 8),
nє7 (mod 8), (2•7 + 1)² = 225є1 (mod 8).

4. Доказывается аналогично.

Литература

1. Генкин С.А., Итенберг И.В., Фомин Д.В. Математический кружок. Первый год. – С.-Петербург, 1992.
2. Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике в 6–8 классах. – М., Просвещение, 1997.
3. Иванов С.Г. Нестандартные задачи по алгебре, 5–7 классы. – С.-Петербург, Институт продуктивного обучения, центр профессионального обновления «Информатизация образования», 1999.