Изменения

{{В разработке}} ==Эквивалентность двух определений простых чисел== ==Основная теорема арифметики== ===Лемма Евклида===

Если простое число <mathtex>p</mathtex> делит без остатка произведение двух целых чисел <mathtex>x\cdot y</mathtex>, то <mathtex>p</mathtex> делит <mathtex>x</mathtex> или <mathtex>y</mathtex>.

Пусть <mathtex>x\cdot y</mathtex> делится на <mathtex>p</mathtex>, но <mathtex>x</mathtex> не делится на <mathtex>p</mathtex>. Тогда <mathtex>x</mathtex> и <mathtex>p</mathtex> — взаимно простые, следовательно, найдутся такие целые числа <mathtex>u</mathtex> и <mathtex>v</mathtex>, что: <mathtex>x\cdot u+p\cdot v=1</mathtex> ([[Наибольший общий делитель|соотношение Безу]]).Умножая обе части на <mathtex>y</mathtex>, получаем: <mathtex>(x\cdot y)\cdot u+p\cdot v\cdot y=y.</mathtex>Оба слагаемых левой части делятся на <mathtex>p</mathtex>, значит, и правая часть делится на <mathtex>p</mathtex>, ч.т.д.

===Собственно Основная теорема=арифметики==

Каждое натуральное число <mathtex>n>1</mathtex> представляется в виде <mathtex>n=p_1\cdot\dots\cdot p_k</mathtex>, где <mathtex>p_1,\dots,p_k</mathtex> — [[простые числа]], причём такое представление единственно с точностью до порядка следования сомножителей.

'''Существование'''. Пусть <mathtex>n</mathtex> — наименьшее натуральное число, неразложимое в произведение простых чисел, предполагая, что оно уже доказано для любого другого числа, меньшего <tex>n</tex>. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если <mathtex>n</mathtex> составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел(уже доказано ранее), значит, <mathtex>n</mathtex> тоже является произведением простых чисел. Противоречие.'return'

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