math4school.okis.ru

 

σ (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. Для n > 1 функция φ (n) не учитывает само число n и мы имеем

φ (n) < n.

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

d₁ = 1 < d₂ < . . . < d_k = n.

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

d₂ < n  и  n – d₂ > 1.

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

n · d (n) – σ (n) = kn – ( d₁ + d₂ + . . . + d_k ) =

= (n – d₁) + (n – d₂) + . . . + (n – d_k) >

> (n – d₁) + (n – d₂) + (n – d_k) >

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

Эдвард Варинг
(ок. 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! = (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

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