§ 1. Основные понятия и теоремы

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

Целые числа — суть {..., –3, –2, –1, 0, 1, 2 , 3,...}. В этой книжке будет употребляться довольно стандартное обозначение этого множества — жирная буква Z . (Очень часто употребляется и ажурная Z , но я не сторонник ажурных излишеств ушедшего в прошлое стиля рококо). Известно, что относительно обычных операций сложения и умножения, множество целых чисел является кольцом, а для более страстных почитателей алгебры можно сказать и точнее: Z является моногенным ассоциативно-коммутативным кольцом с единицей. Этот привычный со школьной скамьи объект на самом деле является очень сложным, но я не буду сейчас объяснять, в чем состоит сложность арифметики целых чисел, ибо такое объяснение может увести нас слишком далеко от названия этого пункта. Математику-профессионалу в этом месте могут прийти в голову и знаменитая теорема Геделя о неполноте формальной арифметики, и выдающийся результат Матиясевича об алгоритмической неразрешимости систем диофантовых уравнений, и великое множество элементарно формулируемых, но до сих пор нерешенных теоретико-числовых проблем и т.д., и т.п. Однако, давайте пока воспримем Z просто как объект, преподнесенный нам в подарок природой-матушкой и займемся его изучением.

“Прекрасная половина” {1, 2, 3, 4,...} множества целых чисел зовется множеством натуральных чисел и стандартно обозначается жирной как поросеночек буквой N .

Определение. Пусть a , b О Z . Число а делится на число b если найдется такое число q О Z , что а = qb . Синонимы: а кратно b ; b — делитель а . Запись: а     b или b  |  a .

Легко заметить, что отношение делимости b | a есть бинарное отношение на множестве Z , а если ограничиться рассмотрением только натуральных чисел, то несложно установить, что на множестве N это бинарное отношение является рефлексивным, антисимметричным и транзитивным, т. е. отношением частичного порядка. Легко проверяется также следующее свойство:

Пусть а ₁ + а ₂ +...+ а _n  = c ₁ + c ₂ +...+ c _k – равенство сумм целых чисел. Если все слагаемые в этом равенстве, кроме одного, кратны b , то и оставшееся слагаемое обязано быть кратным b .

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

Теорема . Для данного целого отличного от нуля числа b , всякое целое число а единственным образом представимо в виде а = bq + r , где 0  Ј   r  < | b |.

Доказательство. Ясно, что одно представление числа а равенством а = bq + r мы получим, если возьмем bq равным наибольшему кратному числа b , не превосходящему а (см. рис. 1)

( a = 3b+r )

Рис. 1

Тогда, очевидно, 0 Ј r < | b |. Докажем единственность такого представления. Ну пусть а = bq + r и а = bq ₁ + r ₁ — два таких представления. Значит 0 = а – а = b ( q – q ₁ ) + ( r – r ₁ ). Здесь 0 делится на b ; b ( q – q ₁ ) делится на b , следовательно ( r – r ₁ ) обязано делиться на b . Так как 0 Ј r < b и 0 Ј r ₁ < b , то r – r ₁ < b и r – r ₁ делится на b , значит r – r ₁ равно нулю, а, значит и q — q ₁ равно нулю, т. е. два таких представления совпадают.

Ё

Сразу после доказательства теоремы, пока не забылись использовавшиеся в нем обозначения, дадим

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

Признаюсь, что идея рисунка 1, поясняющего доказательство теоремы, принадлежит не мне, а древним грекам, которые, впрочем, не знали, что они древние. Именно древние греки, почему-то, очень любили многократно укладывать один отрезок в другой, а оставшуюся часть большего отрезка, естественно, называли “остатком”.

Заметим, дорогие читатели, что остаток — всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом. Поэтому на вопрос: “Сколько будет минус пять поделить на три с остатком?”, каждый должен бойко отвечать: “Минус два, в остатке — один!”. Но за добрый десяток лет опыта приема устных вступительных экзаменов в университет, судьба еще не послала мне абитуриента, правильно ответившего на этот вопрос. А ведь это дети, специально готовившие себя поступать именно на математико-механический факультет. “Печально я гляжу на наше поколение...”

Задачки

1. Разделите с остатком: а) 161 на 17; б) –161 на 17; в) 161 на –17; г) –161 на –17. 2. Разделите с остатком: а) 17 на 161; б) –17 на 161; в) 17 на –161; г) –17 на –161. 3. Проверьте, что множество N \ {1}={2,3,4,...} с отношением делимости есть частично упорядоченное множество. Найдите его минимальные элементы. 4. Справедливый ковбой зашел в бар и попросил у бармена стакан виски за 3 доллара, пачку Marlboro за доллар и 11 центов, шесть пачек патронов для своего кольта и дюжину коробков спичек. Услышав итоговую сумму – 28 долларов и 25 центов, ковбой пристрелил бармена. За что?