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

Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема^[6].

Теорема 1. Пусть ${\displaystyle (m,\;m')=1}$ и ${\displaystyle a}$ пробегает полную систему вычетов по модулю ${\displaystyle m}$, в то время как ${\displaystyle a'}$ пробегает полную систему вычетов по модулю ${\displaystyle m'}$. Тогда числа ${\displaystyle a'm+am'}$ образуют полную систему вычетов по модулю ${\displaystyle m}$${\displaystyle m'}$.

Доказательство. Если

${\displaystyle a_{1}'m+a_{1}m'\equiv a_{2}'m+a_{2}m'{\pmod {mm'}},}$

тогда

${\displaystyle a_{1}m'\equiv a_{2}m'{\pmod {m}},}$

поэтому

${\displaystyle a_{1}\equiv a_{2}{\pmod {m}};}$

аналогично

${\displaystyle a_{1}'\equiv a_{2}'{\pmod {m'}}.}$

Поэтому существует ${\displaystyle mm'}$ несравнимых по модулю чисел, которые образуют полную систему вычетов по модулю ${\displaystyle mm'}$.

Теперь можно доказать основное утверждение^[7].

Теорема 2. Функция Эйлера мультипликативна.

Доказательство. Если ${\displaystyle (m,\;m')=1}$, то по Теореме 1 ${\displaystyle a'm+am'}$ пробегает приведённую систему вычетов по модулю ${\displaystyle mm'}$, когда ${\displaystyle a}$ и ${\displaystyle a'}$ пробегают приведённые системы вычетов по модулям ${\displaystyle m}$ и ${\displaystyle m'}$ соответственно. Также:

${\displaystyle (a'm+am',\;mm')=1}$

${\displaystyle \Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1}$

${\displaystyle \Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1}$

${\displaystyle \Leftrightarrow (a,\;m)=1,\;(a',\;m')=1.}$

Поэтому ${\displaystyle \varphi (mm')}$ чисел, которые меньше числа ${\displaystyle mm'}$ и взаимно просты с ним, являются наименьшими положительными вычетами среди ${\displaystyle \varphi (m)\varphi (m')}$ значений ${\displaystyle a'm+am'}$, для которых ${\displaystyle a}$ взаимно просто с ${\displaystyle m}$ и ${\displaystyle a'}$ взаимно просто с ${\displaystyle m'}$. Отсюда следует, что

${\displaystyle \varphi (mm')=\varphi (m)\varphi (m').}$

Как следует из основной теоремы арифметики, всякое натуральное число ${\displaystyle n>1}$ единственным образом представляется в виде:

${\displaystyle n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{k}^{\alpha _{k}},}$

где ${\displaystyle p_{1}<\ldots <p_{k}}$ — простые числа, ${\displaystyle \alpha _{1},\;\ldots ,\;\alpha _{k}}$ — натуральные числа.

Используя мультипликативность функции Эйлера и выражение для ${\displaystyle \varphi (p^{k})}$, получаем: ${\displaystyle {\begin{aligned}\varphi (n)&=\varphi (p_{1}^{\alpha _{1}})\varphi (p_{2}^{\alpha _{2}})\cdot \ldots \cdot \varphi (p_{k}^{\alpha _{k}})=\\&=p_{1}^{\alpha _{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{\alpha _{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{k}}}\right)=\\&=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right)=\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right).\end{aligned}}}$

Пусть ${\displaystyle (m,\,n)=d,}$ тогда ${\displaystyle m=m'd,\;n=n'd,}$ причем в общем случае ${\displaystyle (m',\,d)\neq 1}$ и ${\displaystyle (n',\,d)\neq 1.}$ Поэтому можно записать:

${\displaystyle d=d_{1}^{\delta _{1}}\cdot \ldots \cdot d_{k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}},}$

${\displaystyle m'=d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{1}}\cdot \ldots \cdot p_{r}^{\beta _{r}},}$

${\displaystyle n'=d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}.}$

Здесь первые ${\displaystyle k}$ делителей ${\displaystyle d}$ являются также делителями ${\displaystyle m',}$ а последние ${\displaystyle K-k}$ делителей ${\displaystyle d}$ являются делителями ${\displaystyle n'.}$ Распишем:

${\displaystyle \varphi (mn)=\varphi (d^{2}\cdot m'n')=\varphi ((d_{1}^{\delta _{1}}\cdot \ldots \cdot d_{k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}})^{2}\cdot d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{1}}\cdot \ldots \cdot p_{r}^{\beta _{r}}\cdot d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}).}$

В силу мультипликативности функции Эйлера, а также с учётом формулы

${\displaystyle \varphi (p^{n})=p^{n}(1-{\frac {1}{p}}),}$

где ${\displaystyle p}$ — простое, получаем:

${\displaystyle {\begin{aligned}\varphi (mn)&=d_{1}^{\alpha _{1}+\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k}^{\alpha _{k}+\delta _{k}}\left(1-{\frac {1}{d_{k}}}\right)\cdot p_{1}^{\beta _{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdot \ldots \cdot p_{r}^{\beta _{r}}\left(1-{\frac {1}{p_{r}}}\right)\cdot d_{k+1}^{\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\delta _{K}}\left(1-{\frac {1}{d_{K}}}\right)\times \\&\;\times \;d_{k+1}^{\gamma _{k+1}+\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\gamma _{K}+\delta _{K}}\left(1-{\frac {1}{d_{K}}}\right)\cdot q_{1}^{\varepsilon _{1}}\left(1-{\frac {1}{q_{1}}}\right)\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}\left(1-{\frac {1}{q_{s}}}\right)\cdot d_{1}^{\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k+1}^{\delta _{k+1}}\left(1-{\frac {1}{d_{k+1}}}\right)\times \\&\;\times \;{\frac {1}{\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{d_{K}}}\right)}}.\end{aligned}}}$

В первой строке записано ${\displaystyle \varphi (m),}$ во второй — ${\displaystyle \varphi (n),}$ а третью можно представить, как ${\displaystyle d/\varphi (d).}$ Поэтому:

${\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)\cdot {\frac {d}{\varphi (d)}}.}$

Действительно, если ${\displaystyle p}$ — простое нечётное и ${\displaystyle \alpha >1,}$ то

${\displaystyle p^{\alpha -1}(p-1)}$ — чётное.

Из равенства

${\displaystyle \varphi (n)=\prod _{i=1}^{k}p_{i}^{\alpha _{i}-1}(p_{i}-1)}$

следует утверждение.

Очевидно, если ${\displaystyle \varphi (n)=m,}$ то ${\displaystyle m<n.}$ С другой стороны, если ${\displaystyle \varphi (n)=m}$ и ${\displaystyle n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s}},}$ то

${\displaystyle m=n\prod _{i=1}^{s}{\frac {p_{i}-1}{p_{i}}}\;\Rightarrow \;n=m\prod _{i=1}^{s}{\frac {p_{i}}{p_{i}-1}}.}$

Однако, если ${\displaystyle p\mid n,}$ то ${\displaystyle p-1\mid \varphi (n).}$ Поэтому

${\displaystyle \forall p_{i}:\;p_{i}-1\mid m.}$

Следовательно ${\displaystyle n\leqslant A(m).}$

Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 — простые числа. Вычисляем

${\displaystyle A(4)=4\cdot {\frac {2}{1}}\cdot {\frac {3}{2}}\cdot {\frac {5}{4}}=15.}$

Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:

${\displaystyle \varphi ^{-1}(4)=\{5,\;8,\;10,\;12\}.}$

Не существует, например, такого числа ${\displaystyle m,}$ что ${\displaystyle \varphi (m)=14.}$ То есть:

${\displaystyle \varphi ^{-1}(14)=\varnothing .}$

В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа — простые. Поэтому

${\displaystyle A(14)=14\cdot {\frac {2}{1}}\cdot {\frac {3}{2}}=42.}$

Перебрав все числа от 15 до 42, несложно убедиться, что

${\displaystyle \varphi (n)\neq 14,\;n\in (15,\,42].}$

В силу выбора чисел на этапе создания ключей

${\displaystyle e\cdot d=1+a\cdot \varphi (n).}$

Если ${\displaystyle (m,\,n)=1,}$ то, с учетом теоремы Эйлера,

${\displaystyle c^{d}=m^{ed}=m^{1}m^{a\varphi (n)}=m\cdot 1^{a}=m\;{\bmod {\;}}n.}$

В общем случае ${\displaystyle m}$ и ${\displaystyle n}$ могут иметь общие делители, но расшифрование всё равно оказывается верным. Пусть ${\displaystyle m=0\;{\bmod {\;}}p.}$ По китайской теореме об остатках:

${\displaystyle m=c^{d}\;{\bmod {\;}}n\;\Leftrightarrow \;{\begin{cases}m=c^{d}\;{\bmod {\;}}p,\\m=c^{d}\;{\bmod {\;}}q.\end{cases}}}$

Подставляя ${\displaystyle c=m^{e},}$ получаем тождество

${\displaystyle {\begin{cases}m^{ed}=0=m\;{\bmod {\;}}p,\\m^{ed}=m(m^{q-1})^{a(p-1)}=m\cdot 1^{a(p-1)}=m\;{\bmod {\;}}q.\end{cases}}}$

Следовательно,

${\displaystyle m^{ed}=m\;{\bmod {\;}}pq.}$

Найдем ${\displaystyle 5^{-1}\;{\bmod {\;}}7}$, то есть такое число ${\displaystyle x}$, что

${\displaystyle 5\cdot x\equiv 1{\pmod {7}}.}$

Очевидно, ${\displaystyle 5}$ и ${\displaystyle 7}$ не имеют общих делителей кроме единицы, ${\displaystyle (5,7)=1}$, при этом число ${\displaystyle 7}$ простое и

${\displaystyle \varphi (7)=7-1=6,}$

поэтому удобно воспользоваться формулой, приведенной выше:

${\displaystyle 5^{6-1}\;{\bmod {\;}}7=5^{5}\;{\bmod {\;}}7=25\cdot 25\cdot 5\;{\bmod {\;}}7=(-3)\cdot (-3)\cdot 5\;{\bmod {\;}}7=9\cdot 5\;{\bmod {\;}}7=2\cdot 5\;{\bmod {\;}}7=3.}$

Легко проверить, что в самом деле

${\displaystyle 5\cdot 3\equiv 1{\pmod {7}}.}$

В общем случае для вычисления обратных значений алгоритм Евклида быстрее, чем использование теоремы Эйлера^[37], так как битовая сложность вычисления по алгоритму Евклида имеет порядок ${\displaystyle O(k^{2}),}$ в то время как вычисление по теореме Эйлера требует порядка ${\displaystyle O(k^{3})}$ битовых операций, где ${\displaystyle k=\lceil \log _{2}{n}\rceil .}$ Однако, в случае, когда известно разложение ${\displaystyle \varphi (n)-1}$ на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм «возводи в квадрат и перемножай»^[38].

Если ${\displaystyle (a,\,n)\neq 1,}$ то обратного к ${\displaystyle a}$ элемента не существует, или, иначе говоря, уравнение

${\displaystyle a\cdot x\equiv 1{\pmod {n}}}$

не имеет решения на множестве натуральных чисел^[39].
Доказательство. В самом деле, допустим

${\displaystyle (a,\,n)=d>1,}$

и решение существует. Тогда по определению наибольшего общего делителя

${\displaystyle a=d\cdot a',\ n=d\cdot n',}$ причем ${\displaystyle (a',\,n')=1;}$

поэтому можно записать:

${\displaystyle d\cdot a'\cdot x=d\cdot n'\cdot t+1,}$ где ${\displaystyle t\in \mathbb {N} _{0},x\in \mathbb {N} ;}$

или, перегруппировав слагаемые,

${\displaystyle a'\cdot x-n'\cdot t={\frac {1}{d}}.}$

Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью

${\displaystyle d=1,}$

что противоречит предположению.

Рассмотрим сравнение

${\displaystyle 7\cdot x\equiv 3{\pmod {9}}.}$

Так как ${\displaystyle (7,9)=1,}$ можно воспользоваться указанной формулой:

${\displaystyle x=3\cdot 7^{\varphi (3^{2})-1}\;{\bmod {\;}}9=3\cdot 7^{3\cdot (3-1)-1}\;{\bmod {\;}}9=3\cdot 7^{5}\;{\bmod {\;}}9=3\cdot 49\cdot 49\cdot 7\;{\bmod {\;}}9=3\cdot 4\cdot 4\cdot 7\;{\bmod {\;}}9=3.}$

Подстановкой убеждаемся, что

${\displaystyle 7\cdot 3\equiv 3{\pmod {9}}.}$

Если ${\displaystyle (a,\,n)\neq 1}$, сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение

${\displaystyle 2\cdot x\equiv 3{\pmod {4}}}$

не имеет решения на множестве натуральных чисел. В то же время сравнение

${\displaystyle 4\cdot x\equiv 6{\pmod {22}}}$

имеет два решения

${\displaystyle x=7,\;x=18.}$

Найдем последние три цифры в десятичной записи числа ${\displaystyle 2^{100}.}$ Замечая, что

${\displaystyle \varphi (125)=\varphi (5^{3})=5^{3}-5^{2}=100,}$

получаем

${\displaystyle 2^{100}\;{\bmod {\;}}125=2^{125-25}\;{\bmod {\;}}125=2^{\varphi (125)}\;{\bmod {\;}}125=1\;{\bmod {\;}}125.}$

Переходя теперь от модуля ${\displaystyle 125}$ к модулю ${\displaystyle 1000,}$ имеем:

${\displaystyle 2^{100}\equiv 1{\pmod {125}}\equiv 376{\pmod {1000}}.}$

Следовательно, десятичная запись числа ${\displaystyle 2^{100}}$ оканчивается на ${\displaystyle 376.}$

Найдем остаток от деления ${\displaystyle 729^{720}}$ на ${\displaystyle 1001.}$ Легко видеть, что

${\displaystyle (729,\;1001)=1.}$

Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством

${\displaystyle \varphi (p)=p-1,}$ для всякого простого ${\displaystyle p,}$

получаем

${\displaystyle \varphi (1001)=\varphi (7\cdot 11\cdot 13)=\varphi (7)\cdot \varphi (11)\cdot \varphi (13)=6\cdot 10\cdot 12=720.}$

По теореме Эйлера

${\displaystyle 729^{720}\equiv 1{\pmod {1001}}.}$