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

Эта статья находится в разработке!

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]