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

Введение

Всякое искусство совершенно бесполезно.
О. Уайльд

Теория чисел — раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Упаси Боже меня давать здесь точное определение понятия "Теория чисел", так как, во-первых, я его не знаю, а во-вторых, даже если вы поместите в одну e-окрестность двух учёных-профессионалов, работающих по их мнению в теории чисел, то они могут подраться между собой, так и не прийдя к единому мнению из чего же состоит "Теория чисел". Я надеюсь, что читатели тоже будут иметь своё мнение по этому вопросу после окончания процесса понимания хотя бы одного учебника или (скромно так) этой книжки по теории чисел.

В головах многих математиков, как профессионалов, так и любителей, паразитирует мнение, что теория чисел — это наиболее абстрактная и отдаленная от практических применений математическая теория, пусть красивая и стройная сама по себе (эдакая "Вещь в себе", по Канту), но совершенно бесполезная с точки зрения народного хозяйства.

Более того, некоторые теоретики-числовики даже гордятся такой точкой зрения, считая себя богемными представителями "чистого искусства", которое неприменимо, например, для создания атомной бомбы или чего-нибудь еще в этом роде. Они задирают нос, освобождают себя от моральных страданий Оппенгеймера и Эйнштейна, они творят красоту и только красоту, выше которой идет мудрость уже божественная, океан слепящего, непостижимого света.

Бедолаги. Их богемность разбивается уже фразой Пифагора "Все есть число!" и изучая числа, они неизбежно изучают окружающий нас мир, и себя в том числе (каламбур). Но кроме этого философского замечания о практической применимости "чистой" теории чисел, которое вряд ли будет понятно тупому дяденьке, дыхнувшему на вас перегаром в трамвае, я расскажу вам одну правдивую историю. Эта история убедит любого эстета от математики в том, что теория чисел не просто красивейшая и стройнейшая область чистой науки, но и серьезная народохозяйственная структура. Правда, не уверен, что она убедит дяденьку из трамвая, но такого дяденьку вообще уже вряд ли что убедит, ибо он убежден сам по себе, причем с утра. В дальнейшем договоримся обозначать убежденные с утра и им подобные объекты латинской буквой х и исключать их из области объектов, на которых рассчитано наше повествование.

В начале семидесятых годов нашего двадцатого века американское космическое агентство NASA, получив от Конгресса США несколько миллиардов долларов, решило осуществить запуск исследовательского спутника на Юпитер. Спутник склепали, напичкали дорогостоящей аппаратурой, назвали "Пионер" (лектору в этом месте рекомендуется характерный жест правой рукой наискосок об лоб), и запустили вверх. Для успешного управления дальнейшим полетом увороченного агрегата, ежику понятно, необходимо было постоянно перерасчитывать его траекторию, корректируя ее от случайных возмущений и целя в Юпитер, который, между прочим, хоть и большой, но летает от нас на расстоянии более 100 миллионов километров, поэтому попасть в него ужасно трудно.

Знатоки знают, что для расчета подобных траекторий нужно решать систему дифференциальных уравнений, которую не то что решать, а даже и писать-то не хочется, настолько она сложна и огромна. Но Пионер-то уже летит, как фанера над Парижем, а Конгресс внимательно следит за расходом средств налогоплательщиков, поэтому специалисты NASA вынуждены считать эти чертовы многомерные интегралы, причем в режиме реального времени. "В режиме реального времени" – это означает, что интеграл надо успеть посчитать до того, как спутник улетит вместо Юпитера в деревню Пропадайлово.

Знатоки опять знают, что единственный известный сегодня быстрый способ вычисления таких интегралов с использованием ЭВМ — это метод Монте-Карло (а это такой город, в отличие от Бойля-Мариотта). Далее буду краток. Монте-Карлу нужно многократное случайное бросание точки в многомерную область. Электронная машина не умеет генерировать случайные числа, так как она работает по программе, написанной заранее на языке FORTRAN (помните, был такой). FORTRAN разработали специально для запуска пионеров и вставили в него датчик (от слова "давать") случайных чисел RND(n), который, работая по некоторой наспех созданной схеме, выдавал последовательность "квазислучайных" чисел из отрезка [0; 1], равномерно на нем распределенную. Все было здорово.

Беда началась тогда, когда эти "квазислучайные" числа начали объединять в пары, тройки, и т. д., чтобы получить координаты "случайной" точки многомерной области. RND(n) оказался составленным настолько неудачно, что 60% "случайных" точек из единичного квадрата на плоскости (всего-то двухмерная область!) попадали в его нижнюю половину (а это даже в боксе — неэтично)! Монте-Карло не сработал, спутник промазал мимо Юпитера всего на каких-то 20 миллионов километров, и несколько миллиардов долларов вылетели в трубу.

Мораль: когда теоретик-числовик из заоблачных высот на несколько минут спускается на землю для сообщения процедуры получения случайных чисел с помощью эффектной цепочки делений и взятия остатков, убейте его сразу — дешевле будет. Народохозяйственное применение теории чисел здесь очевидно: она должна выдать такую процедуру получения случайных чисел, чтобы мы могли спокойно и спутники запускать, и землю пахать, и напильники коллекционировать. Вывод: изучайте теорию чисел, восторгайтесь ее красотами, любуйтесь ею, как произведением искусства, но помните, что вопреки эпиграфу к этому введению из "Портрета Дориана Грея", всякое искусство где-нибудь и когда-нибудь приносит пользу. Читателей же, заинтересовавшихся машинным получением случайных чисел, отсылаю к уникальной и великолепной книжке Д. Кнута "Искусство программирования для ЭВМ", том 2 "Получисленные алгоритмы", глава 3 "Случайные числа". Увлекательное чтиво!

Ну как, читатели, убедил ли я вас в практической значимости теории чисел? Только не говорите, что нет, иначе мне прийдется рассказать еще сотню подобных историй, а это не входит ни в мои планы, ни в планы традиционных университетских курсов по теории чисел. Я хочу закончить на этом многословную общую болтовню о предмете, которому с любовью посвящаю эту скромную книжку, однако, по традиции, во введениях всего мира делают несколько предварительных замечаний и информируют читателя об устройстве дальнейшего текста, а, стало быть, и курса теории чисел. Сим и займемся.

Текст настоящей книжки незатейливо разбивается на параграфы, каждый из которых освещает некоторую тему достаточно полно с точки зрения автора (и, возможно, только автора). Каждый параграф, в свою очередь, разбивается на небольшие пункты. Студенты! Ожидаемый мною устный ответ на экзаменационный вопрос — это либо отдельный пункт (если он не очень большой), либо теорема с доказательством (любому студенту это должно быть понятно). Упорядоченность материала внутри каждого параграфа линейная, поэтому книжку рекомендуется читать подряд, а не так, как делал один мой однокурсник, читая сначала чётные пункты, потом – нечетные. Однако, если у вас механически-идеальная память, вы можете изучать теорию чисел и этим способом.

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

.

(Похоже, эти картинки специально разработаны в огромном количестве фирмой Microsoft исключительно для засорения жестких дисков наших компьютеров.) Не гнушайтесь прорешать предлагаемые задачи, ибо человек начинает уютно себя чувствовать в изучаемом теоретическом материале только после решения нескольких задач.

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

Иногда, в процессе набора книжки, в конце некоторых пунктов оставалось пустое место. Я принял решение заполнять эти пустые места несерьезным окололитературным творчеством, имевшим, однако, успех на нескольких последних студенческих праздниках — Днях Первокурсника и Днях Математика и Механика. Насколько удачно подобное окололитературное творчество — судить читателю, утомленному сложной теорией. Всюду далее такие несерьезные вставки отмечены символом NS (что означает Nе Sерьезно).

От всего сердца желаю вам крепкого здоровья, хорошего настроения и успехов в изучении прекрасного раздела математики — теории чисел. Удачи!

 

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

Пункт 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 центов, ковбой пристрелил бармена. За что?

12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: