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

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

Select[Range[10],GCD[fl,10]==!&]

{1,3,7,9} 

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

EulerPhi[10]

4 

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

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

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

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

В одной, изданной в 1874 году книге под названием "Бытие Бога" (автор книги — Крениг) рассматривается ряд чисел: 22, З3 , 44 .О последнем из этих чисел автор говорит: "Представьте себе отрезок такой длины, что световому лучу понадобился бы квинтиллион лет, чтобы пройти этот путь. Затем представьте себе шар с диаметром, равным этому отрезку, наполненный типографской краской. Всей этой краски не хватило бы, чтобы четко напечатать это число даже самыми мелкими цифрами, какие только существуют". X. Маурер исследовал эти числа с точки зрения теории чисел. Обозначив для простоты число Xх через 3x: и введя затем общее обозначение nх = хm (где хил — целые положительные числа), он показал, как можно найти последние цифры этих числовых великанов. Так, например, 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х .

GodF[n_,x_]:=Module[{t=1},Do[t=xAt,[i,n}];t] 

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

GodFLastk[n_,x_,k_] :=

If [n==l,Mod[x,10Ak],PowerMod[x,GodF[n-l, х],IQ^k] ]

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

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

PowerMod[9,PowerMod[9,9A9,EulerPhi[10^50]],1^50] 

30363975097419408973491530163140828233401045865289 

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

PowerMod[9,PowerMod[9,9Л9Л9,EulerPhi[10Л50]],10^50]

Едва ли.

В чем же причина такого медленного продвижения, почему мы продвигаемся только на один шаг? Это происходит потому, что мы на самом деле устраняем быстрый рост функции nx = x(nf} только на последнем шаге. Почему это происходит? Потому, что мы все время связаны с определением функции GodF. Именно она используется внутри функции GodFLastk. Даже фактически отказавшись от явного применения функции GodFLastk, мы все равно стремимся записать выражение для nх = х(nⁿ) с некоторыми упрощениями для последнего или предпоследнего возведения

в степень. Конечно, это так естественно использовать выражение для "х = х(') Однако нужно иметь в виду, что использование подобных "прямолинейных" определений часто весьма неэффективно. Если уж мы решили повышать эффективность, то делать это нужно на всю "глубину" выражения. Правда, это неизбежно приведет к появлению новых функций. Нам, например, придется отказаться от функции GodFLastk. Как ни удивительно, но вместо нее нам понадобится только одна функция, притом довольно простая. Давайте найдем ее определение. Обозначим через С(n, х, k) остаток от деления "х на k. (Таким образом, G(n, х, m) — это последние т цифр числа nх .) Тогда 0(1, х, k) = Mod [х, k]. С другой стороны,

С(n+1,x,k)=Mod[ хn,k]=PowerMod[x,"x ,k].

Предположим теперь, что х и k взаимно просты. Тогда по малой теореме Ферма это выражение можно записать так: PowerMod [x, G(n, х, ср(А:)), k]. Так что в этом случае G(n+l, x, k) = PowerMod [x, G(n, x, <p(k)), k]. Это и есть нужное нам рекуррентное соотношение. С учетом этого соотношения определение нужной нам функции выглядит так.

GodFk[n_,x_,k_]:=

If[n==l,Mod[x,k],

If[GCD[x,k]==l,PowerMod[x,GodFk[n-l,x, EulerPhi[k]],k],

PowerMod[x,GodF[n-l,x] , k]]];

Теперь легко написать программу.

Do[Print["n=",n,":",GodFk[n,x=9,10/sk]],{n,k=50}]

Давайте теперь выполним аналогичные вычисления для числа 3. Вот так запишется программа.

Do[Print["n=",n,":",GodFk[n,x=3,10Ak]],{n,k=50}] 

Теперь понятно, что имел в виду Вальтер Литцман под аналогичными свойствами. Начиная с некоторого и = и„ последняя цифра числа не изменяется, причем начиная

с и = «() + 1 повторяются уже две цифры, с n = n0+2 — три цифры, с n = n0+k — k цифр и т. д. (Через и„ (х) удобно обозначать наименьшее п0 с таким свойством.) Для некоторых х, например для х = 9, n(х) = 1, а для некоторых х (n)>1. Если п0(х)>1, то нельзя утверждать, что последние n цифр числа "х повторяются во всех последующих числах "+1x, "+2х, ... и т.д. Если п0(х)>1, то повторение последних nцифр начнется не с числа "х, а несколько позднее! Да уж, разбираться в популярных книжках иногда приходится с системой Mathematical

Пример 8.2. График функции Эйлера.

Давайте теперь построим график функции Эйлера. Сначала используем функции Table и EulerPhi для построения таблицы tl (точнее, списка) значений функции Эйлера.

t1= Table[EulerPhi[k],{k,1,n=10A3}];

Теперь можем использовать функцию ListPlot для построения графика.

А вот график для n = 100000.

Содержание

Содержание раздела