При использовании материалов этого сайта - АКТИВНАЯ ССЫЛКА и размещение баннера -ОБЯЗАТЕЛЬНО!!!

БЕСЕДА по теме "НАТУРАЛЬНЫЕ ЧИСЛА и ДЕЛИМОСТЬ"

(диалог Гуманитария и Математика)

Г: ? Что может быть проще натурального ряда? 1, 2, 3, 5,... и так далее, без конца. То есть, для всякого натурального числа (n) найдется число, еще большее ? например, следующее за ним число (n+1). При этом каждое натуральное число (n) следует за неким другим числом ? тем, которое обозначается (n-1). Только единица 1 ни за кем не следует: она ? первая среди натуральных чисел. Выйдя из единицы и последовательно переходя от предыдущего числа к последующему, мы пройдем весь натуральный ряд ? если, конечно, нам дано неограниченное время.

Так рассуждает обычный Гуманитарий на обыденном языке ? русском, английском или китайском. Но Математик, как вам уже известно, подобен Французу ? или, если угодно, Ирокезу. О чем ему ни расскажешь на обычном языке ? он все переводит на свой язык, и получается нечто совсем иное. Например, во что превратит Математик наши наивные рассуждения о натуральных числах? Послушаем этого странного эксперта:

М: ? Ой, как здорово! Всего в пяти фразах вы описали все главные свойства натуральных чисел. Теперь я могу по вашим словам составить систему определений и аксиом, описывающих натуральный ряд (N) со всеми потрохами ? включая арифметические действия! Вот, смотрите:

Аксиома 1. Всякому элементу (n) из множества (N) сопоставлен единственный элемент (n"), СЛЕДУЮЩИЙ за ним и отличный от него.

Аксиома 2. Единица (1) не следует ни за каким элементом множества (N).

Аксиома 3. Каждый элемент (n) множества (N), кроме единицы, следует за некоторым элементом ("n) из (N), отличным от (n).

Аксиома 4. Если (n" = m"), то (n = m).

Аксиома 5. Если подмножество (А) в множестве (N) содержит единицу (1) и, вместе с каждым своим элементом (а), содержит также следующий за ним элемент (а") ? то (А) СОВПАДАЕТ со всем множеством (N).

М: ? Вот вам пять фраз на математическом языке, равносильные тем пяти русским фразам, которыми вы описали свойства натуральных чисел. Как вам это нравится?

Г: ? Боюсь, что ирокезские фразы нравятся только тому, кто сведущ в ирокезском языке. То же самое можно сказать о математических фразах. Кстати, вы обещали сформулировать аксиомы натурального ряда так, что из них будет следовать вся арифметика. Этого пока не видно! В ваших аксиомах не заметно ни знака (+), ни числа (2). Как же мы узнаем, что (2+2 = 4)?

М: ? Чтобы это узнать, нужно дать определение СУММЫ двух натуральных чисел. Вот оно:

О1. Для всякого (n), (n+1) = n".

О2. Если сумма (n+m) уже определена, то n+(m") = (n+m)".

Иными словами, число (2) следует за единицей (1): таково его определение, (2 = 1"). Аналогично, (3 = 2"), (4 = 3") ? тоже по определению чисел (3) и (4). А дальше все просто:

2+2 = 2+(1") = (2+1)" = (2")" = 3" = 4.

Все эти равенства вытекают из определения суммы двух натуральных чисел!

Г: ? Вот как! Значит, фраза "Два плюс два равно четыре" ? это ФОРМУЛИРОВКА теоремы, И уважаемый Математик сейчас рассказал нам ДОКАЗАТЕЛЬСТВО этой теоремы, используя ОПРЕДЕЛЕНИЯ чисел (2) и (4), а также определение СУММЫ двух натуральных чисел и определение всего МНОЖЕСТВА натуральных чисел. Это последнее (а вернее ? первое, изначальное) определение натурального ряда (N) состоит из пяти аксиом, которые мы нечаянно выразили на обыденном языке. Так вас надо понимать, товарищ Математик?

М: ? Именно так! И не жалуйтесь на мое иноязычие. Ведь вы сами довольно быстро осваиваете мой "ирокезский" язык! Какие у вас еще есть вопросы?

Г: ? Ясно, какие! Докажите теперь, что "Дважды два ? четыре"! Об умножении у вас пока ни слова не было. Что же, вы опять придумаете новое определение?

М: ? Ну конечно! Вот оно:

О3. Для всякого (n), (n*1) = (n).

О4. Если произведение (n*m) уже определено, то

n*(m") = (n*m) + n.

М: ? Теперь докажем, для примера, что "Дважды два ? четыре".

Вот так: 2*2 = 2*(1") = (2*1) + 2 = 2+2 = 4.

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

Г: ? Да, это понятно. Но если так ? значит, вся таблица умножения состоит из формулировок теорем! И все их надо доказывать... Неужели каждую отдельно ? так, как вы сейчас доказывали, что "Дважды два ? четыре"?

М: ? Конечно, нет! Для того и был создан математический язык, чтобы сводить длинные рассуждения к коротким. Ведь и первоклассники учат наизусть не всю таблицу умножения, а только небольшой ее кусок ? до строки "Десятью десять ? сто". Дальше запоминать не нужно, а надо выучить ПРАВИЛО умножения чисел "столбиком". Это и есть формулировка самой важной теоремы об умножении натуральных чисел ? разумеется, в ДЕСЯТИЧНОЙ системе записи. Если бы мы пользовались ДВОИЧНОЙ записью (как делают наши компьютеры), то необходимая таблица умножения была бы еще короче ? только до строки "Дважды два ? четыре". А дальше ? простое правило умножения столбиком!

Г: ? Вот теперь, кажется, понятно! Значит, каждое действие ? сложение или умножение ? определяется с помощью двух аксиом. Из них выводятся несколько теорем-формул, составляющих таблицу умножения (либо сложения) однозначных чисел. И еще две теоремы: о сложении либо умножении многозначных чисел столбиком... А как быть с ОБРАТНЫМИ действиями ? вычитанием и делением натуральных чисел?

М: ? С вычитанием все просто: оно определяется аналогично сложению, но для получения разности нужно сдвигать первое слагаемое вдоль натурального ряда не вправо, а ВЛЕВО. Поскольку такой сдвиг не всегда возможен (слева от единицы ничего нет), то для выполнимости вычитания пришлось РАСШИРИТЬ натуральный ряд до ряда ЦЕЛЫХ чисел (Z): он бесконечен в ОБЕ стороны, с тем же шагом 1.

// Кстати, вот вам полезная ЗАДАЧА: напишите систему аксиом, задающую множество всех целых чисел (Z). Какие из пяти аксиом натурального ряда вам придется изменить, и как изменить?

Г: ? Спасибо: эта задача, кажется, под силу обычному человеку. А как насчет операции УМНОЖЕНИЯ среди целых чисел? Почему все-таки "Минус, умноженный на Минус, дает Плюс"? Из чего этот факт выводится?

М: ? Ни из чего! Это НОВАЯ АКСИОМА, без которой арифметику целых чисел не построить. Конечно, ее можно заменить ДРУГОЙ аксиомой: например, "Минус, умноженный на Минус, дает Минус". Но этим мы загубим операцию умножения: обратная операция (деление) станет НЕОДНОЗНАЧНОЙ, и даже простейшие линейные уравнения окажутся без решений.

Г: ? Ладно: этому можно поверить без доказательства. А вот насчет ДЕЛЕНИЯ ? это дело серьезное. По аналогии со сложением и умножением я делаю вывод: правило деления столбиком ? это тоже теорема, с довольно сложным доказательством. Верно?

М: ? Да, именно так! Но в основе почти каждой трудной теоремы лежат одна-две леммы с простыми формулировками и не очень сложными доказательствами. Внутри теоремы о делении целых чисел скрыта всего одна такая лемма: о СУЩЕСТВОВАНИИ и ЕДИНСТВЕННОСТИ деления с ОСТАТКОМ среди натуральных чисел. Вот ее точная формулировка:

ЛЕММА. Пусть даны два натуральных числа (а) и (в), причем (а>в). Тогда существуют целые числа (с) и (d) такие, что а = с*в + d. При этом 0<d<в, 1<c<а. Числа (с) и (d) с такими свойствами ЕДИНСТВЕННЫ: из них (c) называют ЧАСТНЫМ, а (d) ? ОСТАТКОМ от деления (а) на (в).

Г: ? Ну, тут смысл ясен. Да и доказательство, видимо, несложное. Надо раз за разом вычитать из числа (а) его делитель (в) ? до тех пор, пока (после (с) вычитаний) не получится остаток (d<в). Потом нужно доказать единственность частного и остатка. Там, наверное, будут какие-нибудь ухищрения ? но вдаваться в них не стоит! Вы нам лучше ответьте на такой вопрос: где еще применяется эта лемма?

М: ? Вот это меткий вопрос! Поздравляю вас, коллега, с хорошим вкусом в математике! Действительно: самое важное применение леммы о делении с остатком ? это АЛГОРИТМ ЕВКЛИДА, имеющий целью поиск Наибольшего Общего Делителя двух чисел. А самое главное теоретическое применение этого алгоритма ? доказательство Большой Теоремы о Единственности РАЗЛОЖЕНИЯ целого числа на ПРОСТЫЕ множители. Некогда эту теорему величали "Основной Теоремой Арифметики" ? до тех пор, пока не были обнаружены диковинные числовые миры, в которых простое разложение НЕ единственно. После этого гонор алгебраистов нашел себе новые выражения.

Г: ? Ну, об этих чудесах мы поговорим позже ? если явится такая нужда. А вот про алгоритм Евклида вы нам объясните все необходимое ? да и про разложение на множители тоже!

М: ? Извольте, объясню: большой хитрости тут нет. Пусть нужно найти НОД чисел (а1) и (в1), причем (а1>в1). Для начала разделим (а1) на (в1) с остатком (d1): это, как мы уже знаем, процедура однозначная. Если получился нулевой остаток ? ура! Тогда наша работа окончена, (в1) = НОД (а1, в1).

А если остаток (d1) не равен 0? Тогда он меньше, чем (в1) ? и можно разделить (в1) на (d1) с новым остатком (d2). Если (d2 = 0), то (в1) делится на (d1) без остатка. Поэтому число (а1), равное (в1*c1 + d1), тоже делится на (d1) без остатка; так что (d2) есть НОД (а1, в1).

В общем случае придется проделать много таких делений: каждый раз мы делим предыдущий делитель на предыдущий остаток и дожидаемся, пока очередной остаток окажется равным 0. После этого мы принимаем ПОСЛЕДНИЙ НЕНУЛЕВОЙ остаток за НОД исходных чисел (а1) и (в1). Вот и все доказательство!

Г: ? Схема, пожалуй, ясна; но некоторые детали вызывают сомнение. Например, почему описанный вами процесс поиска НОД завершится на каком-то шаге ? а не будет длиться без конца? И еще: легко поверить, что последний ненулевой остаток (dк) будет общим делителем всех промежуточных делимых чисел: от последнего (вк) до первого (а1). Но почему это будет НАИБОЛЬШИЙ их общий делитель? Тут, наверное, нужны точные расчеты; на слово этому рассказу верить не следует!

М: ? Воистину так! Проделайте сами эти расчеты: вы убедитесь, что все верно. Из записи первого деления с остатком (а1=в1*c1+d1) видно, что ЛЮБОЙ общий делитель чисел (а1) и (в1) делит также число (d1). Из второй строки вы узнаете, что такой делитель делит также число (d2) ? и так далее, до конца.

А вот будет ли делу конец ? это особый вопрос, с утвердительным ответом. Дело в том, что каждый следующий остаток в алгоритме Евклида МЕНЬШЕ предыдущего. Значит, на каждом шаге остаток уменьшается хотя бы на 1 ? то есть, процесс поисков НОД (а,в) может длиться не более чем (в) шагов.

Г: ? Да, теперь, кажется, все понятно. Только не ясно, как из алгоритма Евклида может следовать ОДНОЗНАЧНОСТЬ разложения на простые множители... Что-то я не заметил такой теоремы в знаменитой книге Евклида!
 
 

М: ? Действительно, это непростой вывод ? и сам Евклид его не сделал, потому что он ПРИНЯЛ НА ВЕРУ единственность раложения на множители среди натуральных чисел (а отрицательных чисел он вовсе не знал!)

Если мы хотим получить такое доказательство, то нам нужно еще одно СЛЕДСТВИЕ из алгоритма Евклида: что число НОД(а,в) является ЛИНЕЙНОЙ КОМБИНАЦИЕЙ чисел (а) и (в) с ЦЕЛЫМИ коэффициентами.

Например: НОД(3,5) = 1 = 2*3 + (-1)*5

Или: НОД(98, 26) = 2 = 4*98 + (-15)*26

М: ? Позвольте мне не доказывать этот факт в общем виде! Лучше я покажу, как он получается во ВТОРОМ из моих примеров ? достаточно сложном. Запишем алгоритм Евклида для чисел (98,26):

98 = 26*3 + 20

26 = 20*1 + 6

20 = 6*3 + 2

6 = 2*3 + 0

М: ? Итак, мы узнали, что НОД(98,26) = 2; при этом из ТРЕТЬЕЙ строки видно, как этот НОД выражается через два остатка, которые ему предшествовали: (6) и (20). Заменим в этом равенстве промежуточные остатки (6) и (20) их выражениями через НАЧАЛЬНЫЕ числа (98) и (26): эти выражения записаны в ПЕРВОЙ и ВТОРОЙ строках. Так мы получим:

2 = 20 ? 3*6 = (98 ? 3*26) ? 3*(26 ? 20) =

= 98 ? 6*26 + 3*20 = 98 ? 6*26 + 3*(98 ? 3*26) =

= 4*98 ? 15*26

М: ? В общем случае выкладки такие же, но чуть длиннее.

Г: ? Да, этому можно поверить! Но почему все-таки разложение целого числа на простые множители единственно?

М: ? Потому, что произведение двух целых чисел (А*В) делится на ПРОСТОЕ число (Р) только в том случае, если (А = К*Р) или (В = N*Р).

Этот факт нетрудно доказать ОТ ПРОТИВНОГО. Сделаем это!

М: ? Если число (А) НЕ делится на простое (Р), то НОД(А,Р) = 1

Если число (В) НЕ делится на простое (Р), то НОД(В,Р) = 1 Если верно и то, и другое, то мы получаем систему двух равенств

1 = (а1)*А + (в1)*В

1 = (а2)*А + (в2)*В

А теперь ПЕРЕМНОЖИМ левые части этих двух равенств друг на друга, и их правые части ? тоже. Получится:

1 = (а1*А + в1*Р)*(а2*В + в2*Р) = (а1*а2*А*В) + (в1*а2*Р) +

+ (а1*в2*Р) + (в1*в2*Р*Р)

Видно, что в ПРАВОЙ части этого равенства КАЖДОЕ слагаемое делится на (Р). Для всех слагаемых, кроме первого, это очевидно ? а первое слагаемое делится на (Р), поскольку произведение (А*В) делится на (Р) ? по условию нашей теоремы.

Напротив: в ЛЕВОЙ части нашего равенства стоит единица 1, которая не делится ни на какое другое число.

Это противоречие доказывает ЛОЖНОСТЬ нашего предположения: либо (А), либо (В) делится на (Р), что и требовалось доказать.

Г: ? Ну и хитрец вы, сударь! Получили два равенства с одинаковыми левыми частями ? и вместо того, чтобы ПРИРАВНЯТЬ их правые части, вы их ПЕРМНОЖАЕТЕ... Но победителя не судят! Как же теперь доказать, что 3*5*11*19 = 7*13*17?

М: Теперь это просто! Сначала разобьем правую часть вашего равенства на ДВА множителя ? например, на (7) и (13*17). Далее, заметим, что левая часть равенства ДЕЛИТСЯ на простое число (3); значит, и правая часть делится на него. Согласно только что доказанной лемме, хотя бы ОДИН из множителей справа ? либо (7), либо (13*17) ? ДЕЛИТСЯ на (3). Но ПРОСТОЕ число (7) НЕ делится на другое простое число (3). Поэтому на (3) делится произведение (13*17). Значит, либо число (13), либо число (17) делится на (3). Но оба эти числа ? простые, и такое деление невозможно. Все доказано!

Г: ? Вот теперь ясно! Вы "ДРОБИТЕ" одну из частей предполагаемого равенства (скажем, правую часть) пополам ? и заключаете, что один из ее сомножителей ОБЯЗАН делиться на какой-то из ПРОСТЫХ множителей, стоящих слева. Потом вы еще раз дробите пополам этот якобы "делящийся" сомножитель ? и повторяете эту процедуру, пока не дойдете до одного простого числа. Уж оно наверняка не делится на ДРУГОЕ простое число!

М: ? Совершенно верно ! Вы так хорошо все поняли, что мне охота задать вам коварный профессиональный вопрос. Откуда вы знаете, что число (2) или (3) ? простое? Как это можно доказать?

Г: ? Вот это лихо! А и правда: ни в одной из аксиом не говорится о СУЩЕСТВОВАНИИ простых чисел! Значит, это ? теорема, и надо ее доказывать... Ну, начнем с двойки: на что она могла бы делиться? На что-нибудь меньшее, чем она сама... А ничего меньшего нет ? кроме единицы!

М: ? Верно! Простоту числа (2) вы доказали. А как насчет тройки?

Г: Наверное, так же: перебором произведений всех меньших тройки натуральных чисел! Человеку это занятие противно ? но можно научить ему компьютер...

М: ? И тут вы правы! Человек должен доказывать такие факты, от которых он становится умнее. Вот, например, теорема Евклида о бесконечности множества простых чисел.

Г: ? А как ее можно доказать?

М: ? Конечно, от противного! Попробуйте сделать это сами!

Г: ? Можно попробовать... Итак, пусть множество всех простых чисел конечно: допустим, их сто штук. Как бы построить из них сто первое простое число?

М: ? Постарайтесь для начала смастерить число, НЕ ДЕЛЯЩЕЕСЯ ни на одно из ваших ста простых чисел!

Г: ? Это можно! Достаточно перемножить их все, и к этому произведению (А) добавить единицу. Она будет остатком от деления огромного числа (А+1) на каждое простое число, входящее в (А) как множитель.

М: ? Верное рассуждение! Но можете ли вы утверждать, что ваше огромное числа (А+1) ? простое?

Г: ? Не знаю... Может быть, и нет!

М: ? Опять вы правы! Поэтому позвольте мне быстро закончить ваше доказательство. Если даже (А+1) ? не простое число, то среди его делителей НЕТ чисел из отмеченной вами сотни простых чисел. Значит, СУЩЕСТВУЕТ сто первое простое число ? хотя БЫСТРОГО пути его построения по известной сотне простых чисел мы с вами придумать не смогли. Кстати, такого способа не знает никто из математиков!

Но я могу предложить вам пример. Пусть А = 2*3*5*7*11*13. Я обещаю вам, что число (А+1) ? не простое. Попробуйте отыскать хоть один его простой делитель! Если не сумеете сами ? поручите это дело компьютеру.

Г: ? А поинтереснее задачку вы не можете предложить?

М: ? Извольте! Могу дать несколько задач ? на любой вкус. Например, попробуйте доказать, что множество простых чисел вида (4к-1) бесконечно. Схема доказательства ? почти как у Евклида, но тут будет одна дополнительная тонкость: найдите ее сами!

И обязательно проверьте: почему эта схема доказательства НЕ ПРОХОДИТ для простых чисел вида (4к+1)? Сам-то факт верен и там, и в более общей ситуации: множество простых чисел почти в любой арифметической прогрессии бесконечно. Но доказательство намного сложнее: для чисел вида (4к+1) его нашел только Гаусс, использовав комплексные числа. Вот вам урок: рядом с красивым и простым фактом лежит другой ? очень похожий на него по красоте, но гораздо более трудный!

Г: ? Ладно, попробую помериться силой если не с Гауссом, то хоть с Евклидом! А насчет делимости вы можете дать хорошую задачу?

М: ? Конечно, могу! На эту тему много хороших задач. Вот вам две ? не особенно трудные. Первая: многочлен (Х.. + Х + 41) принимает простые значения при очень многих натуральных значениях аргумента (Х). Проверьте это сами ? и докажите, что этот многочлен не может принимать простые значения при ВСЕХ натуральных значениях арггумента! Кстати, этот факт верен для ЛЮБОГО многочлена с целыми коэффициентами. Сообразите: при каких коэффициентах доказательство окажется самым трудным?

Г: ? Наверное, тогда, когда все коэффициенты равны плюс или минус единице!

М: ? Славно работает ваша интуиция! Вот вам за это еще одна исследовательская задача. Рассмотрим многочлен (Р.. -1), где символ (Р) пробегает все ПРОСТЫЕ значения, начиная с 5. Я утверждаю, что значения этого многочлена во ВСЕХ точках делятся на некоторое натуральное число ? довольно большое. Какое оно? Угадайте в простейших примерах и докажите в общем виде!

Г: ? А по поводу аксиом есть красивые задачи?

М: ? Конечно, есть! Например, попробуйте доказать НЕОБХОДИМОСТЬ каждой из 5 аксиом натурального ряда с помощью контрпримеров. То есть, постройте 5 примеров множеств, отличных от (N), но удовлетворяющих всем аксиомам, кроме какой-то одной. Это удобно сделать на рисунке ? из точек и стрелочек.

Г: ? Вот это ? хорошее развлечение! Наверное, одним из контрпримеров будет ряд целых чисел. А другим ? замкнутый контур...

М: ? Верно! Продолжайте в том же духе ? не разочаруетесь! А если угодно еще задачу на ту же тему ? сообразите-ка, почему пятую аксиому натурального ряда называют "Аксиомой Индукции"?

Г: ? Это как-то связано с "методом математической индукции", о котором вы ни слова не сказали?

М: ? Конечно, связано! Возьмем любую формулу, зависящую от натурального числа (n). Обозначим через (А) множество тех чисел (n), для которых формула верна. Проверим, лежит ли в множестве (А) число 1. Затем предположим, что в нем лежит число (к) ? и проверим, вытекает ли из этого, что в (А) лежит следующее число (к"). Если вытекает ? значит, (А) совпадает со всем (N), по аксиоме 5. То есть, наше формула верна для всех значений (n).

Г: ? Вот оно что! Ну, дайте еще парочку задач на индукцию!

М: ? Извольте! Вот легкая задача: докажите, что сумма кубов первых (к) натуральных чисел равна (к(к+1))../4.

Г: ? Это же ? квадрат суммы первых (к) натуральных чисел!

М: ? Именно так! Но угадать этот факт трудно ? а доказать по индукции довольно легко. А еще получайте исследовательскую задачу: на какое наибольшее число частей могут разделить плоскость (к) прямых? Ответ я вам подсказывать не стану: угадайте его в простейших примерах, а потом докажите по индукции!

Г: ? Кажется, этого хватит для разумного развлечения... Но под занавес ? приведите пример НЕ РЕШЕННОЙ до сих пор проблемы из области натуральных чисел! Есть такие проблемы?

М: ? Есть, хотя немного. Вот вам самая древняя проблема: ее, видимо, предложил еще Эратосфен. Конечно или бесконечно множество простых близнецов ? то есть, пар простых чисел вида

(Р);(Р+2)?

Г: ? Неужели это неизвестно?

М: ? Представьте себе: неизвестно! Тут не помогают ни простейшие приемы Евклида, ни хитрые рассуждения Гаусса, ни даже зубодробительная техника Дирихле. Только в 1930 году удалось доказать, что доля близнецов среди всех простых чисел УБЫВАЕТ и стремится к 0 при неограниченном росте того отрезка натурального ряда, на котором мы рассматриваем простые числа. Но из стремления к нулю этой доли не следует существование НАИБОЛЬШЕГО простого близнеца! Итак, проблема Эратосфена все еще ждет своего покорителя ? через 22 столетия после того, как ее заметил хитроумный директор Александрийской библиотеки. Так вот и развивается древняя и вечно юная теория чисел, с которой я имел честь вас познакомить. Вы довольны?

Г: ? Да, премного! Математиком вы меня, конечно, не сделали. Однако убедили в том, что "Одной наукой больше ? одной душой больше", если чуть перефразировать немецкуб поговорку о языках.

Спасибо вам, уважаемый Француз ? или Ирокез, как вам угодно!

FINITA LA COMEDIA. SAPERE AUDE! PLUS ULTRA!

БЕСЕДА по теме "НАТУРАЛЬНЫЕ ЧИСЛА и ДЕЛИМОСТЬ"