~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ BB446BAEA8F437768E26BCE44BF6FAE6__1710078840 ✰
Заголовок документа оригинал.:
✰ Carmichael function - Wikipedia ✰
Заголовок документа перевод.:
✰ Функция Кармайкла — Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Carmichael_function ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/bb/e6/bb446baea8f437768e26bce44bf6fae6.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/bb/e6/bb446baea8f437768e26bce44bf6fae6__translat.html ✰
Дата и время сохранения документа:
✰ 11.06.2024 09:28:08 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 10 March 2024, at 16:54 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Arc.Ask3.ru: далее начало оригинального документа

Функция Кармайкла — Википедия Jump to content

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

Из Википедии, бесплатной энциклопедии
Кармайкла λ Функция : λ ( n ) для 1 ≤ n ≤ 1000 (по сравнению с функцией Эйлера φ )

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

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

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

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

н 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
λ ( п ) 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20 12 18 6 28 4 30 8 10 16 12 6
φ ( п ) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20 16 24 12

Числовые примеры [ править ]

  1. Функция Кармайкла в точке 5 равна 4, λ (5) = 4 , поскольку для любого числа взаимно простыми до 5, т.е. есть с а именно 1 1⋅4 = 1 4 ≡ 1 (против 5) , 2 4 = 16 ≡ 1 (по модулю 5) , 3 4 = 81 ≡ 1 (по модулю 5) и 4 2⋅2 = 16 2 ≡ 1 2 (мод 5) . И это m = 4 является наименьшим показателем степени с этим свойством, потому что также.)
    Эйлера Более того, функция тотента в точке 5 равна 4, φ (5) = 4 , поскольку существует ровно 4 числа меньше 5 и взаимно простых с ними (1, 2, 3 и 4). Теорема Эйлера утверждает, что 4 ≡ 1 (по модулю 5) для всех чисел , взаимно простых с 5, а 4 — наименьший такой показатель. И 2, и 3 являются примитивными λ -корнями по модулю 5, а также примитивными корнями по модулю 5.
  2. Функция Кармайкла в 8 равна 2, λ (8) = 2 , потому что для любого числа, взаимно простого с 8, т.е. он утверждает, что 2 ≡ 1 (по модулю 8) . А именно, 1 1⋅2 = 1 2 ≡ 1 (мод. 8) , 3 2 = 9 ≡ 1 (по модулю 8) , 5 2 = 25 ≡ 1 (по модулю 8) и 7 2 = 49 ≡ 1 (по модулю 8) .
    Эйлера Тотент-функция в 8 равна 4, φ (8) = 4 , потому что существует ровно 4 числа меньше 8 и взаимно простых с 8 (1, 3, 5 и 7). Более того, теорема Эйлера утверждает, что 4 ≡ 1 (по модулю 8) для всех чисел , взаимно простых с 8, но 4 не является наименьшим таким показателем. Примитивными λ -корнями по модулю 8 являются 3, 5 и 7. Примитивных корней по модулю 8 нет.

Повторение для λ ( n ) [ править ]

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

Тотент Эйлера для простой степени, т. е. числа p р с p prime и r ≥ 1 , определяется выражением

Теоремы Кармайкла [ править ]

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

Теорема 1. Если a относительно простое с n , то . [2]

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

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

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

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

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

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

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

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

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

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

λ ( n ) делит φ ( n ) [ редактировать ]

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

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

Делимость [ править ]

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

По определению, для любого целого числа с (и, следовательно, также ), у нас такое есть , и поэтому . Это устанавливает, что для всех k относительно простого с a . По доказанному выше следствию минимальности имеем .

Состав [ править ]

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

.

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

Длина экспоненциального цикла [ править ]

Если является наибольшим показателем в простой факторизации n n , то для всех a (включая те, которые не взаимно просты с ) и всех r r max ,

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

Среднее значение [ править ]

Для любого n ≥ 16 : [6] [7]

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

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

В следующей таблице представлен некоторый обзор первых двух 26 – 1 = 67 108 863 значений функции λ как для точного среднего, так и для его приближения Эрдеша.

Дополнительно дается некоторый обзор более доступных значений «логарифм по логарифму» LoL( n ) := ln λ ( n ) / ln n с

  • ЛоЛ( п ) > 4 / 5 λ ( п ) > п 4 / 5 .

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

  • % ЛоЛ > 4 / 5   → 60.49

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

н п = 2 н – 1 сумма
средний
Лес средний Лес /
точное среднее значение
Лол средний % ЛоЛ > 4 / 5 % ЛоЛ > 7 / 8
5 31 270 8.709677 68.643 7.8813 0.678244 41.94 35.48
6 63 964 15.301587 61.414 4.0136 0.699891 38.10 30.16
7 127 3574 28.141732 86.605 3.0774 0.717291 38.58 27.56
8 255 12994 50.956863 138.190 2.7119 0.730331 38.82 23.53
9 511 48032 93.996086 233.149 2.4804 0.740498 40.90 25.05
10 1023 178816 174.795699 406.145 2.3235 0.748482 41.45 26.98
11 2047 662952 323.865169 722.526 2.2309 0.754886 42.84 27.70
12 4095 2490948 608.290110 1304.810 2.1450 0.761027 43.74 28.11
13 8191 9382764 1145.496765 2383.263 2.0806 0.766571 44.33 28.60
14 16383 35504586 2167.160227 4392.129 2.0267 0.771695 46.10 29.52
15 32767 134736824 4111.967040 8153.054 1.9828 0.776437 47.21 29.15
16 65535 513758796 7839.456718 15225.43 0 1.9422 0.781064 49.13 28.17
17 131071 1964413592 14987.40066 0 28576.97 0 1.9067 0.785401 50.43 29.55
18 262143 7529218208 28721.79768 0 53869.76 0 1.8756 0.789561 51.17 30.67
19 524287 28935644342 55190.46694 0 101930.9 00 1.8469 0.793536 52.62 31.45
20 1048575 111393101150 106232.8409 00 193507.1 00 1.8215 0.797351 53.74 31.83
21 2097151 429685077652 204889.9090 00 368427.6 00 1.7982 0.801018 54.97 32.18
22 4194303 1660388309120 395867.5158 00 703289.4 00 1.7766 0.804543 56.24 33.65
23 8388607 6425917227352 766029.1187 00 1345633 .000 1.7566 0.807936 57.19 34.32
24 16777215 24906872655990 1484565.386 000 2580070 .000 1.7379 0.811204 58.49 34.43
25 33554431 96666595865430 2880889.140 000 4956372 .000 1.7204 0.814351 59.52 35.76
26 67108863 375619048086576 5597160.066 000 9537863 .000 1.7041 0.817384 60.49 36.73

Преобладающий интервал [ править ]

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

с постоянной [7]

Нижние границы [ править ]

Для любого достаточно большого числа N и любого ∆ ≥ (ln ln N ) 3 , есть максимум

целые положительные числа n ≤ N такие, что λ ( n ) ≤ ne . [9]

Минимальный заказ [ править ]

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

Маленькие значения [ править ]

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

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

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

Изображение функции [ править ]

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

где

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

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

Доказательство теоремы 1 [ править ]

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

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

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

для какого-то другого целого числа . По индукции отсюда следует, что для всех a относительно простых с p и, следовательно, с p р . Это устанавливает теорему для n = 4 или любой нечетной степени простого числа.

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

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

,

где является целым числом. При r = 3 это пишется

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

где является целым числом. По индукции следует, что

для всех и все простые взаимно . [13]

Целые числа с несколькими простыми множителями [ править ]

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

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

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

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

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

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

Примечания [ править ]

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

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

Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: BB446BAEA8F437768E26BCE44BF6FAE6__1710078840
URL1:https://en.wikipedia.org/wiki/Carmichael_function
Заголовок, (Title) документа по адресу, URL1:
Carmichael function - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)