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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Первая тысяча значений \varphi(n)

Функция Эйлера \varphi(n) — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и \varphi(1)=1.[1]

Например, для числа 24 существует 8 меньших него и взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому \varphi(24)=8.

Названа в честь Эйлера, который впервые использовал её в 1760 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования» (Disquisitiones Arithmeticae (англ.)), вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение \varphi(n).[2]

Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов (см. сравнение по модулю), теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA.[3]

Содержание

Вычисление[править | править вики-текст]

Общие сведения[править | править вики-текст]

Функция Эйлера \varphi(n) показывает, сколько натуральных чисел из отрезка [1,\;n-1] имеют c n только один общий делитель — единицу. Функция Эйлера определена на множестве натуральных чисел, и значения её лежат в множестве натуральных чисел.

Как следует из определения, чтобы вычислить \varphi(n), нужно перебрать все числа от 1 до n-1 и для каждого проверить, имеет ли оно общие делители с n, а затем подсчитать, сколько чисел оказались взаимно простыми с n. Эта процедура весьма трудоемка, поэтому для вычисления \varphi(n) используют другие методы, которые основываются на специфических свойствах функции Эйлера.

В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение \varphi(n) не превосходит n-1, и в точности ему равно, если n — простое. Таким образом, если в координатах (n,\;y) провести прямую y=n-1, то значения y=\varphi(n) будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения \varphi(n) снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число n, такое что \varphi(n) лежит ниже этой прямой. Ещё одной интересной особенностью графика, является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой y=n-1, на которой лежат значения \varphi(n)=n-1, где n — простое, выделяется прямая, примерно соответствующая y=n/2, на которую попадают значения \varphi(2n)=\varphi(n)=n-1, где n — простое.

Более подробно поведение функции Эйлера рассматривается в разделе #Асимптотические соотношения.

Первые 99 значений функции Эйлера (последовательность A000010 в OEIS)
\varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+ 1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Мультипликативность функции Эйлера[править | править вики-текст]

Одним из основных свойств функции Эйлера является её мультипликативность. Это свойство было установлено ещё Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел m и n [4]

\varphi(mn)=\varphi(m)\varphi(n).

Функция Эйлера от простого числа[править | править вики-текст]

Для простого p значение функции Эйлера задается явной формулой:[7]

\varphi(p)=p-1,

которая следует из определения. Действительно, если p — простое, то все числа, меньшие p, взаимно просты с ним, а их ровно p-1 штук.

Для вычисления функции Эйлера от степени простого числа используют следующую формулу:[7]

\varphi(p^n)=p^n-p^{n-1}.

Это равенство обосновывается следующим образом. Подсчитаем количество чисел от 1 до p^n, которые не взаимно просты с p^n. Все они, очевидно, кратны p, то есть, имеют вид: p,\;2p,\;3p,\;\ldots,\;(p^{n-1}-1)p. Всего таких чисел p^{n-1}-1. Поэтому количество чисел, взаимно простых с p^n, равно p^n-1-(p^{n-1}-1)=p^n-p^{n-1}.

Функция Эйлера от натурального числа[править | править вики-текст]

Вычисление \varphi(n) для произвольного натурального n основывается на мультипликативности функции Эйлера, выражении для \varphi(p^{n}), а также на основной теореме арифметики. Для произвольного натурального числа значение \varphi(n) представляется в виде:[7]

\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,

где p — простое число и пробегает все значения, участвующие в разложении n на простые сомножители.

Свойства[править | править вики-текст]

Обобщённая мультипликативность[править | править вики-текст]

Функция Эйлера является мультипликативной арифметической функцией, то есть

\varphi(mn)=\varphi(m)\varphi(n) \;\;\; \forall m, n \in \N: \;\; (m,n)=1.

Здесь существенно, что наибольший общий делитель m и n равен единице. Оказывается, существует обобщение этой формулы на случай, когда m и n имеют общие делители, отличные от единицы. А именно, для любых натуральных m и n: [8]

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},

где d — наибольший общий делитель m и n. Это свойство является естественным обобщением мультипликативности.

Некоторые частные случаи:

Теорема Эйлера[править | править вики-текст]

Наиболее часто на практике используется свойство, установленное Эйлером:

a^{\varphi(m)}\equiv 1\pmod m,

если a и m взаимно просты.
Это свойство, которое называют теоремой Эйлера, вытекает из Теоремы Лагранжа и того факта, что φ(m) равна порядку группы обратимых элементов кольца вычетов по модулю m.
В качестве следствия теоремы Эйлера можно получить малую теорему Ферма. Для этого нужно взять не произвольное m, а простое. Тогда:

a^{m - 1}\equiv 1\pmod m.

Последняя формула находит применение в различных тестах простоты.

Другие свойства[править | править вики-текст]

Исходя из представимости \varphi(n) произведением Эйлера, несложно получить следующее полезное утверждение:

a\mid b \Rightarrow \varphi(a)\mid\varphi(b).

Следующее равенство[9][10] является следствием теоремы Зигмонди (англ.)

\varphi(a^{n} + b^{n}) \equiv 0 \pmod n, \; a > b \ge 1.

Всякое натуральное число представимо в виде суммы значений функции Эйлера от его натуральных делителей:[11]

\sum_{d\mid n}\varphi(d)=n.

Сумма всех чисел, меньших данного, и взаимно простых с ним, выражается через функцию Эйлера:

\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n > 1.

Множество значений[править | править вики-текст]

Исследование структуры множества значений функции Эйлера является отдельной сложной задачей. Здесь представлены лишь некоторые результаты, полученные в этой области.[12]

  • Функция Эйлера \varphi(n) принимает только чётные значения при n > 2. Причём, если n имеет r различных нечётных простых делителей, то 2^{r} \mid \varphi(n).

В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции. Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду, что

  1. значения функции Эйлера повторяются (например, \varphi(1) = \varphi(2) = 1), следовательно обратная функция является многозначной, а также
  2. функция Эйлера принимает лишь чётные значения при n > 2, то есть \varphi^{-1}(m) = \empty, если m нечётно и m \not = 1.

В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза \varphi является следующая теорема:[13]

  • Пусть m — чётное, положим
    A(m) = m \prod_{p-1|m}\frac{p}{p-1}, где p — простое.
Если n \in \varphi^{-1}(m), то m < n \le A(m).

Эта теорема показывает, что прообраз элемента m \in \mathbb{N} всегда представляет собой конечное множество. Также она дает практический способ нахождения прообраза. Для этого нужно

  1. вычислить A(m),
  2. вычислить \varphi(n) для всех n из полуинтервала (m, A(m)];
  3. все числа n, для которых \varphi(n)=m, образуют прообраз элемента m.

Может оказаться, что в указанном промежутке нет такого числа n, что \varphi(n)=m; в этом случае прообраз является пустым множеством.
Стоит отметить, что для вычисления A(m) нужно знать разложение m на простые сомножители, что для больших m является вычислительно сложной задачей. Затем, нужно A(m)-m раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.

Асимптотические соотношения[править | править вики-текст]

Простейшие неравенства[править | править вики-текст]

  • Оценка снизу значений функции Эйлера:[14][15]
     \varphi(n) \ge \sqrt{n},
для всех n, кроме n = 2 и n = 6.
  • Оценка сверху для составных n:[14][16]
    \varphi(n) \le n - \sqrt{n},
для всякого составного n.
  • Для всех натуральных значений n \ge 3 справедливо двойное неравенство:[14]
    \frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.

Сравнение φ(n) с n[править | править вики-текст]

  • Верхняя грань отношения \varphi(n)/n приближается к единице с ростом n:[17]
    \varlimsup \frac{\varphi(n)}{n} = 1.
  • В то же время отношение \varphi(n)/n^{1-\delta} может быть сколь угодно большим:[18]
    \forall \delta > 0: \; \frac{\varphi(n)}{n^{1 - \delta}} \rightarrow \infty.

Отношение последовательных значений[править | править вики-текст]

  • Следующие равенства показывают, насколько непредсказуемо ведет себя функция Эйлера:[19]
    
\lim\inf \frac{\varphi(n+1)}{\varphi(n)}= 0 и 
\lim\sup \frac{\varphi(n+1)}{\varphi(n)}= \infty.
  • Формулы, приведенные выше, получил Somayajulu в 1950 году. А четырьмя годами позже Шинцель (англ.) и Серпинский доказали,[19] что множество

\left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,2,\cdots\right\}
плотно в множестве действительных положительных чисел.
  • В том же году они установили,[19] что множество

\left\{\frac{\varphi(n)}{n},\;\;n = 1,2,\cdots\right\}
плотно на интервале (0,1).

Асимптотики для сумм[править | править вики-текст]

  • Точное выражение для суммы последовательных значений функции Эйлера:[20]
    \sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).
Отсюда вытекает, что средний порядок (англ.) функции Эйлера равен 6n/\pi^{2}. Этот результат интересен тем, что позволяет получить вероятность события, состоящего в том, что два наугад выбранных натуральных числа являются взаимно простыми. А именно, эта вероятность равна 6/\pi^{2}.[21]
  • С учетом приведенного выше выражения, можно получить следующие асимптотические оценки:
    \sum_{k=1}^n\frac{k}{\varphi(k)}=O(n);
    \sum_{k=1}^n\frac{1}{\varphi(k)}=O(\ln n).
  • Используя мультипликативность функции Эйлера и свойства суммы делителей \sigma(n) несложно установить, что[22]
    \frac {6}{\pi^2} < \frac{\varphi(n) \sigma(n)}{n^2} < 1, \; n > 1.

Порядок функции Эйлера[править | править вики-текст]

где \gamma — постоянная Эйлера-Маскерони.
  • Этот результат можно уточнить. В 1962 году была получена оценка снизу для функции Эйлера:[25]
    \varphi(n) \ge e^{-\gamma} \frac {n} {\log \log n + (5/2 \; e^{\gamma} \log \log n)},
для всех n \ge 3, с одним исключением n = 2\times3\times5\times7\times11\times13\times17\times19\times23; в указанном случае следует заменить 5/2 на 2.50637. Это одна из наиболее точных оценок снизу для \varphi(n).[26]
\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} 
для n > 2,
  • В качестве оценки сверху был установлен следующий факт:[27] существует бесконечно много натуральных n таких, что
    \varphi(n) < e^{-\gamma} \frac {n} {\log \log n}.
Как отмечает Paulo Ribenboim (англ.) по поводу доказательства этого неравенства:[26] «Способ доказательства интересен тем, что неравенство сначала устанавливается в предположении, что гипотеза Римана верна, а затем в предположении, что она не верна».

Связь с другими функциями[править | править вики-текст]

Функция Мёбиуса[править | править вики-текст]

  • Следующую формулу можно использовать для вычисления \varphi(n):[28]
    \varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right),
где \mu(m) — функция Мёбиуса.
  • Другие соотношения с функцией Мёбиуса:
    \sum_{k=1}^n\varphi(k)=\frac{1}{2}\left(1+\sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right);
    \sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor;
    \sum_{d\mid n}\frac{\mu^2(d)}{\varphi(d)}=\frac{n}{\varphi(n)}.[29]

Ряд Дирихле[править | править вики-текст]

Ряд Ламберта[править | править вики-текст]

Наибольший общий делитель[править | править вики-текст]

Действительная часть:
\varphi (n)=\sum\limits_{k=1}^n \gcd(k,n) \cos {2\pi\frac{k}{n}}.
В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей n.

Приложения и примеры[править | править вики-текст]

Функция Эйлера в RSA[править | править вики-текст]

На основе алгоритма, предложенного в 1978 году Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов — система RSA. Криптостойкость этой системы определяется сложностью разложения на сомножители целого n-разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом.[33]

На этапе создания пары из секретного и открытого ключей, вычисляется

\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),

где p и q — простые. Затем выбираются случайные числа d, e так, чтобы

d \cdot e = 1 \;\bmod \;\varphi(n).

Затем сообщение шифруется открытым ключом адресата:

c = m^e \;\bmod \;n.

После этого расшифровать сообщение может только обладатель секретного ключа d:

m = c^d \;\bmod \;n.

Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.

Вычисление обратного элемента[править | править вики-текст]

Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю n, а именно:[34]

a^{-1} \equiv a^{\varphi(n)-1} \pmod n, если (a,n) = 1.

Эта формула следует из теоремы Эйлера:

1 = (a \cdot a^{-1}) \cdot a^{\varphi(n)} \;\bmod \;n = a \cdot (a^{-1} \cdot a^{\varphi(n)}) \;\bmod \;n = a \cdot a^{\varphi(n) - 1} \;\bmod \;n.

Решение линейного сравнения[править | править вики-текст]

Метод вычисления обратного элемента можно использовать для решения сравнения

a \cdot x \equiv b \pmod n.

Решение задается формулой [35]

x \equiv b \cdot a^{\varphi(n)-1} \pmod n, если (a,n) = 1.

Вычисление остатка от деления[править | править вики-текст]

Функции Эйлера позволяет вычислять остатки от деления больших чисел.[38]

Нахождение порядка мультипликативной группы кольца вычетов[править | править вики-текст]

Мультипликативная группа кольца вычетов по модулю m состоит из \varphi(m) классов вычетов.[39]
Пример. Приведённая система вычетов по модулю 14 состоит из \varphi(14) = 6 классов вычетов: [1]_{14}, [3]_{14}, [5]_{14}, [9]_{14}, [11]_{14}, [13]_{14}.

Приложения в теории групп[править | править вики-текст]

Число порождающих элементов в конечной циклической группе G равно \varphi(|G|). В частности, если мультипликативная группа кольца вычетов по модулю m является циклической группой — что возможно только при m = 2, 4, p^{n}, 2p^{n}, где p — простое нечетное, n — натуральное,[40] — то существует \varphi(\varphi(m)) генераторов группы (первообразных корней по модулю m).
Пример. Группа \mathbb{Z}_{14}^{\times}, рассмотренная в примере выше, имеет \varphi(\varphi(14)) = \varphi(6) = 2 генератора: 3 и 5.

Нерешенные вопросы[править | править вики-текст]

Задача Лемера[править | править вики-текст]

Как известно, если p — простое, то \varphi(p) = p - 1. В 1932 Лемер (англ.) задался вопросом, существует ли такое составное число n, что \varphi(n) является делителем n-1. Лемер рассматривал уравнение

k\varphi(n) = n-1,

где k — целое. Ему удалось доказать, что если n — решение уравнения, то либо n — простое, либо оно является произведением семи или более различных простых чисел.[41] Позже были доказаны и другие сильные утверждения. Так в 1980 году Cohen и Hagis показали, что если n составное и \varphi(n) делит n-1, то n > 10^{20} и \omega(n) \ge 14, где \omega(n) — количество простых делителей. В 1970 году Lieuwens установил, что если 3\mid n, то \omega(n) \ge 213 и n > 5{,}5 \times 10^{570}. Wall в 1980 году доказал, что если 30\mid n, то \omega(n) \ge 26.[42]

По сей день неизвестно, существуют ли составные решения задачи Лемера. Если предположить, что их не существует, то получается следующий критерий простоты: n — простое, тогда и только тогда \varphi(n)\mid n-1.[41]

Гипотеза Кармайкла[править | править вики-текст]

Если посмотреть даже на первые десять значений функции Эйлера {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, бросается в глаза, что среди них много повторяющихся. Гипотеза Кармайкла состоит в том, что нет такого значения m, которое функция Эйлера принимала бы только один раз.

В 1907 Кармайкл предложил как упражнение доказать следующее утверждение:[43]

Если n — натуральное число, то существует натуральное число m \not = n такое, что \varphi(n)=\varphi(m).

Иначе это утверждение можно сформулировать так:[44]

Не существует натурального числа m такого, что \dim(\varphi^{-1}(m)) = 1.

Однако в 1922 Кармайкл обнаружил, что предложенное им доказательство содержит ошибку. В этом же году он показал, что если \dim(\varphi^{-1}(m)) = 1, то n > 10^{37}. Позже эта оценка неоднократно улучшалась, и современное значение нижней границы, с которой стоит начинать искать контрпример для гипотезы Кармайкла, есть n = 10^{10^7}. Это значение получили Schlafly и Wagon в 1994 году, используя метод Klee.[43]

Стоит отметить, что в 1999 Форд доказал следующую теорему:[45]

\forall k \ge 2 \;\exist m: \dim(\varphi^{-1}(m)) = k.

Это означает, что задавшись некоторым числом k \ge 2, можно найти среди множества значений функции Эйлера такое значение m, что оно принимается ровно k раз. Однако, доказать, что нет такого значения, которое функция Эйлера принимала бы только один раз, до сих пор никому не удалось.[44]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Ribenboim, 1996, p. 34
  2. Sandifer, 2007, p. 203
  3. Габидулин, 2011, Системы RSA
  4. Burton, 2007, Theorem 7.2, p. 133
  5. Hardy, 1975, Theorem 59, p. 52
  6. Hardy, 1975, Theorem 60, p. 53
  7. 1 2 3 Сагалович, 2007, Вычисление функции Эйлера, p. 35-36
  8. Burton, 2007, Euler's Phi-Function, p. 136
  9. Weisstein, MathWorld, Totient Function
  10. Ruiz, S., A Congruence With the Euler Totient Function, 2004
  11. Виноградов, 1952, Функция Эйлера
  12. Информация в этом разделе основана на статье: Coleman, Some remarks on Euler’s totient function
  13. Gupta H., 1981
  14. 1 2 3 Handbok, 2005, Elementary inequalities for φ
  15. Kendall and Osborn 1965
  16. Sierpiński and Schinzel 1988
  17. Hardy, 1975, Theorem 326, p. 267
  18. Hardy, 1975, Theorem 327, p. 267
  19. 1 2 3 Ribenboim, 1996, Values of Euler's Function, p. 38
  20. Hardy, 1975, Theorem 330, p. 268
  21. Hardy, 1975, Theorem 332, p. 269
  22. Hardy, 1975, Theorem 329, p. 267
  23. Handbok, 2005, On the function n/φ(n)
  24. Hardy, 1975, Theorem 328, p. 267
  25. Rosser and Schoenfeld, 1962
  26. 1 2 Ribenboim, 1996, Distribution of Values of Euler's Function, p. 320
  27. Nicolas, 1983
  28. Виноградов, 1952
  29. Rosica Dineva, The Euler Totient, the Möbius, and the Divisor Functions
  30. Hardy, 1975, Theorem 288, p. 250
  31. Hardy, 1975, Theorem 309, p. 258
  32. Schramm, 2008
  33. Габидулин, 2011, Система шифрования RSA
  34. Алфёров, 2002, p. 462-463
  35. 1 2 Schneier, 1995, The Euler Totient Function
  36. Габидулин, 2011, Нахождение мультипликативного обратного по модулю
  37. Schneier, 1995, Number Theory
  38. Сагалович, 2007
  39. Сагалович, 2007, Приведенная система вычетов
  40. Виноградов, 1952
  41. 1 2 Lehmer, 1932
  42. Ribenboim, 1996, p. 36-37
  43. 1 2 Ribenboim, 1996, p. 39-40
  44. 1 2 Coleman, Some remarks on Euler’s totient function
  45. Ford, 1999

Литература[править | править вики-текст]

  • Charles Sandifer The early mathematics of Leonhard Euler. — MAA, 2007. — С. 391. — ISBN 0-88385-559-3.
  • József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici Euler's φ-function // Handbook of Number Theory I. — Springer, 2005. — 622 с.
  • Виноградов И. М. Основы теории чисел. — 5-е изд. — М.-Л.: Гостехиздат, 1952. — 180 с. — 100 000 экз.
  • G. H. Hardy, E. M. Wright An Introduction to the Theory of Numbers. — fourth edition. — Oxford: Oxford University Press, 1975. — 421 с.
  • Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Элементы алгебры и теории чисел // Основы криптографии. — 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — 480 с. — ISBN 5-85438-025-0.
  • Bruce Schneier Applied Cryptography: Protocols, Algorithms and Source Code in C. — Australia: John Wiley & Sons, 1995. — ISBN 0-471-12845-7.
  • Сагалович Ю. Л. Введение в алгебраические коды. — 2-е изд.. — М.: МФТИ, 2007. — 260 с. — ISBN 5-7417-0191-4.
  • Paulo Ribenboim The New Book of Prime Number Records. — New York: Springer, 1996. — ISBN 0-387-94457-5.
  • Габидулин Э. М., Кшевецкий А. С.б Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. — ISBN 5-7417-0377-9.
  • David M. Burton Elementary Number Theory. — Sixth Edition. — University of New Hampshire: McGraw-Hill, 2007. — 512 с. — ISBN 978-0-07-305188-8.
  • Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. — М.: МЦНМО, 2003. — 44 с. — ISBN 5-94057-141-7.

Ссылки[править | править вики-текст]