Простые и составные числа. Решето Эратосфена.

Определение. Натуральное число >1 называется простым если оно имеет ровно два делителя единицу и само это число.

Например, 2,5,11 и т.д.

Определение. Натуральное число >1 называется составным если оно имеет более двух делителей.

Например 12,14.

Число единиц имеет один делитель его не относят не к простым не к составным числам.

Число 0 имеет бесконечно много делителей. Его не относят ни к простым ни к составным числам.

2,3,4,5,6,7,8,9,10

11,12,13,14,15,16,17,18,19,20

21,22,23,24,25,26,27,28,29,30

31,32,33,34,35,36,37,38,39,40

остались простые числа которые делятся на себя и единицу.

Греческий математик и астроном Эратосфен живший в Александрии в 3 веке до н.э. придумал составление таблицы в которой указаны простые числа. Его метод заключается в следующем сначала выписываются все натуральные числа от 2 до n после этого вычеркивают все числа кратные 2, кроме самого числа 2, затем первым оставшимся числом после 2 является 3 вчеркиваются все числа кратные 3, кроме самого числа 3 и т.д.

Простое число — это число, у которого только два делителя: 1 и само число.

Например: 13 (1 * 13 = 13); 457 (1 * 457 = 457)

Натуральное число > 1назыв. составным, если оно имеет более двух делителей (12,14,16).

Число 0 и 1 не относят ни к простым, ни к составным числам.

Решето Эратосфена

этим именем называют следующий способ получения ряда простых чисел.

Из ряда чисел 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14...

вычеркивают кратные двум;

4, 6, 8, 10, 12,...

— кратные трем:

6, 9, 12, 15,...

— кратные пяти:

10, 15, 20, 25, 30,...

— кратные семи:

14, 21, 28, 35, 42, 49,...

и т. д.

Таким образом все составные числа будут просеяны, и останутся только простые числа 2, 3, 5, 7, 11, 13...

Наибольший общий делитель (НОД), наименьшее общее кратное(НОК).

Общим делителем натуральных чисел а и в назыв. всякое натуральное число явл-мся делителем каждого из данных чисел. Наибольшее число из всех делителей чисел а и в называется наибольшим общим делителем данных чисел. Обозначается К (а,в)

Общим кратным натуральных чисел а и в называется число, которое кратно каждому из данных чисел. Наименьшее число из всех общих кратных чисел а и в называется наименьшим общим кратным этих чисел. Обозначается К (а,в) (напр. общее кратное чисел 5 и 7 явл. 35,70, 140. НОК 35)

Или

Общий делитель нескольких чисел – это число, которое является делителем для каждого из этих чисел. Например, общими делителями чисел 24, 30 и 18 являются числа 2, 3 и 6.

Наибольший общий делитель (обозначается НОД) – это наибольшее число из общих делителей. Например, НОД (24, 30,18) = 6.

Общее кратное нескольких чисел – это число, которое является кратным каждому из этих чисел. Например, для чисел 3 и 6 общими кратными являются 12, 24, 36 и т.д.

Наименьшее общее кратное (обозначается НОК) – это наименьшее из общих кратных. Наименьшее общее кратное чисел (НОК) – это такое минимальное число, которое делится без остатка на каждое из этих чисел.

Например, НОК (3,6) = 6, НОК (24,30,18) = 360.

НОД и НОК можно найти, применяя разложение чисел на простые множители.

Для НОД нужно выписать все множители, которые входят в разложения данных чисел. Затем каждый такой множитель следует взять с наименьшим показателем, с которым он входит во все данные числа, после чего нужно произвести умножение.

Например,

24 = 2 · 2 · 2 · 3 = 23 · 3.

30 = 2 · 3 · 5

18 = 2 · 3 · 3 = 2 · 32

В нашем примере множители, которые входят в разложение каждого числа – это 2 и 3. Их минимальная степень – это единица.

Тогда НОД (24,30,18) = 2 · 3 = 6.

Если НОД (a, b) = 1, то числа a и b называют взаимно простыми. Например, числа 15 и 8 являются взаимно простыми, хотя каждое из них – составное.

Для определения НОК нужно выписать все множители, которые встречаются хотя бы в одном из разложений данных чисел. Затем каждый такой множитель следует взять с наибольшим показателем, с которым он входит в одно из чисел, после чего нужно произвести умножение.

Например,

24 = 2 · 2 · 2 · 3 = 23 · 3.

30 = 2 · 3 · 5

18 = 2 · 3 · 3 = 2 · 32

В нашем примере множители, которые входят в разложение каждого числа – это 2, 3 и 5. Их максимальные степени – это соответственно 3,2 и 1.

Тогда НОК (24,30,18) = 23 · 32 · 5 = 360.

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

Любое составное число можно единственным образом представить виде произведения простых множителей.

Каждое натуральное число представляется в виде , где суть простые числа, причём такое представление единственно с точностью до порядка следования сомножителей. Основная теорема арифметики/рамка Единицу можно также считать произведением нулевого количества простых чисел, «пустым произведением».

Как следствие, каждое натуральное число единственным образом представимо в виде , где — простые числа, и — некоторые натуральные числа.

Следствия теоремы

Основная теорема арифметики даёт элегантные выражения для наибольшего общего делителя и наименьшего общего кратного.

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

Доказательство основной теоремы арифметики опирается на так называемую лемму Евклида:

сли простое число p делит без остатка произведение двух целых чисел x·y, то p делит x или y. Основная теорема арифметики/рамка

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

Единственность. Пусть n — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть p — любой из сомножителей в любом из двух разложений. Если p входит и в другое разложение, мы можем сократить оба разложения на p и получить два разных разложения числа n/p, что невозможно. А если p не входит в другое разложение, то одно из произведений делится на p, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.