Процессы и алгоритмы

Давайте рассмотрим тривиальное () разложение на множителей. Пусть у нет простых множителей больших И будем делать следующее: если есть множитель больший и произведение каких-нибудь двух множителей то объединяем их в один, а потом раскладываем множитель больший на два не единичных (один из которых меньше Очевидно, что этот алгоритм закончится в силу того, что у конечное количество множителей. Теперь докажем, что когда алгоритм закончится, у нас все множители меньше Пусть не так. Тогда есть множитель больший при этом произведение любых двух больше, чем следовательно, все произведение хотя бы ( берется из того, что у нас есть множителей, попарные произведения которых больше а, значит, их произведение хотя бы Противоречие. Если же число имеет простой делители, которые хотя бы то поделим на них и будем действовать абсолютно аналогично, но для меньшего количества множителей. Пусть их было Тогда финальная оценка превращается в что легко понять больше, чем