Основная теорема арифметики
Лемма Евклида
| Лемма: |
Если простое число делит без остатка произведение двух целых чисел , то делит или . |
| Доказательство: |
|
Пусть делится на , но не делится на . Тогда и — взаимно простые, следовательно, найдутся такие целые числа и , что Умножая обе части на , получаем |
Основная теорема арифметики
| Теорема: |
Каждое натуральное число представляется в виде , где — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей. |
| Доказательство: |
|
Существование. Пусть — наименьшее натуральное число, неразложимое в произведение простых чисел, предполагая, что оно уже доказано для любого другого числа, меньшего . Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел (уже доказано ранее), значит, тоже является произведением простых чисел. Противоречие. Единственность. Пусть — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть — любой из сомножителей в любом из двух разложений. Если входит и в другое разложение, мы можем сократить оба разложения на и получить два разных разложения числа , что невозможно. А если не входит в другое разложение, то одно из произведений делится на , а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству. |
