Разложение на множители, основная теорема арифметики

Покажем, что наибольший простой делитель числа при указанных операциях не уменьшается, и потому мы никогда не получим число из составного числа, имеющего простой делитель, больший чем

Заметим, что наибольший собственный делитель составного числа делится на наибольший простой делитель этого числа. В самом деле, очевидно, что где — наименьший собственный (и наименьший собственный) делитель числа и, поскольку множитель должен остаться в разложении. В частности, если то это всё равно верно, поскольку тогда где

Поэтому если мы делим составное число на то получаем частное где — наименьший собственный делитель и множитель остаётся в разложении числа

Если же мы к числу прибавляем кратное его наименьшему собственному делителю то получаем число у которого наибольший простой делитель не меньше, чем наибольший простой делитель числа то есть не меньше