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




Скачать 132.73 Kb.
НазваниеПростые числа
Дата публикации07.08.2013
Размер132.73 Kb.
ТипДокументы
zadocs.ru > Информатика > Документы
Определение 1.2.5 НОК целых чисел а1, а2,…, аn равносильно выполнению свойств 1–3.

4. Если НОК целых чисел существует, то оно единственное.

Пусть m, – два НОК целых чисел а1, а2,…, аn, n  2. По свойству 3 НОК  | m | = || по свойству 4 делимости целых чисел. Поскольку m,  N, то m = .

Очевидно, что если b | a, то [ab] = | a | при a  0.

C помощью рекурсии НОК вычисляется не только для двух, но и большего количества целых чисел: [a1,…, an  1, an] = [[a1,…, an  1], an], n = 3, 4,…

^

§1.3. Простые числа



Определение 1.3.1. Натуральное число p > 1 называется простым, если оно делится только на 1 и на само себя, в противном случае p называется составным. 1 не является ни простым, ни составным числом. Таким образом,

= {1}  {простые числа}  {составные числа}.

Очевидно, справедлива следующая теорема.

Теорема 1.3.1. Наименьший делитель p > 1 натурального числа n > 1 есть число простое, причем если n – составное число, то .

1. n – простое число .

2. n – составное число, пусть p – составное  ( t  N: , что противоречит минимальности делителя p.

Пусть теперь

Свойства простых чисел

1. Для  n  N и любого простого p

2. (p1p2) = 1, если p1  p2 – различные простые числа.

Заметим, что из соотношения натуральных чисел при n > 1, 1 < pq < n следует, что либо , либо принадлежит отрезку [2; ]. Истори-чески первый метод проверки числа n на простоту заключался в делении его на простые числа, не превосходящие . Если среди таких чисел делителей не найдено, то n – простое число. Это один из вариантов так называемого «реше-та» Эратосфена, ставшего его наиболее знаменитым достижением. Эратосфен (ок. 276–194 до н. э.) – один из самых разносторонних ученых Античности.

23, 4, 5, 6, 7, 8, 9, 10, 11, 12,…, [],

где [] – целая часть :

  1. 2 – простое число, исключаем все числа, кратные 2 (2 | n – да или нет?);

  2. 3 – простое число, исключаем все числа, кратные 3 (3 | n – да или нет?);

и т. д. до ближайшего к простого числа.

В целом «решето» Эратосфена решает более общую задачу нахождения всех простых чисел на отрезке натурального ряда [mn], где m < n.

Теорема 1.3.2 (Евклид). Простых чисел бесконечно много.

Пусть p1p2,…, pk, k  N, – все простые числа. Рассмотрим число N = p1  p2 … pk + 1. N не делится ни на одно из pi, , т. к. в противном случае для некоторого i pi | 1 (свойство делимости целых чисел 6), что невозможно. Поэтому N является либо новым простым числом, либо составным, в последнем случае существует отличное от всех pi простое число p, где p | N.

Значение простых чисел в том, что они, согласно теореме 1.3.1, являются составными «кирпичиками» всех натуральных чисел. Распределение простых чисел среди натуральных весьма непредсказуемо, о чем свидетельствуют следующие две теоремы. Теорема 1.3.3, доказанная в 1852 г. выдающимся русским математиком и механиком Пафнутием Львовичем Чебышевым (1821–1894), приводится здесь без доказательства.

Теорема 1.3.3 (П. Л. Чебышев). Между натуральными числами k и 2k, k > 1, обязательно найдутся простые.

Теорема 1.3.4. Для всякого натурального n существует отрезок , k  N, натурального ряда, все числа которого составные.

В самом деле, все следующие числа составные:

k = (n + 2)! + 2,…, k + n = (n + 2)! + 2 + n.

Действительно, k = 2  (3 … (n + 2) + 1),…, k + n = (n + 2)  (2 … (n + 1) + 1) (здесь m! = 1  2  3 … k для m  N, 0! = 1).

Несмотря на теорему 1.3.4, для x  N>2 количество (x) всех простых чисел, меньших x, подчинено достаточно равномерному закону.

Теорема 1.3.5 (Ж. Адамар, Ш. Ж. Валле-Пуссен).

.

Любопытным фактом является утверждение следующей теоремы, доказанной в 1737 г. выдающимся швейцарским математиком Леонардом Эйлером (1707–1783).

Теорема 1.3.6 (Л. Эйлер). Ряд из чисел, обратных прос-тым, – расходящийся.

Это означает, что сумма ряда равна +. Тем не менее, его частичная сумма по всем известным простым числам (их примерно 50 млн) меньше 4.

Теоремы 1.3.5 и 1.3.6 приведены здесь без доказательства.

Также широко известно применение простых чисел в криптографии – науке о методах шифрования данных. Для криптографических целей нужны большие простые числа длиной более 80–90 десятичных знаков. Такие числа заме-чательно подходят для этих целей, т. к., во-первых, они встречаются довольно часто: аппроксимация была найдена французским математиком Жаком Адама-ром (1865–1963) и бельгийским математиком Шарлем Жаном де ла Валле-Пуссеном (1866–1962), которые независимо друг от друга доказали в 1896 г., что простых чисел, меньших натурального числа x, (теорема 1.3.5). Во-вторых, различные вычисления с простыми числами (модульная арифметика) дают хорошие односторонние функции (эффективно вычислимые, для задачи инвертирования которых не существует эффективных алгоритмов), позволяющие зашифровать преобразованное в числовой вид сообщение. Например, произведение двух простых чисел – качественная односторонняя функция.

Большой интерес представляют простые числа вида 2p – 1, которые названы в честь открывшего их французского математика, физика, философа и теолога Марена Мерсенна (1588–1648). Мерсенн открыл числа вида 2p – 1 в результате поиска совершенных чисел (так называются натуральные числа, которые равны сумме всех своих делителей, меньших данного числа, например, 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248). Одним из преимуществ чисел вида 2p – 1, благодаря которому при проверке их на простоту происходит отсев показателей p, является то, что числа такого вида могут быть простыми только тогда, когда p – простое число. Но не для любого простого p число 2p – 1 является простым, например, 211 – 1 = 2047 = 23  89. При больших показателях p получаются огромные числа 2p – 1, поэтому все рекордные простые числа принадлежат классу чисел Мерсенна.

Французский математик Франсуа Эдуард Анатоль Люка (1842–1891) разработал методы для проверки чисел на простоту. В 1876 г. он доказал, что 2127 – 1 – простое число. Оно оставалось самым большим известным простым числом Мерсенна в течение 75 лет. Позже, в 1930 г., американский математик, профессор университета в Беркли Деррик Генри Лемер (род. в 1905 г.) продолжил работу Люка и получил тест проверки чисел Мерсенна на простоту, называемый теперь тестом Люка – Лемера.

Поиском простых чисел Мерсенна занимается проект GIMPS (Great Internet Mersenne Primes Search), действующий с 1996 г. Именно участники этого проекта последнее время находят новые большие простые числа Мерсенна. Инструментом поиска служит программа Prime95 основателя GIMPS Джорджа Вольтмана (род. в 1957 г.), последняя версия которой – v25.7, где и используется тест Люка – Лемера. Исходный текст этой программы открыт для изучения и представляет собой высокооптимизированный ассемблерный код.

Открытое в 1999 г. 38-е простое число Мерсенна являлось самым большим простым числом на конец XX в. – это число 26972593 – 1, которое содержит 2098960 десятичных знаков. После этого было открыто еще девять больших простых чисел Мерсенна. По состоянию на конец 2009 г. самым большим из них является открытое в августе 2008 г. 45-е число 243112609 – 1, содержащее 12978189 десятичных знаков, последним из найденных является открытое в ап-реле 2009 г. 47-е число 242643801 – 1, содержащее 12837064 десятичных знака.

Обобщением теоремы 1.3.2 является следующая теорема, доказанная в 1837 г. известным немецким математиком, внесшим существенный вклад в математический анализ, теорию функций и теорию чисел, Петером Густавом Ле-женом-Дирихле (1805–1859), приводимая здесь без доказательства.

^ Теорема 1.3.7 (П. Дирихле). Всякая арифметическая прогрессия {a + + b  n | n  Z0}, где a, b – фиксированные натуральные числа и (ab) = 1, содержит бесконечно много простых чисел.

К сожалению, больше в теории чисел результатов, аналогичных теореме 1.3.7, нет. До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены немецким математиком Эдмундом Георгом Германом Ландау (1877–1938) на V Международном математическом конгрессе в 1912 г.

^ Первая проблема Ландау, известная еще как проблема Гольдбаха (Крис-тиан Гольдбах (1690–1764), немецкий математик): доказать или опровергнуть, что каждое четное число, большее 2, может быть представлено в виде суммы двух простых чисел, а каждое нечетное число, большее 5, может быть представлено в виде суммы трех простых чисел. Вторая проблема Ландау: беско-нечно ли множество простых чисел-близнецов (чисел типа p и p + 2, например, 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31,…, 1997 и 1999 и т. д.)? Третья проблема Ландау, известная также как гипотеза Лежандра (Адриен Мари Лежандр (1752–1833), французский математик): верно ли, что между n2 и (n + 1)2 всегда найдется простое число? Четвертая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?

Открытыми проблемами являются бесконечность множества простых чисел Мерсенна, а также чисел Ферма и чисел-значений многочлена Эйлера , n = 0, 1, 2,... Еще известный французский математик Пьер де Ферма (1601–1665) показал, что , , , , – простые числа, и выдвинул гипотезу, что все числа такого вида простые. Однако эта гипотеза была опровергнута в 1732 г. Леонардом Эйлером, нашедшим разложение числа на простые множители: и больше простых чисел вида Fn найдено не было. При n = 0, 1, 2, 3,…, 39 многочлен g(n) дает число простое, однако больше простых чисел такого вида не найдено, например, g(40) = 412.

^

§1.4. Взаимно простые числа. Основная теорема арифметики



Определение 1.4.1. Целые числа называются взаимно простыми, если .

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

Теорема 1.4.1 (критерий взаимной простоты). Целые числа взаимно просты тогда и только тогда, когда существуют такие целые числа , что

.

Необходимость. , из соотношения Безу для НОД следует, что , такие, что .

Достаточность. Пусть , такие, что . Если , то d | 1 (в силу свойства 5 делимости целых чисел), следовательно, d = 1.

Свойства взаимно простых чисел

1. .

Необходимость. Согласно следствию из теоремы 1.2.3 , такие, что , следовательно, , зна-чит, по теореме 1.4.1.

Достаточность. , следовательно, , такие, что (согласно теореме 1.4.1), откуда d = u1a1 +…+ + unan. Значит, по свойству 5 делимости целых чисел, а поскольку , то по определению НОД, следовательно, .

2. с | ab  (ca) = 1  с | b.

При b  0  tuv  Z, такие, что ab = ctcu + av = 1  cub + ctv = b   с | b по свойству 5 делимости целых чисел. При b = 0 доказательство очевидно согласно свойству 1 делимости целых чисел.

3.   .

Необходимость.



где . Значит, согласно теореме 1.4.1.

Достаточность. Пусть . Если предположить, что или , то согласно свойству 3 делимости целых чисел и определению НОД получим, что либо . Это противоречит тому, что . Значит,   .

4. Следствие из свойства 3. Простое число p делит произведение , k  N, тогда и только тогда, когда , 1  i  k, со свойством .

Необходимость. Если с указанным свойством, то по свойству 1 простых чисел , значит, по свойству 3 взаимно простых чисел, следовательно, снова по свойству 1 простых чисел, что приводит к противоречию. Итак, , 1  i  k, со свойством .

Достаточность. Если , 1  i  k, со свойством , то по свойству 3 делимости целых чисел.

С помощью свойств взаимно простых чисел и метода математической индукции доказывается следующая важная теорема.

Теорема 1.4.2 (основная теорема арифметики). Всякое натуральное число n > 1 однозначно раскладывается в произведение простых чисел с точностью до порядка следования множителей:

, . (1.4.1)

n = 2 – база индукции. Предположим, что утверждение верно для .

Для простого числа n доказательство очевидно, s = 1. Пусть – составное число, . Воспользуемся предположением индукции и разложим на простые множители и , тем самым в произведение простых чисел будет разложено и n.

Пусть и , st  N, – два разложения числа n на простые множители. Тогда, воспользовавшись свойством 4 взаимно простых чисел и свойством 1 простых чисел и последовательно сокращая обе части равенства  =  на , приходим к выводу, что s = t и с точностью до порядка следования множителей , . Таким образом, разложение (1.4.1) числа n однозначно с точностью до порядка следования множителей.

Определение 1.4.2. Если в равенстве (1.4.1) собрать одинаковые множители в степени, то получим каноническое разложение натурального числа n > 1: , где , , при i  j. Если z – целое, не равное 0, 1 число, то каноническое разложение .

Пример 1.4.1. Найдем разложения вида (1.4.1) и канонические разложения целых чисел.

1. – 484 = – 2  242 = – 2  2  121 = – 2  2  11  11 = – 22  112.

2. 212 – 1 = 4095 = 3  1365 = 3  3  455 = 3  3  5  91 = 3  3  5  7  13 = = 32  5  7  13.

По каноническому разложению целых чисел легко находятся их НОД и НОК, решаются иные задачи.

Пусть – ненулевые целые числа, хотя бы одно из которых отлично от . Запишем их канонические разложения:

, , , , ,

где p1,…, pt – простые числа, входящие во все разложения , , причем в случае отсутствия множителя pj в разложении полагается ij = 0. Тогда, исходя из определений, получаем следующие формулы для канонических разложений НОД и НОК чисел :

, где , ,

, где , .

Добавить документ в свой блог или на сайт

Похожие:

Простые числа iconПрограмма вступительных испытаний по математике
Натуральные числа и ноль. Сложение, вычитание, умножение натуральных чисел. Квадрат и куб числа. Простые и составные числа. Разложение...

Простые числа iconПрограмма вступительных испытаний по учебному предмету «Математика»
Квадрат и куб натурального числа. Простые и составные числа. Делитель, кратное. Четные и нечетные числа. Признаки делимости на 2,...

Простые числа iconЗдрава
Цель этого пособия – в явном виде показать те простые принципы, на которых базируется здоровье. Обратить внимание на богатство возможностей,...

Простые числа iconВопросы к зачету по курсу «Алгебра и теория чисел»
Комплексные числа. Пары действительных чисел. Точки плоскости. Алгебраическая форма. Тригонометрическая форма. Действительная и мнимая...

Простые числа icon5. Комплексные числа
В процессе развития математики потребовалось дополнительно к известным действительным числам ввести числа нового рода. Они называются...

Простые числа iconПрограмма экзамена по дисциплине “Математика”, 4-й семестр
Модуль и аргумент комплексного числа. Тригонометрическая и показательная форма записи комплексного числа

Простые числа iconВопросы к экзамену по линейной алгебре 2012г. Преподаватель: Авдеев Иван Федорович
...

Простые числа iconЭкзаменационные вопросы по дисциплине Математика для студентов 1...
Целые и рациональные числа. Приближение действительных чисел. Действительные числа

Простые числа icon1. Числа точные и приближённые
При обработке физического эксперимента надо различать точные и приближённые числа

Простые числа icon1 Представление числа в ЭВМ. Зависимость машинной точности от формата...
Обозначим через X точное, а через x~ приближенное значения величины. Тогда ошибка будет равна x-x~, а неотрицательную величину |x-x~|...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов