Основы теории целых чисел

Дискретная математика для ФРТ

Содержание.

Основы теории целых чисел - 3 лекции,

комбинаторика - 2 лекции,

понятие о графах (дополнительный материал)-1 лекция,

булевы функции - 3 лекции.

И материалы для семинаров.

Примечание: часть материала носит ознакомительный характер! Например, если теории для некоторой задачи не было в лекциях – значит, эта задача не входит в семинары, домашние задания и экзамен, а её условие даётся как дополнительный материал для самых любознательных. Конечно, готов кратко рассказать про решения таких задач, если спросите.

Основы теории целых чисел

1. Деление с остатком

Определение

a, b Î Z, b > 0.

Поделить a на b с остатком – значит найти такие числа p и q, что a = bq + r, при этом 0≤ r<b.

Примеры:

1. (Показать на доске) 25 = 4×6 + 1

2. (Решить самостоятельно) -25 = -5×6 + 5

Докажем единственность деления с остатком.

В самом деле, если

Тогда

Если левая часть не равна 0, то её модуль не меньше b, поскольку умножаем b на ненулевое целое число. С другой стороны, оба остатка меньше b, поэтому модуль разности в правой части меньше b.

Противоречие!

Поэтому левая часть равна 0, и два представления совпали.

Пример.

Найдутся два целых числа, составленных из одних единиц, которые дают одинаковый остаток при делении на 37.

Решение

Возьмём 38 чисел, составленных из одних единиц. Поскольку остатков от деления на 37 всего 37, то хотя бы у двух чисел совпадут остатки.

Задачи.

1. Найти остаток от деления 2²⁰⁰⁰ на 3.

Решение

Раскрыв скобки, получим много слагаемых, кратных 3, и одно слагаемое, равное 1. Поэтому остаток равен 1.

Ответ: 1.

2. а) доказать, что найдутся два числа, составленные из единиц, разность которых кратна 5007.

б) доказать, что найдётся одно число, составленное из единиц и кратное 5007.

Решение.

а) Возьмём 5008 чисел, составленных из одних единиц. Поскольку остатков от деления на 5007 всего 5007, то хотя бы у двух чисел совпадут остатки, следовательно, их разность будет кратна 5007.

б) Рассмотрим эту разность. В начале её некоторое количество единиц, затем одни нули.

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

Поэтому число из единиц делится на 5007.