Простые и составные числа. Бесконечность множества целых чисел. Каноническое разложение составного числа и его единственность

4. Простые и составные числа. Для каждого x ∈Z + рассмотрим множество Dx = {d ∈ Z + | 1 <d,d | x} ⊂ Z +.

Определение 2.2. Число x ∈Z +, x > 1, называетсяпростым, если Dx = {x}, и составным в противном случае.

Число наз-сяпростым если делится тока на себя и 1., числа которые кроме себя и 1 имеют еще положительные делители наз-ся составными.

Примеры простых чисел: 2, 7, 11, 97 и т. д

 

Теорема Евклида: е сли простое число делит произведение двух целых чисел, то оно делится хотя бы на одно из этих чисел.

Мн-во простых чисел яв-сябесконечным.

 

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

Пусть переменная p изначально равна двум — первому простому числу.

Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)

Найти первое не зачеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Теперь все не зачеркнутые числа в списке — простые.

 

Основная теорема арифметики каждое натуральное число n > 1 представляется в виде n = p1 ·.... · pk, где p1,...., pk — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

 

Доказательство основной теоремы арифметики опирается на так называемую лемму Евклида: если простое число p делит без остатка произведение двух целых чисел x · y, то p делит x или y.

 

Докажем существование такого разложения. Докажем существование от противного. Предположим, существуют числа >1, для которых такого разложения не существует. Тогда пусть n — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа себя. Если n составное, то оно — произведение двух меньших натуральных чисел. Поскольку они меньше n, то каждое из них, согласно условию выше, можно разложить в произведение простых чисел, значит, n тоже является произведением простых чисел. Противоречие. ЧиТД

Например, 24=2*2*2*3.Например, 24=2*2*2*3.

.

 

 

Из основной теоремы арифметики следует, что все делители числа nможно записать в виде

n=p₁^β₁…p_k^β_k

где 0<β₁<α₁… 0<β_k<α_k

Из этой теоремы также вытекает и второй способ нахождения НОД и НОК. Предположим, что числа а и b представлены в виде:

B= p₁^β₁…p_k^β_kиа=p₁^α₁…p_k^α_k

 

Здесь к каноническому представлению числаа приписаны в нулевой степени те простые числа, которые входят в каноническое представление числа b, но не входят в представление числа а. Соответственно то же проделано с каноническим представлением числа b. Тогда НОД (ab)=p₁^y₁...p_k^y_k,y_i=min(α_iβ_i) 1<i<k

 

НОК (ab)= p₁^δ₁...p_k^δ_k,),δ_j=max(α_jβ_j) 1<j<k

 

Любое натуральное число «n» можно представить в виде произведения простых

сомножителей с натуральными степенями. Например:

12=3 ˙ 2 ˙ 2=22 ˙ 31; 15=31 ˙ 51; 27=3 ˙ 3 ˙ 3=33; 7=71.

Запись вида: n = p₁^k1 ˙ p₂^k2 ˙… ˙ p_m^km,

где pi– простые числа, ki– натуральные числа, i=1; 2; 3;...; m – называется каноническим

разложением натурального числа «n».

Например, N = 10500.

10500: 2 = 5250; 5250: 2 = 2625. Это число больше не делится на 2

нацело. Делим его на 3. 2625: 3 = 875. Это число на 3 нацело не делится.

Делим его на 5. 875: 5 = 175. Еще раз делим на 5. 175: 5 = 35. Еще раз

делим на 5. 35: 5 = 7. Число 7 – простое число, поэтому окончательно

имеем в каноническойформе: 10500 = 2^2*3^1*5^3*7^1.