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

Функция $λ$ Кармайкла : $λ$ $($ $n$ $)$ для $1 \leq$ $n$ $\leq 1000$ (по сравнению с функцией $φ$ Эйлера )

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

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

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

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

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

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

$n = 5$ . Множество чисел, меньших и взаимно простых с 5, равно ${1,2,3,4$ }. Следовательно, функция Эйлера имеет значение $φ$ $(5) = 4$ , а значение функции Кармайкла $λ$ $(5)$ должно быть делителем 4. Делитель 1 не удовлетворяет определению функции Кармайкла, посколькуза исключением. Также не удовлетворяет и 2, поскольку. Следовательно, $λ$ $(5) = 4$ . Действительно,. Оба числа 2 и 3 являются примитивными $λ$ -корнями по модулю 5, а также примитивными корнями по модулю 5. $a^{1}\not \equiv 1{\pmod {5}}$ $a\equiv 1{\pmod {5}}$ $2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}$ $1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}$
$n = 8.$ Множество чисел, меньших и взаимно простых с 8, равно ${1,3,5,7}$ . Следовательно, $φ$ $(8) = 4$ и $λ$ $(8)$ должно быть делителем 4. Фактически, $λ$ $(8) = 2$ , так как. Первообразные $λ$ -корни по модулю 8 равны 3, 5 и 7. Первообразных корней по модулю 8 нет. $1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}$

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

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

\lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or a unetcative simple degree,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are degrees of different простые числа.}}\end{cases}}

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

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

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

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

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

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

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

Если $g$ является одним из примитивных $λ$ -корней, гарантированных теоремой, то не имеет положительных целых решений $m,$ меньших $λ$ $($ $n$ $)$ , что показывает, что не существует положительного $m$ $<$ $λ$ $($ $n$ $)$ такого, что для всех $a$ взаимно просто с $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$

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

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

m\mid n.

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

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

Доказательство: Если $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}}

для всех чисел $a$ , взаимно простых с $n$ . Отсюда следует, что $r = 0$ , поскольку $r$ $<$ $λ$ $($ $n$ $)$ и $λ$ $($ $n$ $)$ является минимальным положительным показателем, для которого сравнение выполняется для всех $a,$ взаимно простых с $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)}}}\right)\approx 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);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ln λ ( n )/в н⁠$ с

$ЛоЛ(н) > ⁠ 4 / 5 ⁠ \Leftrightarrow λ (n) > n ⁠ 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. doi : 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 . doi : 10.2140/ant.2014.8.2009. S2CID 50397623.
^ Кармайкл (1914) стр.38–39

Ссылки

Эрдеш, Пол ; Померанс, Карл ; Шмутц, Эрик (1991). «Лямбда-функция Кармайкла». Акта Арифметика . 58 (4): 363–385. дои : 10.4064/aa-58-4-363-385 . ISSN 0065-1036. МР 1121092. Збл 0734.11047.
Фридлендер, Джон Б .; Померанс, Карл; Шпарлинский, Игорь Э. (2001). «Период генератора мощности и малые значения функции Кармайкла». Математика вычислений . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
Шандор, Йожеф; Крстичи, Борислав (2004). Справочник по теории чисел II . Дордрехт: Клювер Академик. стр. 32–36, 193–195. ISBN 978-1-4020-2546-4. Збл 1079.11001.
Кармайкл, Роберт Д. [1914]. Теория чисел в проекте Гутенберг