Иллюстрированный самоучитель по Mathematica 5

Функция Эйлера (EulerPhi)

Если в полной системе вычетов по модулю поставить только вычеты, взаимно простые с модулем, получим приведенную систему вычетов по модулю n. Мощность приведенной системы вычетов по модулю n как множества обозначается φ(n), а функция φ:n › φ(n) называется функцией Эйлера. Найдем, для примера, приведенную систему вычетов по модулю 10.

Приведенная система вычетов по модулю 10, как видим, содержит 4 элемента. Значит,φ(10) = 4. В системе Mathematica функция Эйлера имеет имя EulerPhi. Вот как можно вычислить φ(10).

Функция Эйлера имеет замечательные свойства и многочисленные применения. Например, она обладает следующим свойством:

Если а и т взаимно простые, то а^φ(m) = 1(modm).

Это утверждение называется теоремой Эйлера и очень часто малой теоремой Ферма, который знал ее частный случай для простых модулей т. Эта теорема позволяет упростить вычисление остатков степеней чисел, взаимно простых с модулем. Рассмотрим пример.

Пример 8.1. "Бытие Бога".

Во второй половине XIX века некоторых авторов привлекали числа 22, З3, 44. Вот что пишет об этих числах известный немецкий популяризатор математики Вальтер Литцман в середине XX столетия:

В одной, изданной в 1874 году книге под названием "Бытие Бога" (автор книги – Крениг) рассматривается ряд чисел: 22, З3, 44. О последнем из этих чисел автор говорит: "Представьте себе отрезок такой длины, что световому лучу понадобился бы квинтиллион лет, чтобы пройти этот путь. Затем представьте себе шар с диаметром, равным этому отрезку, наполненный типографской краской. Всей этой краски не хватило бы, чтобы четко напечатать это число даже самыми мелкими цифрами, какие только существуют". X. Маурер исследовал эти числа с точки зрения теории чисел. Обозначив для простоты число Xх через 3x: и введя затем общее обозначение nх = хm (где х и n – целые положительные числа), он показал, как можно найти последние цифры этих числовых великанов. Так, например, 29 (т. е. 99) оканчивается на 89, 39 – на 289, 49 – на 5289, 59 – на 45 289 и так далее, наконец, 109 – на 9 392 745 289. Таким образом, последние n цифр числа "9 повторяются во всех последующих числах "+19, "+29,… и т.д. Аналогичными свойствами обладает и любой другой ряд 1х = х, 2х, 3х,… и так далее, где х – целое.

Что вы чувствуете по мере чтения этого отрывка? Я чувствую интерес и нарастающее недоверие. Я, например, в захвате от сравнения с шаром. Но я сомневаюсь, заканчивается ли 109 – на 9 392 745 289. И даже если последние из цифр числа "9 повторяются во всех последующих числах "+19, "+29,… и так далее, то я полагаю, что это как-то связано с девяткой и с тем, что эти числа записываются в десятичной системе счисления. Едва ли такими свойствами обладает и любой другой ряд 1х = х, 2х, x,… и так далее, где х – целое. И действительно, i2 = 2 заканчивается на 2, а 2 х = 4 – на 4. Уже последняя цифра не повторяется во всех последующих числах этого вида! Как можно говорить о повторении последних n цифр числа? Так что насчет таких свойств у любого другого ряда 1х = х, 2х, 3x… и так далее, где х – целое, то тут явное вранье. Вальтер Литцман, правда, говорит не о таких свойствах, а об аналогичных свойствах, но в чем отличие, не указывает явно. Такими свойствами не обладают, например, числа х = 3, 4, 8 и многие другие. Поэтому в чем именно состоит аналогия, для меня пока не совсем понятно. И мне, естественно, хочется прояснить этот вопрос и еще сильнее хочется вычислить последние и цифр числа n9.

Давайте начнем с вычисления последних n цифр числа n9. Как это сделать с помощью системы Mathematica?

Вот определение функции nх.

Функция "х возрастает очень быстро, значительно быстрее факториалов, поэтому, если нужно вычислить, скажем, последние k знаков какого-нибудь значения этой функции, необходимо использовать PowerMod.

Пусть k = 50. Тогда мы в мгновение ока сможем вычислить последние 50 знаков чисел 19, 29 и 39. Но вот вычислить последние даже 10 знаков числа 49 так легко не удастся. Этот пример показывает, что в некоторых случаях применение функции PowerMod может продвинуть вычисления всего лишь на один шаг!

Но функция Эйлера (и малая теорема Ферма) позволяет быстро вычислить последние 50 знаков числа "9. Программа, конечно, будет другая.

Можно ли быстро вычислить последние 50 знаков числа 59 по такой программе?

Едва ли.