4. Если , то .

5. Если , то существуют такие целые и , что . Это свойство есть прямое следствие теоремы 13.2.

Доказательство 1 . Воспользуемся свойством 5 . Имеем

.

Умножим обе части равенства на с, получим

.

Тогда, так как делит первое и второе слагаемое, по второму свойству делимости на делится и сумма, т.е., с.

Доказательство остальных свойств оставляем студентам.

Определение 13.4. Пусть заданы два натуральных числа и , тогда натуральное число, делящееся на эти числа, называется их общим кратным, наименьшее из которых называется наименьшим общим кратным (НОК) и обозначается .

Лемма 13.3. Пусть , тогда .

Доказательство. Пусть , тогда , . При этом по свойству 3 НОД. Поэтому, если М – какое-либо кратное и , то М кратно а и, значит, , для некоторого . Но М кратно и , так что

.

Так как полученное число должно быть целым, то по первому свойству взаимно простых чисел , т.е., , . Следовательно, отсюда получаем, что

.

Отсюда ясно, что при любом число М будет общим кратным чисел и , а наименьшим общим кратным при .

Следствие 1. Произвольное общее кратное чисел и – М удовлетворяет соотношению , .

Следствие 2. Если и , то .

Простые числа

Начнем с определения простого числа.

Определение 13.5. Натуральное число называется простым, если имеет только тривиальные делители, т.е., делятся только на 1 и самого себя.

Определение 13.6. Натуральные числа, не являющиеся простыми, называются составными.

Рассмотрим несколько простых результатов, касающихся простых чисел.

Лемма 13.4. Наименьший не равный 1 делитель целого, большего 1, – число простое. Доказательство. Пусть этот делитель числа не является простым, т.е., составное число. Тогда существует представление , где . А это противоречит тому, что наименьший делитель, ибо по первому свойству делимости, например, .

Лемма 13.5. Наименьший отличный от 1 делитель составного числа не превосходит .

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

Теорема 13.3 (Евклида).

Простых чисел бесконечно много.

Доказательство. Докажем теорему от противного. Пусть – все существующие простые числа. Рассмотрим число . Это число по предположению должно быть составным. И тогда у него есть нетривиальные делители, среди которых должен присутствовать наименьший, т.е., некоторое простое число из имеющихся, например, . Но число не делится на , ибо по свойствам делимости тогда и единица должна была бы делится на , а , будучи простым, больше единицы. Противоречие доказывает теорему.

Это, наверное, самое простое доказательство факта бесконечности простых, хотя имеются многие другие и весьма сложные. Еще в древности был найден способ выписывания последовательности всех простых, не превосходящих некоторой величины. Метод этот называется решетом Эратосфена и заключается в следующем. Задается число-граница , до которой следует выписать все простые числа без пропусков. Составляется ряд натуральных чисел от 2 до и затем начинают процедуру «просеивания». Именно, из последовательности вычеркиваются все числа, кратные 2. Первым не вычеркнутым числом оказывается 3. Поэтому оно простое. Теперь вычеркиваются все числа, кратные 3. И видим, первым не вычеркнутым оказывается число 5, так как 4 вычеркнуто в предыдущий раз. Тогда 5 – простое число. Затем вычеркиваются числа, кратные 5 и т.д. Возникает вопрос: когда процесс можно завершить? Ответ дает лемма 13.5, т.е., требуется перебрать простые и через них «просеять» указанный ряд. Учитывая, что гораздо больше , получаем, что, используя сравнительно малый отрезок простых, можно получить большой массив простых чисел. С точки зрения эффективности эта процедура достаточно медленная и требующая много памяти. Но для небольших вполне приемлемая. Простым числам посвящено множество исследований, но здесь ограничимся необходимым минимумом.

Лемма 13.6. Всякое целое число или взаимно просто с простым , или делится на него.

Доказательство. Пусть . Тогда и, значит, .

Лемма 13.7. Если произведение нескольких целых чисел делится на простое число , то, по крайней мере, один из сомножителей делится на .

Доказательство. Достаточно доказать для двух сомножителей. Пусть . Если , то , тогда по первому свойству взаимно простых чисел .

Теорема 13.4 (основная теорема арифметики).

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

Доказательство. Существование. Пусть число и . Тогда если – простое, то разложение получено, а если оно составное, то его можно представить в виде , где есть наименьший делитель отличный от 1. Отсюда заключаем, что . И вновь, если – число простое, то разложение получено. Иначе, , где уже суть наименьший нетривиальный делитель . Тогда имеем: , и . Продолжая этот процесс, видим, что последовательность нумерованных , строго убывает. Поэтому в силу ограниченности натурального ряда снизу этот процесс обязательно завершится, выделив в последнем случае простое число. Тогда получим представление

. (13.2)

Единственность. Пусть существует еще одно представление в виде произведения простых, а именно: . Приравняем полученные разложения.

.

В соответствии с леммой 13.7 число и, значит, должно делить какой-то из сомножителей , . Пусть это будет . Но так как само простое, то это возможно лишь при . Сократив равенство на общий множитель , получим соотношение

.

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

,

что невозможно. А если , то , что тоже невозможно. Это доказывает единственность разложения.

Следствие. Ввиду того, что в разложении (13.2) могут быть одинаковые сомножители, их можно собрать вместе и представить разложение в виде произведения степеней простых чисел, которое называется каноническим разложением числа . Именно:

, где при , . (13.3)