Простые числа

• Определение, примеры.
• Формула простого числа
• Способы проверки
• Решето Эратосфена
• Бесконечность ряда простых чисел

Составные числа

• Определение

• Разложение на множители

• Признаки делимости

• НОД

• НОК
   

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

Каждое отличное от 1 натуральное число может быть разложено в произведение простых чисел. Такое разложение единственно, если не обращать внимание на порядок множителей.

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

1) Возможность разложения на простые множители: Возьмем некоторое число N>1. Его наименьший отличный от 1 делитель есть, как указано выше, простое число. Обозначим этот делитель p₁, тогда N=n₁ +p₁. Если n₁ >1, то наименьший отличный от 1 делитель числа n₁ также будет простым числом. Обозначив его p₁, найдем n₁=p₂*n₂, где n₂- натуральное число и    N=p₁*p₂*n₂.

   Продолжая этот процесс, мы получим убывающую цепочку составным чисел.

n₁>n₂>n₃>...

   и последовательность простых чисел p₁, p₂, p₃..., таких, что

N=p₁*p₂*...*p_k

    Итак, мы доказали возможность такого разложения.

2) Единственность разложения на простые множители: Допустим, что существуют представления в виде произведения простых чисел разными способами. Выберем среди них самое маленькое и обозначим  его буквой N. Для числа N  возможны 2 различных представления

N=p₁*p₂*...*p_r=q₁*q₂*...*q_s

    где p₁, p₂..., p_r, q₁, q₂..., q_s- простые числа. Все числа q₁, q₂..., q_s отличные от p_r. Действительно, если, например, q₁=p₁, то, разделив равенство 

N=p₁*p₂*...*p_r=q₁*q₂...*q_s

на p₁, получим

M=p₂*...*p_r=q₂...*q_s

и число M, меньшее, чем N, представляется различными способами в виде произведения простых чисел. Но мы обозначили буквой N самое маленькое число с этим свойством. Значит, действительно, все числа q₁, q₂..., q_s отличны от p₁ и, следовательно, взаимно просты с p₁, т. е.

( p₁)=(q₁, p₁)=...=(q_s, p₁)=1.

     Произведение q₁*(q₂*...*q_s)=N делится на p₁ и (q₁, p₁)=1. По свойству делимости заключаем, что на p₁ делится произведение q₂*q₃*...*q_s=q₂(q₃*...*q_s). Но множитель q₂ также взаимно прост с p₁. Опять, пользуясь свойством делимости, заключаем, что произведение q₃*...*q_s делится на p₁ и т. д. В конце концов придем к заключению, что q_s делится на p₁. Но ведь q_s и p₁- различные простые числа и такого быть не может. Это означает, что наше первоначальное допущение неверно и равенство

N=p₁*p₂*...*p_r=q₁*q₂*...*q_s

возможно, только если r=s и правая часть получена перестановкой сомножителей из левой части. Основная теорема арифметики доказана.