Math    schooL

 

 

Два условия простоты чисел

 

Два условия простоты чисел

σ (n) + φ (n) = n · d (n)

Часто отмечают, что замечательное равенство еπi + 1 = 0 связывает пять самых важных во всей математике чисел. Лишь немного уступает ему равенство

σ (n) + φ (n) = n · d (n),

связывающее три наиболее важные функции элементарной теории чисел, где

σ (n) – сумма положительных делителей числа n,

d (n) – количество положительных делителей числа n,

φ (n) – функция Эйлера, равная количеству натуральных чисел m < n, взаимно простых с числом n, то есть НОД (m, n) = 1.

Конечно, можно соединить любые функции, какие мы хотим, придумав соответствующее математическое соотношение. Однако докажем тот удивительный факт, что 

соотношение σ (n) + φ (n) = n · d (n) является необходимым и достаточным условием того, что n – простое число. 

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

Необходимость. Предположим, что n простое число. Тогда делителями n является 1 и n и поэтому 

σ (n) = n + 1,

φ (n) = n – 1,

d (n) = 2.

В этом случае 

σ (n) + φ (n) = 2n = n · d (n),

σ (n) + φ (n) = n · d (n). 

Следовательно, выполнение этого условия необходимо.

Достаточность. Предположим, что 

σ (n) + φ (n) = n · d (n)

и что n – не простое число. Соотношение не выполняется для п = 1: 

1 + 1 ≠ 1 · 1. 

Будем считать, что n > 2. Для > 1 функция φ (n) не учитывает само число n и мы имеем

φ (n) < n.

Так как n составное число, то оно имеет не менее трех делителей. Обозначим d (n) через k, а положительные делители числа n через

d1 = 1 < d2 < . . . < dk = n.

Так как k = d (n) > 3, то делитель d2  не является наибольшим делителем, поэтому

d2 < n  и  nd2 > 1.

Следовательно, получаем

n · d (n) – σ (n) = kn – ( d1 + d2 + . . . + d) =

(nd1) + (nd2) + . . . + (ndk) >

> (nd1) + (nd2) + (ndk) >

> (n – 1) + 1 + 0 = n > φ (n);

тем самым мы показали невозможность условия

n · d (n) σ (n) = φ (n).

Полученное противоречие показывает, что n – не является простым числом.

 

Теорема Вильсона 

Возможно, что самым знаменитым условием простоты числа является теорема Вильсона: 

Число n является делителем числа (n – 1)! + 1 тогда и только тогда, когда n – простое число. 

Теорема Вильсона в значительной мере имеет теоретическое значение, поскольку довольно трудно вычислить (n–1)!. Проще вычислить an–1, поэтому элементарные тесты, определяющие является ли число простым, основаны не на теореме Вильсона, а на малой теореме Ферма:

Если n – простое число и a – целое число, не делящееся на n , то an–1 1 делится на n (другими словами an–1 при делении нацело на n даёт в остатке 1).

Например, наибольшее простое число, найденное используя теорему Вильсона, – 1099511628401, и даже с умным подходом к расчету n!, потребуется около суток вычислений на процессорах SPARC. Но числа с десятками тысяч цифр, проходят тест на простоту с использованием теоремы Ферма, меньше чем за час.

Однако, в отличие от малой теоремы Ферма, теорема Вильсона является одновременно необходимым и достаточным условием простоты числа.

Теоремы Ферма и Вильсона можно соединить в одну следующую теорему:

Если n – простое число, то для любого целого числа а число an + a · (n – 1)! делится на n.

Теорема Вильсона впервые была сформулирована  в 1770 году видным английским математиком XVIII века, членом Лондонского королевского общества, доктором медицины и профессором математики Кембриджского университета Эдвардом Варингом.  

Эдвард Варинг, Эдуард Уоринг (ок. 1734—1798)

Эдвард Варинг
(ок. 1734—1798)

 

В своем сочинении "Meditationes Algebraicae", опубликованном в Кембридже, он приводит без доказательства теорему Вильсона. По его словам, теорема принадлежит некоему его ученику, Вильсону. Собственное доказательство этой теоремы Варинг опубликовал только в 1782 году. Первое же доказательство теоремы Вильсона дал французский математик Жозеф Луи Лагранж в 1771 году. 

 

Теорема Вильсона в действии

В 1965 году журнал "American Mathematical Monthly" напечатал следующую задачу, принадлежащую Дугласу Линду и решенную Кеннетом Крамером и Стевеном Минскером: 

Докажите,   что   число   n   является   делителем   числа 

N = 1 · 1! + 2 · 2! + 3 · 3! + . . .  + (n – 3) · (n – 3)!

тогда и только тогда, когда n – простое число. 

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

· r! = (r + 1) · r! – r! = (r + 1)! – r!,

то

N = (2! – 1!) + (3! – 2!) + (4! – 3!) + . . . + ((n – 2)! – (n – 3)!) = (n – 2)! – 1.

Умножив на n – 1 и прибавив n к обеим частям равенства, получим

(n – 1) · N + n = (n – 1)! + 1.

По теореме Вильсона n – простое число в том и только том случае, если n является делителем числа

(n – 1)! + 1,

а последнее соотношение является верным тогда и только тогда, если n есть делитель числа N, так как числа n и (n – 1) взаимно просты. 

 

Источники: Р. Хонсбергер. Математические изюминки (Москва, "Наука", 1992), В. Серпинский. Что мы знаем и чего не знаем о простых числах (Москва, Ленинград "Государственное издательство физико-математической литературы", 1963) и Википедия.

 

  <<< Назад

 

     Смотрите так же:

Бесконечность ряда простых чисел

Созвездия простых чисел

Таблица простых и парных простых чисел, не превосходящих 10000

Задачи математических олимпиад. Простые и составные числа

 

Нам 4 года!

14 марта 2016 года сайту Математика для школы|math4school.ru исполнилось 4 года. Поскольку число 4 для нашего сайта не чужое, мы решили подвести некоторые итоги.

Новый формат главного меню

Расширены функциональные возможности главного меню.

Галерея на сайте math4school.ru
Приглашаю посетить Галерею, – новый раздел на сайте.

444 года со дня рождения Иоганна Кеплера

27 декабря 2015 года исполнилось 444 года со дня рождения Иоганна Кеплера.

Новый раздел на сайте math4school.ru

Закончена работа над новым разделом сайта Работа над ошибками.

Союз образовательных сайтов