Основная теорема арифметики (2)

 2016-11-01 19:00:00      

Назад ко всем статьям

Мы продолжаем сюжет про основную теорему арифметики! На этот раз мы её докажем. И попутно узнаем, что же это такое.

Основная теорема арифметики:

Каждое натуральное число n>1 представляется в виде n=p1...pk, где p1, ..., pk — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Лемма Евклида:

Если простое число p делит без остатка произведение двух целых чисел xy, то p делит x или y.

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

Пусть xy делится на p, но x не делится на p. Тогда x и p — взаимно простые, следовательно, найдутся такие целые числа u и v, что

x u+p v=1 (соотношение Безу). 

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

(x y) u + p v y=y. 

Оба слагаемых левой части делятся на p, значит, и правая часть делится на p.

Доказано.

Перейдём к доказательству теоремы. Оно состоит из двух частей - существования разложения и единственности оного.

Существование.

Пусть n — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если n составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, n тоже является произведением простых чисел. Противоречие.

Единственность.

Пусть n — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть p — любой из сомножителей в любом из двух разложений. Если p входит и в другое разложение, мы можем сократить оба разложения на p и получить два разных разложения числа n/p, что невозможно. А если p не входит в другое разложение, то одно из произведений делится на p, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.

Доказано.

Итак, мы доказали основную теорему арифметики.