Функция Кармайкла

В теории чисел , разделе математики , функция Кармайкла $λ$ $($ $n$ $)$ положительного целого числа $n$ — это наименьшее положительное целое число $m$ такое, что

a^{m}\equiv 1{\pmod {n}}

выполняется для любого целого числа $, взаимно$ простого с $n$ . В алгебраических терминах $λ$ $($ $n$ $)$ является показателем мультипликативной группы целых чисел по модулю n . Поскольку это конечная абелева группа , должен существовать элемент, порядок которого равен показателю степени $λ$ $($ $n$ $)$ . Такой элемент называется примитивным $λ$ -корнем по модулю $n$ .

Функция Кармайкла названа в честь американского математика Роберта Кармайкла , который определил ее в 1910 году. ^[1] Она также известна как λ-функция Кармайкла , приведенная функция тотента и наименьшая универсальная показательная функция .

В следующей таблице сравниваются первые 36 значений $λ$ $($ $n$ $)$ (последовательность A002322 в OEIS ) с функцией тотента Эйлера $φ$ (выделены жирным шрифтом, если они разные; n $s$ , такие, что они различны, перечислены в OEIS : A033949 ).

Числовые примеры

Функция Кармайкла в точке 5 равна 4, $λ$ $(5) = 4$ , поскольку для любого числа , взаимно простого с 5, т.е. существует $1$ $1\cdot4$ $= 1$ $4$ $\equiv 1 (mod 5)$ , $2$ $4$ $= 16 \equiv 1 (mod 5)$ , $3$ $4$ $= 81 \equiv 1 (по модулю 5)$ и $4$ $2\cdot2$ $= 16$ $2$ $\equiv 1$ $2$ $(по модулю 5)$ . И это $m$ $= 4$ является наименьшим показателем степени с этим свойством, потому что (и также.) Более того, функция тотента Эйлера в 5 равна 4, $φ$ $(5) = 4$ , потому что существует ровно 4 числа меньше 5 и взаимно простых с 5 ( 1, 2, 3 и 4). Теорема Эйлера гарантирует, что $4$ $\equiv$ $1 (по модулю 5)$ для всех $чисел$ , взаимно простых с 5, и 4 является наименьшим таким показателем. И 2, и 3 являются примитивными $λ$ -корнями по модулю 5, а также примитивными корнями по модулю 5. $0<a<5$ $a\in \{1,2,3,4\}~,$ $a^{m}\equiv 1\,({\text{mod }}5)$ $m=4,$ $2^{2}=4\not \equiv 1\,({\text{mod }}5)$ $3^{2}=9\not \equiv 1\,({\text{mod }}5)$
Функция Кармайкла в точке 8 равна 2, $λ$ $(8) = 2$ , поскольку для любого числа $взаимно$ простое с 8, т.е. верно, что $a$ $2$ $\equiv 1 (mod 8)$ . А именно, $1$ $1\cdot2$ $= 1$ $2$ $\equiv 1 (по модулю 8)$ , $3$ $2$ $= 9 \equiv 1 (по модулю 8)$ , $5$ $2$ $= 25 \equiv 1 (по модулю 8)$ и $7$ $2$ $= 49 \equiv 1 (по модулю 8)$ . Функция тотента Эйлера в 8 равна 4, $φ$ $(8) = 4$ , потому что существует ровно 4 числа меньше 8 и взаимно простых с ними (1, 3, 5 и 7). Более того, теорема Эйлера гарантирует, что $4$ $\equiv$ $1 (по модулю 8)$ для всех взаимно простых $чисел$ с 8, но 4 не является наименьшим таким показателем. Примитивными $λ$ -корнями по модулю 8 являются 3, 5 и 7. Примитивных корней по модулю 8 нет. $a\in \{1,3,5,7\}~,$

Повторение для λ ( n )

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

\lambda (n)={\begin{cases}\varphi (n)& {\text{if }}n{\text{ равно 1, 2, 4 или нечетной простой степени,}}\\ {\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\ лямбда (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2 }\ldots n_{k}{\text{ где }}n_{1},n_{2},\ldots ,n_{k}{\text{ — степени различных простых чисел.}}\end{cases}}

Тотент Эйлера для степени простого числа, то есть числа $p$ $r$ с $p$ простым числом и $r$ $\geq 1$ , определяется выражением

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

Теоремы Кармайкла

Кармайкл доказал две теоремы, которые вместе устанавливают, что если $λ$ $($ $n$ $)$ рассматривается как определенное повторением предыдущего раздела, то оно удовлетворяет свойству, указанному во введении, а именно, что это наименьшее положительное целое число $m$ такое, что для всех $относительно$ простое число для $n$ . $a^{m}\equiv 1{\pmod {n}}$

Теорема 1. Если $a$ относительно просто с $n$ , то . ^[2] $a^{\lambda (n)}\equiv 1{\pmod {n}}$

Это означает, что порядок каждого элемента мультипликативной группы целых чисел по модулю $n$ делит $λ$ $($ $n$ $)$ . Кармайкл называет элемент $a$ , для которого является наименьшей степенью $конгруэнтного$ 1 (mod $n$ ), примитивным λ-корнем по модулю n . ^[3] (Это не следует путать с примитивным корнем по модулю n , который Кармайкл иногда называет примитивным корнем по модулю $n$ .) $a^{\lambda (n)}$ $\varphi$

Теорема 2. Для каждого натурального числа $n$ существует примитивный $λ$ -корень по модулю $n$ . Более того, если $g$ — такой корень, то существуют примитивные $λ$ -корни, конгруэнтные степеням $g$ . ^[4] $\varphi (\lambda (n))$

Если $g$ является одним из примитивных $λ$ -корней, гарантированных теоремой, то он не имеет целочисленных положительных решений $m,$ меньших, чем $λ$ $($ $n$ $)$ , что показывает, что не существует такого положительного $m$ $<$ $λ$ $($ $n$ $)$ , что для всех $чисел$ , относительно простых с $n$ . $g^{m}\equiv 1{\pmod {n}}$ $a^{m}\equiv 1{\pmod {n}}$

Из второго утверждения теоремы 2 не следует, что все примитивные $λ$ -корни по модулю $n$ конгруэнтны степеням одного корня $g$ . ^[5] Например, если $n$ $= 15$ , то $λ$ $($ $n$ $) = 4$ в то время как и . Существует четыре примитивных $λ$ -корня по модулю 15, а именно 2, 7, 8 и 13 при . Корни 2 и 8 конгруэнтны степеням друг друга, а корни 7 и 13 конгруэнтны степеням друг друга, но ни 7, ни 13 не конгруэнтны степени 2 или 8, и наоборот. Остальные четыре элемента мультипликативной группы по модулю 15, а именно 1, 4 (что удовлетворяет ), 11 и 14, не являются примитивными $λ$ -корнями по модулю 15. $\varphi (n)=8$ $\varphi (\lambda (n))=2$ $1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}$ $4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}$

Для контрастного примера: если $n$ $= 9$ , то и . Есть два примитивных $λ$ -корня по модулю 9, а именно 2 и 5, каждый из которых конгруэнтен в пятой степени другого. Они также оба являются примитивными корнями по модулю 9. $\lambda (n)=\varphi (n)=6$ $\varphi (\lambda (n))=2$ $\varphi$

Свойства функции Кармайкла

В этом разделе целое число делится на ненулевое целое, если существует такое целое число, что . Это написано как $п$ $м$ $k$ $n=км$

м\середина п.

Следствие минимальности λ ( n )

Предположим, что $a$ $m$ $\equiv 1 (mod$ $n$ $)$ для всех чисел, $взаимно$ простых с $n$ . Тогда $λ$ $($ $п$ $) |$ $м$ .

Доказательство: если $m$ $=$ $kλ$ $($ $n$ $) +$ $r$ с $0 \leq$ $r$ $<$ $λ$ $($ $n$ $)$ , то

a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}= a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}

для всех чисел $взаимно$ простое с $n$ . Отсюда следует, что $r = 0$ , поскольку $r$ $<$ $λ$ $($ $n$ $)$ и $λ$ $($ $n$ $)$ — минимальный положительный показатель степени, для которого сравнение выполняется для всех чисел, взаимно $простых$ с $n$ .

λ ( n ) делит φ ( n )

Это следует из элементарной теории групп , поскольку показатель любой конечной группы должен делить порядок группы. $λ$ $($ $n$ $)$ — показатель мультипликативной группы целых чисел по модулю $n$ , а $φ$ $($ $n$ $)$ — порядок этой группы. В частности, они должны быть равны в тех случаях, когда мультипликативная группа является циклической из-за существования примитивного корня , что имеет место для нечетных простых степеней.

Таким образом, мы можем рассматривать теорему Кармайкла как усиление теоремы Эйлера .

Делимость

a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)

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

По определению, для любого целого числа с (и, следовательно, также ), мы имеем это и, следовательно , . Это устанавливает, что для всех $k$ относительно просто $a$ . По доказанному выше следствию минимальности имеем . $k$ $\gcd(k,b)=1$ $\gcd(k,a)=1$ $b\,|\,(k^{\lambda (b)}-1)$ $a\,|\,(k^{\lambda (b)}-1)$ $k^{\lambda (b)}\equiv 1{\pmod {a}}$ $\lambda (a)\,|\,\lambda (b)$

Состав

Для всех натуральных чисел $a$ и $b$ справедливо соотношение

\lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))

Это непосредственное следствие повторяемости функции Кармайкла.

Экспоненциальная длина цикла

Если — наибольший показатель степени в простой факторизации n , то для всех $a (включая те$ $,$ которые не взаимно просты с $n$ ) и всех $r$ $\geq$ $r$ $max$ , $r_{\mathrm {max} }=\max _{i}\{r_{i}\}$ $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$

a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.

В частности, для свободного от квадратов $n$ ( $r$ $max$ $= 1$ ) для всех $a$ мы имеем

a\equiv a^{\lambda (n)+1}{\pmod {n}}.

Средняя стоимость

Для любого $n$ $\geq 16$ : ^[6]^[7]

{\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1) ))\ln \ln n/(\ln \ln \ln n)}

(далее называемое приближением Эрдеша) с постоянной

B:=e^{-\gamma }\prod _{p\in \mathbb {P}}\left({1- {\frac {1}{(p-1)^{2}(p +1)}}}\вправо)\приблизительно 0,34537

и $γ$ $\approx 0,57721$ — постоянная Эйлера–Машерони .

В следующей таблице представлен некоторый обзор первых $226 - 1 = 67108863$ значений $функции λ$ как для точного среднего, так и для его приближения Эрдеша.

Дополнительно дается некоторый обзор более доступных значений «логарифм по логарифму» $LoL( n ) :=.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}пер λ ( п )/в н$ с

$ЛоЛ(п) > 4 / 5 \Leftrightarrow λ (п) > п 4 / 5$ .

Там запись таблицы в строке номер 26 в столбце

$% ЛоЛ > 4 / 5$ → 60.49

указывает на то, что 60,49% (≈40 000 000 ) целых чисел $1 \leq n \leq 67108863$ имеют $λ$ $($ $n$ $) >$ $n$ $4 / 5$ это означает, что большинство значений $λ$ является экспоненциальным по длине $l$ $:= log$ $2$ $($ $n$ $)$ входного $n$ , а именно

\left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right) ^{\frac {4}{5}}=n^{\frac {4}{5}}.

Преобладающий интервал

Для всех чисел $N$ и всех положительных целых чисел, кроме $o$ $($ $N$ $)$ ^[8], $n$ $\leq$ $N$ («преобладающее» большинство):

\lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}

с константой ^[7]

A:=-1+\sum _{p\in \mathbb {P} {\frac {\ln p}{(p-1)^{2}}}\approx 0,2269688

Нижние границы

Для любого достаточно большого числа $N$ и любого $∆ \geq (ln ln N) 3$ существует не более

N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)

целые положительные числа $n$ $\leq N$ такие, что $λ$ $($ $n$ $) \leq$ $ne$ $-Δ$ . ^[9]

Минимальный заказ

Для любой последовательности $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots$ натуральных чисел любая константа $0 <$ $c$ $<$ $1 / пер. 2$ , и любой достаточно большой $i$ : ^[10]^[11]

\lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.

Маленькие значения

Для константы $c$ и любого достаточно большого положительного $A$ существует целое число $n$ $>$ $A$ такое, что ^[11]

\lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.

Более того, $n$ имеет вид

n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q

для некоторого целого числа без квадратов $m$ $< (ln$ $A$ $)$ $c$ $ln ln ln$ $A$ . ^[10]

Изображение функции

Множество значений функции Кармайкла имеет счетную функцию ^[12]

{\frac {x}{(\ln x)^{\eta +o(1)}}},

где

\eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607

Использование в криптографии

Функция Кармайкла важна в криптографии из-за ее использования в алгоритме шифрования RSA .

Доказательство теоремы 1.

Для $n$ $=$ $p$ , простого числа, теорема 1 эквивалентна малой теореме Ферма:

a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.

Для простых степеней $p$ $r$ , $r$ $> 1$ , если

a^{p^{r-1}(p-1)}=1+hp^{r}

выполняется для некоторого целого числа $h$ , то возведение обеих частей в степень $p$ дает

a^{p^{r}(p-1)}=1+h'p^{r+1}

для некоторого другого целого числа . По индукции следует, что для всех $a$ относительно просто с $p$ и, следовательно, с $p$ $r$ . Это устанавливает теорему для $n$ $= 4$ или любой нечетной степени простого числа. $h'$ $a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}$

Повышение резкости результата для высших степеней двойки

Для $числа$ , взаимно простого с (степенью) 2, имеем $a$ $= 1 + 2$ $h$ $2$ для некоторого целого числа $h$ $2$ . Затем,

a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}

где целое число. При $r$ $= 3$ это пишется $h_{3}$

a^{2^{r-2}}=1+2^{r}h_{r}.

Возведение в квадрат обеих сторон дает

a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},

где целое число. По индукции следует, что $h_{r+1}$

a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}

для всех и всех $взаимнопростых$ . ^[13] $r\geq 3$ $2^{r}$

Целые числа с несколькими простыми делителями

По теореме об уникальной факторизации любое $n$ $> 1$ может быть записано единственным образом как

n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}

где $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $k$ — простые числа, а $r$ $1$ $,$ $r$ $2$ $, ...,$ $r$ $k$ — положительные целые числа. Результаты для простых степеней показывают, что при , $1\leq j\leq k$

a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.

Отсюда следует, что

a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,

где, как следует из рекуррентности,

\lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.

Из китайской теоремы об остатках можно сделать вывод, что

a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.

Смотрите также

Число Кармайкла

Примечания

^ Кармайкл, Роберт Дэниел (1910). «Заметка о новой функции теории чисел». Бюллетень Американского математического общества . 16 (5): 232–238. дои : 10.1090/S0002-9904-1910-01892-9 .
^ Кармайкл (1914) стр.40
^ Кармайкл (1914) стр.54
^ Кармайкл (1914) стр.55
^ Кармайкл (1914) стр.56
^ Теорема 3 в Эрдеше (1991).
^ аб Шандор и Крстичи (2004) стр.194
^ Теорема 2 Эрдеша (1991) 3. Нормальный порядок. (стр.365)
^ Теорема 5 Фридлендера (2001).
^ ab Теорема 1 в Эрдеше (1991)
^ аб Шандор и Крстичи (2004) стр.193
^ Форд, Кевин; Лука, Флориан; Померанс, Карл (27 августа 2014 г.). «Образ λ -функции Кармайкла». Алгебра и теория чисел . 8 (8): 2009–2026. arXiv : 1408.6506 . дои : 10.2140/ant.2014.8.2009. S2CID 50397623.
^ Кармайкл (1914), стр. 38–39.