Функции связанные с делителями — Divisors и DivisorSigma

Функции, связанные с делителями, — Divisors и DivisorSigma

Делители натурального числа легко найти с помощью системы Mathematica. Для этого предусмотрена функция Divisors. Найдем, например, делители 120.

Divisors[120] {1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}

Эта функция работает и в области гауссовых чисел.

Divisors [24 + 301.] (1,1+I,2,3,3+3I,4+5I,6,8+10I,9+11I,12+15I,24+30I,27+31I}

При необходимости нужно указать опцию Gaussianlntegers->True. Без этой опции делители натуральных чисел находятся только среди натуральных чисел.

Divisors[320] {1,2,4,5,8,10,16,20,32,40,64,80,160,320}

Если же указать эту опцию, то даже у натурального числа будут найдены все его делители в области гауссовых чисел.

Функция Эйлера — 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х = х(nn) с некоторыми упрощениями для последнего или предпоследнего возведения

в степень. Конечно, это так естественно использовать выражение для "х = х(') Однако нужно иметь в виду, что использование подобных "прямолинейных" определений часто весьма неэффективно. Если уж мы решили повышать эффективность, то делать это нужно на всю "глубину" выражения. Правда, это неизбежно приведет к появлению новых функций. Нам, например, придется отказаться от функции 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 для построения графика.

Функция Мебиуса µ(m) — MoebiusMu

Функция Мебиуса µ(m) = 1, если т есть произведение четного числа различных простых чисел; µ(m) = -1, если m есть произведение нечетного числа различных простых чисел; (f(/n) = 0, если т делится на квадрат какого-либо простого числа. Вот как вычисляется эта функция.

MoebiusMu[210] 1

Пример 8.4. График функции Мебиуса.

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

tl= Table[MoebiusMu[k], {k,1,п=10^3}];

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

Резюме

В этой главе знакомство с важными числовыми функциями мы начали с функции Эйлера ф(m), дающей количество классов приведенной системы вычетов. Эта функция удовлетворяет сравнению a*1n-1 =l(modm). Однако наименьшее натуральное число, удовлетворяющее сравнению ax=1l(modm) для всех а, взаимно простых с т, доставляет функция Кармайкла ?(m). Эти функции связаны с каноническим разложением аргумента. По каноническому разложению аргумента легко также вычисляется и функция Мебиуса µ(x), отличная от нуля только в том случае, если ее аргумент свободен от квадратов, т.е. представляет собой произведение (возможно, пустое) различных простых чисел. Наконец, рассматривая функции, связанные с каноническим разложением аргумента, мы особо выделили функции, связанные с делителями. Функция Divisors позволяет найти все делители числа, а функция DivisorSigma — сумму k-x степеней всех делителей ?(n). При k = 0 получается количество делителей ?(n), а при k = 1 — сумма делителей ?(n). Изучая случай k = 0, т.е. количество делителей т(/г), мы обратили внимание на сверхсоставные числа. Рассматривая же случай k = 1, т.е. сумму делителей ?(n), мы нашли, что числа бывают недостаточные, избыточные, совершенные и дружественные. Но даже обсудив совершенные числа и дружбу между числами, мы решили далеко не все задачи элементарной теории чисел. (Сальвадор Дали сказал бы: мы не достигли совершенства.) Но эта книга предназначена для первого (хотя и серьезного) знакомства с системой Mathematica. И потому пришло время обратить свой взор не только на дружбу чисел, но и на те разделы математики, с которыми так дружна теория чисел. Иными словами, на все остальные разделы математики. И раз уж мы вспомнили об искусстве, предварим свое знакомство с возможностями системы Mathematica в других разделах математики коротеньким разговором об искусстве построения графиков.