Дискретно-непрерывная математика (стр. 14 )

M = mq + r,

где 0 ≤ r < т. Так как М и т делятся на а и b, по следствию теоремы 6, число r также должно де­литься и на а, и на b и тем самым быть общим крат­ным этих чисел. Но r < т, а т есть наименьшее по­ложительное общее кратное а и b. Значит, r не может являться положительным числом, так что r = 0. Поэтому Мт.

Теорема 11. Наименьшее общее кратное двух взаимно простых чисел равно их произведению.

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

Пусть числа а и b взаимно просты, и т — их наименьшее общее кратаое. Так как aba и ab'b по предыдущей теореме ab т. Пусть ab = mk. По­ложим т = ас. Тогда ab = ack, т. е. b = ck, так что bk. Точно так же убеждаемся в том, что и ak. Так как числа а и b по условию взаимно простые, должно быть k = 1, а это и означает, что m=ab.

Следствие. Для того чтобы число а делилось на взаимно простые числа b и с, необходимо и достаточно, чтобы оно делилось на их произведение.

Теорема 12. Если abc, причем числа b и с взаимно простые, то ас.

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

Обозначим через т наименьшее общее кратное чисел b и с. По предыдущей теореме т = bс. Да­лее, по условию abс, кроме того, очевидно, аbb. Значит, по теореме 10, abbc, т. е. ab = bck или, после сокращения на b, a = ck, а это и требовалось.

Теорема 13. Если произведение нескольких со­множителей делится на простое число р, то хотя бы один из сомножителей делится на р.

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

Доказательство ведется индукцией по числу сомножителей. Если сомножитель один, то теорема тривиальна. Предположим, что теорема доказана для любого произведения п сомножителей. Пусть а1а2 ... апап+1р. Обозначим а1a2 ... ап через А. Тогда Аап+1p. Если ап+1р, то теорема доказана, а если нет, то по теореме 9 числа ап+1 и р взаимно просты. Но тогда по предыдущему Ар. Так как А есть произведение п сомножителей, по индуктивному предположению один из них должен делиться на р. Теорема доказана.

Следствие. Вся дробь представляет собой це­лое число, т. е. ее числитель делится на знаменатель. Будем считать, что числитель является произведением двух сомножителей: р и 1∙2 ... (р—1)=(р—1)!

Ни один из сомножителей знаменателя дроби не делится на р. Следовательно, по предыдущей тео­реме, на р не делится и весь знаменатель. Но тогда на основании теоремы 9 он взаимно прост с р. Поэто­му на знаменатель должен делиться второй сомно­житель числителя. Обозначая частное от этого деле­ния через q, мы имеем С k р = pq, и требуемое доказано.

Следствие. Если р — простое и 0 < k < p, то число

делится на р.

Теорема 14 (основная теорема арифметики). Всякое целое положительное число, кроме единицы, может быть представлено в виде произве­дения простых сомножителей и притом единственным способом (произведения, отличающиеся только порядком сомножителей, различными не считаются).

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

Сначала докажем возможность разложе­ния любого числа, отличного от единицы, на простые множители. Предположим, что все числа, меньшие N, могут быть так разложены. Если число N простое, то оно автоматически разлагается в произведение про­стых (именно, в произведение, состоящее только из одного сомножителя — самого числа N), и теорема доказана. Пусть теперь N составное, N1 — некоторый делитель N, отличный как от N, так и от единицы, и N2 — частное от деления N на N1. Тогда N = NiN2, причем, как легко проверить, 1<N2<N. Так как N1 и N 2 меньше N, то, по предположению, они разла­гаются в произведения простых множителей. Пусть N1=p1p2 ... pk и N2=q1q2... ql — эти разложения. Тогда p1p2 ... pk q1q2 ... ql является искомым разло­жением числа N. Возможность разложения, таким образом, доказана.

Переходим к доказательству единственности разложения. Пусть нам даны два разложения числа N на простые множители: p1p2 ... pk и q1q2... ql. Оче­видно,

p1p2 ... pk =q1q2... ql (**)

Так как q1q2... ql делится на р1, то по предыдущей теореме хотя бы одно из чисел q1, q2, ..., qt делится на р1. Пусть q1р1 (то, что мы считаем именно пер­вый сомножитель в (**) справа делящимся на р1, никакого дополнительного предположения не озна­чает, так как мы вправе переставлять сомножители местами и обозначить через q1 именно тот из них, ко­торый делится на р1). Так как число q1 простое, это возможно лишь при р1 = q1. Сокращая равенство (**) на р1 получаем

p1p2 ... pk =q1q2... ql . (***)

Аналогично предыдущему убеждаемся в том, что не­которое из чисел q2,q3,..., ql (например, q2) делится на р2, и потому р2 = q2. Сокращая равенство (***) на р2, мы уменьшаем число сомножителей в его час-тях еще на единицу. Такой процесс сокращения, очевидно, можно продолжать до тех пор, пока мы не сократим одно из произведений полностью. Пусть первым сократится произведение, стоящее в (**) слева. Произведение, стоящее в (**) справа, тоже должно при этом сократиться нацело, так как в про­тивном случае мы получили бы равенство вида

1= qk+1... ql

которое невозможно, так как единица не делится ни на какое простое число. При этом мы получаем так­же, что

р1 = q1, р2 = q2,…, pk= qk.

Теорема полностью доказана,

Основная теорема арифметики указывает на принципиальную возможность разложения любого числа на простые сомножители. Однако практическое осу­ществление такого разложения встречает большие трудности. Разложение больших чисел на множители или установление их простоты осуществляется на основе применения электронных вычислительных машин. Так, было обнаружено, что число 219937 — 1 является простым.

Пусть некоторое число а разложено в произведение простых сомножителей. Объединяя равные со­множители, мы получим формулу вида

(7)

где р1, р2.....рr — различные простые числа, a α1, α1,…, αr — некоторые целые положительные числа. Произведение, стоящее в правой части формулы (7),называется каноническим разложением числа α.

Теорема 15. Для того чтобы числа а и b были взаимно простыми, необходимо и достаточно, чтобы ни один из простых сомножителей, входящих в каноническое разложение числа а, не входил в канони­ческое разложение числа b.

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

Пусть — соответственно канонические разложения чисел а и b, a d — некоторый общий делитель этих чисел. Если d ≠ 1, то d делится на некоторое простое число р. Тогда по теореме 3 ар и bр, так что р находится как среди чисел р1, р2, ..., рk, так и среди чисел q1, q2, ..., ql. Поэтому среди простых чисел, входящих в канониче­ское разложение α, существует хотя бы одно, входя­щее в каноническое разложение b.