Теорема (О единственности разложения на произведение простых чисел)

, а>1 существует единственное разложение a=p₁∙p₂∙…∙p_n, где , р_i – простое .

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

Действительно, обозначая буквой p₁ наименьший (простой) делитель а, имеем a=p₁a₁ Если a₁>0, то, обозначая p₂ наименьший (простой) делитель числа a₁, имеем a₁=p₂a₂ и т.д., пока не придем к a_n=1 для некоторого n (поскольку ряд a₁, a₂, …, a_n - убывающий ряд натуральных чисел, то рано или поздно мы придем к единице).

Тогда a=p₁∙p₂∙…∙p_n. Показали существование разложения на простые сомножители. Теперь докажем единственность.

Предположим, что для того же самого а существуетвторое разложение на простые сомножители a=q₁∙q₂∙…∙q_s, и, не нарушая общности, предположим, что s≥n. Тогда

p₁∙p₂∙…∙p_n = q₁∙q₂∙…∙q_s *

В силу основного свойства простых чисел, q₁\( p₁∙p₂∙…∙p_n) i: q₁\p_i. Не нарушая общности, предположим, что i=1 q₁\p₁. В силу простоты чисел p₁, q₁, получим p₁=q₁. Сократив обе части равенства (*) на q₁, получим

p₂∙…∙p_n = q₂∙…∙q_s,

p₁=q₁

Повторив рассуждения для q₂, получим

p₃∙…∙p_n = q₃∙…∙q_s,

p₁=q₁, p₂=q₂

И т.д. В итоге получим

1=q_n+1∙…∙q_s,

p₁=q₁, p₂=q₂, … , p_n=q_n

Отсюда q_n+1=1, …, q_s=1. То есть оба разложения на простые сомножители тождественны.

□

В разложении числа на простые сомножители некоторые из сомножителей могут повторяться. Обозначая p₁,…, p_k различные из них, а α₁,…, α_k – кратности их вхождения в разложение, получим каноническое разложение числа а:

Добавим, что задача разложения числа на простые сомножители, или, иначе, задача факторизации, считается сложной задачей, поскольку известные алгоритмы факторизации имеют экспоненциальную или субэкспоненциальную сложность. Ознакомиться с такими алгоритмами можно будет в гл. 2 настоящего пособия.