НОК (наименьшее общее кратное)

Если a1\b, a2\b, … , an\b, то b называется общим кратным чисел a1,…,an. Наименьшее положительное общее кратное чисел a1,…,an называется их наименьшим общим кратным (НОК).

Пусть НОД(a,b)=d, тогда можно записать a=d∙a1, b=d∙b1, где (a1,b1)=1.

Пусть a\M, b\M M=ak для некоторого целого k, и тогда число – целое. Но, поскольку (a1,b1)=1, то b1\k , и тогда k=b1t для некоторого , и

. *

Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных.

При t=1 имеем M=НОК(a,b).

Формулой M = НОК(a,b)∙t можно представить все общие кратные чисел a и b. ( ).

 

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

Числа a1,…,an называются взаимно простыми, если НОД(a1,…,an)=1, попарно простыми, если , НОД(ai,aj)=1.

Если числа попарно a1,…,an простые, то они взаимно простые. Обратное неверно.

Число p называется простым, если оно имеет лишь два делителя – “1” и р.

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

Число а>1 имеющее более двух делителей, называется составным.

Утверждение 1

Наименьший не равный единице делитель числа a: , >1, является простым числом.

Доказательство:
Пусть q: q>1, q\a – наименьший делитель а. Если бы q было составным, то нашлось бы число q1>1: q1\q, и тогда для некоторого целого k выполнялось бы q=kq1 a=qt=q1kt q1\a, q1<q (то есть нашелся делитель числа a, который меньше q) q – не наименьший делитель числа a. Пришли к противоречию с условием теоремы. Предположение неверное, следовательно верно обратное. q – простое число.

Утверждение 2

p – наименьший делитель составного числа а, p≠1 .

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

Представим a в виде a=pa1. Поскольку p – наименьший делитель числа a, то a1p ap2 в силу монотонности квадратичной функции на положительной полуоси, p .

Теорема Евклида (о простых числах) №1

Простых чисел бесконечно много.

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

Пусть простых чисел ровно k штук, и p1,…,pk – все простые числа.

Возьмем n=p1p2∙…∙pk+1. По предположению, n – составное число, т.к. n> , существует простое число d: d\n.

Но очевидно, исходя из вида числа n, что , получили противоречие с тем, что p1,…,pk – все простые числа.

 

Теорема Евклида (о простых числах) №2

в числовом ряду (1, 2, 3, …) существует k подряд идущих составных чисел.

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

Возьмем m=k+1.

m!+2, m!+3,…, m!+m – составные числа, и их ровно k штук.

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

Решето Эратосфена используется для составления таблицы простых чисел, меньших или равных наперед заданного натурального числа N.

1. Выписываем числа 1 2 3 … N

2. Первое число, которое больше, чем 1, есть 2. Двойка делится только на 1 и 2, т.е. является простым числом.

Вычеркиваем из ряда (как составные) все числа, кратные 2, кроме самой двойки.

3. Второе невычеркнутое число есть 3. Оно не делится на 2, иначе оно оказалось бы вычеркнутым, значит 3 делится только на 1 и 3, значит 3 – простое число.

Вычеркиваем из ряда все числа, кратные 3.

4. Следующее невычеркнутое число есть 5. Оно простое, так как не делится ни на одно число, меньшее самого себя, иначе оно было бы вычеркнуто. Вычеркиваем все числа, кратные 5, кроме самой пятерки.

Этот процесс продолжаем далее для всех невычеркнутых чисел.

Когда этим способом вычеркнуты все числа, меньшие p (p – простое), то все невычеркнутые числа, меньшие p2, будут простыми.

Действительно, всякое составное а<p2 уже вычеркнуто, как кратное его наименьшего делителя d: a=da1 который d <p (по утверждению 2).

Тогда следуют правила:

1. Числа, кратные р, вычеркиваются, начиная с p2.

2. Составление таблицы простых чисел, меньших или равных N, закончено, как только вычеркнуты все кратные простых, меньших или равных

Пример: N=50 .

1 2 3 45 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 41 42 43 44 45 46 47 48 49 50

 








Дата добавления: 2015-11-28; просмотров: 1365;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.