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

О: a,b Î Z, Z-кольцо , то a-делимое, b-делитель, q-частное

Св-ва: 1. . Д-во по опр . 2. Д-во: a=bq₁ b=cq₂, a=cq₁q₂=c(q₁q₂) и т. д. Опр: натур число n наз-ся простым если и не кратно никакому другому делителю. Опр: натур число наз-ся составным если n>1 и n имеет делители (хотя бы один) отличные от 1 и n. Единица не входит ни в разряд простых ни в разряд составных. В ряду простых чисел сущ-ет только одно четное число – 2. Т. о. Мн-во простых чисел разбито на 3 множ-ва: 1)единица; 2)простые (2,3,5,7,11,13,…); 3)составные (4,6,8,9,10,12,14,15,…).

Теор Евклида: (о бесконечности числа простых чисел). Множ-во положительных простых чисел бесконечно. Д-во: (от противного) предположим что множ-во простых чисел конечно, т. е. - простые, причем Р_n максимальное простое число. Составим произведение из всех простых чисел и прибавим 1. . Это натуральное число больше всех перечисленных, значит оно составное. Оно разлагается в произведение положительных простых чисел и поэтому обладает хотя бы одним положительным простым делителем p. Однако ни на Р₁, ни на Р₂, и т. д. оно не делится. Значит оно тоже простое. Пришли к противоречию с предположением. Множ-во простых чисел бесконечно.

Теор: любое натур число ≠1 м. б. Представлено в виде произведения простых множителей единственным образом. Д-во: n-составное. I.сущ-е. 1) n=4=2*2. 2) пусть утверждение верно для всех составных чисел и некоторого составного числа k. 3) n=k, т. к. k-составное, то n=k₁k₂, k₁k₂<n. Если k₁ и k₂ простые, то утверждение выполнено, если хотя бы одно из них составное, то его можно разложить на простые множители по предположению индукции. II.един-ть. (от противного)Пусть n=p₁p₂…p_k и n=q₁q₂…q_s, где p и q-простые

т. к. q₁-простое. Найдется какое-то . Т. к. p_i-простое, то . Пронумеруем множители левой части так, чтобы . Затем сократим на эти числа. Получим:

и p₂=q₂ и т. д. Докажем что k=s. Пусть k>s. Тогда на s-ом шаге получим: p_s+1…p_k=1, что невозможно. Так же док-ся случай если k<s. Значит k=s. Замечание: в разложении числа на множители простые множители могут повторяться. Их принято записывать в виде степени, полученную запись наз-ют канонической формой записи числа: . Пример: 588=2²*3*7². Решето Эратосфена: (способ нахождения простых чисел на промежутке 1..n) Суть: выписываются все числа от 2 до n. В этой послед-ти вычеркнем каждое второе число. Первое незачеркнутое число – это простое число 3. Далее вычеркнем каждое третье число после 3(причем надо считать и те числа, которые уже вычеркнуты ранее). Первое следующее за 3 невычеркнутое число – это простое число 5, и т. д. это вычеркивание продолжаем до тех пор пока не дойдем до первого простого числа, не меньшего Ön. Все числа оставшиеся незачеркнутыми будут простыми числами не превосходящие n.

Св-ва простых чисел: 1) наименьш. ≠1делитель натур. числа есть число простое. 2) наименьший делитель числа n не превосходит Ön. 3) простых б/м. 4) составных б/м. 5) различные простые числа взаимно просты. 6) если , где p-простое, то или . 7) если а-неизв. натуральн. число, р-простое число, то или (а,р)=1, или .