Изменения

Перейти к: навигация, поиск

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

36 байт убрано, 08:55, 29 сентября 2010
Лемма Евклида
|id=th1
|statement=
Если простое число <mathtex>p</mathtex> делит без остатка произведение двух целых чисел <mathtex>x\cdot y</mathtex>, то <mathtex>p</mathtex> делит <mathtex>x</mathtex> или <mathtex>y</mathtex>.
|proof=
Пусть <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>, ч.т.д.
}}
153
правки

Навигация