Часто отмечают, что замечательное равенство еπ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)
Часто отмечают, что замечательное равенство еπ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 через
d1 = 1 < d2 < . . . < dk = n.
Так как k = d (n) > 3, то делитель d2 не является наибольшим делителем, поэтому
d2 < n и n – d2 > 1.
Следовательно, получаем
n · d (n) – σ (n) = kn – ( d1 + d2 + . . . + dk ) =
= (n – d1) + (n – d2) + . . . + (n – dk) >
> (n – d1) + (n – d2) + (n – dk) >
> (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! = (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) и Википедия.
Немає коментарів:
Дописати коментар