Теория делимости

Модуль 1. Элементы теории чисел

Глава 1.1. Целые числа

Теория делимости

Целыми называются числа..., -3, -2, -1, 0, 1, 2, 3,..., т.е. натуральные числа 1, 2, 3, 4,..., а также нуль и отрицательные числа -1, -2, -3, -4,.... Множество всех целых чисел обозначается через Z (от немецкого слова Zahl – число).

Сумма, разность и произведение двух целых чисел – также целые числа. Если для трех целых чисел a, b и с выполнено равенство то говорят: а делится на b или b делит а и применяют соответственно обозначения При этом а называют кратным числа b, а b – делителем числа а.

Свойства делимости целых чисел:

1) а делится на а (рефлексивность);

2) если а делится на b, b делится на а, то или - b;

3) если а делится на b, b делится на с, то а делится на с (транзитивность);

4) если а делится на d, b делится на d, то и с делится на d;

5) если ad делится на bd, то а делится на b.

Доказательство свойства 1:

Доказательство свойства 2: Отсюда т.е. или -1.

Доказательство свойства 3: Отсюда

Доказательство свойства 4: Отсюда

Доказательство свойства 5: Отсюда

Теорема (о делении с остатком): Для любых двух целых чисел а и b существует и притом единственная пара чисел q и r, для которых

.

Доказательство теоремы существования. Расположим на числовой оси числа..., -2 b, - b, 0, b, 2 b,...

Они разбивают ось на интервалы длины в один из которых попадает число а, т.е. существует целое число q, для которого

Введем обозначение Тогда

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

(1)

(2)

Предположим, что Тогда Здесь в то же время Получили противоречие, а это значит, что предположение неверно. Аналогично приводит к противоречию предположение Остается лишь одна возможность но тогда и т.е. оба представления совпадают.

Доказательство закончено. ■

Число q в равенстве называется неполным частным, а r остатком от деления а на b. Если то q называется частным от деления а на b.

Пример. Если то

Если то

Если то

Если то

Если то