В теории чисел , Функция Эйлер подсчитывает положительные целые числа до заданного целого числа п , которые взаимно просты с п . Он написан с использованием греческой буквы фи как или же , и может также называться фи-функцией Эйлера . Другими словами, это количество целых чисел k в диапазоне 1 ≤ k ≤ n, для которых наибольший общий делитель gcd ( n , k ) равен 1. [2] [3] Целые числа k этой формы иногда равны упоминается как totatives из п .
Например, сумма n = 9 - это шесть чисел 1, 2, 4, 5, 7 и 8. Все они взаимно просты с 9, но три других числа в этом диапазоне, 3, 6 и 9, не являются. , так как gcd (9, 3) = gcd (9, 6) = 3 и gcd (9, 9) = 9 . Следовательно, φ (9) = 6 . В качестве другого примера φ (1) = 1, поскольку для n = 1 единственное целое число в диапазоне от 1 до n - это 1, а НОД (1, 1) = 1 .
Общая функция Эйлера является мультипликативной функцией , что означает, что если два числа m и n взаимно просты, то φ ( mn ) = φ ( m ) φ ( n ) . [4] [5] Данная функция выдает приказ о мультипликативной группе целых чисел по модулю п (на группу из блоков в кольце ℤ / п ℤ ). [6] Он также используется для определения системы шифрования RSA .
История, терминология и обозначения
Леонард Эйлер ввел эту функцию в 1763 году. [7] [8] [9] Однако в то время он не выбрал какой-либо конкретный символ для ее обозначения. В публикации 1784 года Эйлер дополнительно изучил функцию, выбрав для ее обозначения греческую букву π : он написал πD для «множества чисел меньше D , не имеющих с ним общего делителя». [10] Это определение отличается от текущего определения функции totient при D = 1, но в остальном остается таким же. Ныне стандартное обозначение [8] [11] φ ( A ) происходит из трактата Гаусса об арифметических исследованиях 1801 года [12] [13], хотя Гаусс не использовал скобки вокруг аргумента и написал φA . Таким образом, ее часто называют phi-функцией Эйлера или просто phi-функцией .
В 1879 году, JJ Сильвестр ввел термин totient для этой функции, [14] [15] поэтому он также упоминается как функции Эйлера totient , в Эйлера totient или Эйлера в . Тотиент Джордана является обобщением теории Эйлера.
Cototient из п определяется как п - ф ( п ) . Он подсчитывает количество положительных целых чисел, меньших или равных n , у которых есть хотя бы один простой делитель, общий с n .
Вычисление тотентифицирующей функции Эйлера
Есть несколько формул для вычисления φ ( n ) .
Формула произведения Эйлера
Говорится
где произведение находится над различными простыми числами, делящими n . (Обозначения см. В разделе Арифметическая функция .)
Эквивалентная формулировка для , где - различные простые числа, делящие n , это:
Доказательство этих формул зависит от двух важных фактов.
Phi - мультипликативная функция
Это означает, что если gcd ( m , n ) = 1 , то φ ( m ) φ ( n ) = φ ( mn ) . Схема доказательства: пусть A , B , C - множества натуральных чисел, взаимно простых с m , n , mn и меньших, чем m , n , mn , соответственно, так что | А | = φ ( m ) и т. д. Тогда существует биекция между A × B и C по китайской теореме об остатках .
Значение фи для аргумента первичной мощности
Если p простое и k ≥ 1 , то
Доказательство : поскольку p - простое число, единственными возможными значениями gcd ( p k , m ) являются 1, p , p 2 , ..., p k , и это единственный способ иметь gcd ( p k , m )> 1 означает, что m кратно p , то есть m = p , 2 p , 3 p , ..., p k - 1 p = p k , и таких кратных p k - 1 меньше, чем p k . Следовательно, все остальные p k - p k - 1 числа взаимно просты с p k .
Доказательство формулы произведения Эйлера
Основная теорема арифметики утверждает , что если п > 1 существует единственное выражениегде p 1 < p 2 <... < p r - простые числа и каждое k i ≥ 1 . (Случай n = 1 соответствует пустому произведению.) Многократное использование мультипликативного свойства φ и формулы для φ ( p k ) дает
Это дает обе версии формулы произведения Эйлера.
Альтернативное доказательство, которое не требует мультипликативного свойства, вместо этого использует принцип включения-исключения, примененный к множеству, исключая наборы целых чисел, делящихся на простые делители.
Пример
На словах: различные простые делители числа 20 равны 2 и 5; половина из двадцати целых чисел от 1 до 20 делится на 2, остается десять; пятая часть из них делится на 5, в результате чего восемь чисел взаимно просты с 20; это: 1, 3, 7, 9, 11, 13, 17, 19.
Альтернативная формула использует только целые числа:
преобразование Фурье
Totient является дискретным преобразованием Фурье от НОДА , оценивается в 1. [16] Пусть
где x k = gcd ( k , n ) для k ∈ {1,…, n } . потом
Действительная часть этой формулы:
Например, используя а также :
В отличие от произведения Эйлера и формулы суммы делителей, здесь не требуется знать множители n . Однако он включает в себя вычисление наибольшего общего делителя n и каждого положительного целого числа меньше n , что в любом случае достаточно для факторизации.
Сумма делителя
Свойство, установленное Гауссом [17], что
где сумма берется по всем положительным делителям d числа n , можно доказать несколькими способами. (См. Условные обозначения в разделе « Арифметическая функция» .)
Одно из доказательств состоит в том, чтобы отметить, что φ ( d ) также равно количеству возможных образующих циклической группы C d ; В частности, если С д = ⟨ г ⟩ с г д = 1 , то г к представляет собой генератор для каждого к взаимно просто д . Поскольку каждый элемент C n порождает циклическую подгруппу , а все подгруппы C d ⊆ C n порождаются некоторым элементом C n , формула следует. [18] Аналогично, формула может быть получена с помощью того же аргумента, что и мультипликативная группа корней n- й степени из единицы и примитивных корней d- й степени из единицы.
Формулу можно также получить из элементарной арифметики. [19] Например, пусть n = 20 и рассмотрим положительные дроби до 1 со знаминателем 20:
Поместите их в самые низкие термины:
Эти двадцать фракций все положительные k/d≤ 1, знаменателями которого являются делители d = 1, 2, 4, 5, 10, 20 . Дроби со знаменателем 20 - это дроби, числители которых взаимно просты с 20, а именно: 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20; по определению это дроби φ (20) . Аналогичным образом , существует ф (10) фракции с знаменателем 10, и ф (5) дроби с знаменателем 5 и т.д. Таким образом, множество из двадцати фракций разделяются на подмножества размера ф ( г ) для каждого д делящихся 20. Аналогичного рассуждения применяется для любого n.
Обращение Мёбиуса, примененное к формуле суммы делителей, дает
где μ - функция Мёбиуса , мультипликативная функция, определяемая формулой а также для каждого простого p и k ≥ 1 . Эта формула также может быть получена из формулы произведения путем умножения получить
Пример:
Некоторые ценности
Первые 100 значений (последовательность A000010 в OEIS ) показаны в таблице и на графике ниже:
φ ( n ) для 1 ≤ n ≤ 100 + 1 2 3 4 5 6 7 8 9 10 0 1 1 2 2 4 2 6 4 6 4 10 10 4 12 6 8 8 16 6 18 8 20 12 10 22 8 20 12 18 12 28 год 8 30 30 16 20 16 24 12 36 18 24 16 40 40 12 42 20 24 22 46 16 42 20 50 32 24 52 18 40 24 36 28 год 58 16 60 60 30 36 32 48 20 66 32 44 год 24 70 70 24 72 36 40 36 60 24 78 32 80 54 40 82 24 64 42 56 40 88 24 90 72 44 год 60 46 72 32 96 42 60 40
На графике справа верхняя линия y = n - 1 является верхней границей, действительной для всех n, кроме одного, и достигается тогда и только тогда, когда n - простое число. Простая нижняя оценка, что довольно рыхло: на самом деле нижняя граница графика пропорциональнап/журнал журнал n. [20]
Теорема Эйлера
Это утверждает , что если и п являются взаимно простыми , то
Частный случай, когда n простое, известен как малая теорема Ферма .
Это следует из теоремы Лагранжа и тот факт , что φ ( п ) является порядок в мультипликативной группе целых чисел по модулю п .
RSA криптосистемы на основе этой теоремы: это означает , что обратная функции ↦ е мод п , где е является (общественного) шифрования показатель, функция б ↦ б д мод п , где г , тем (частное ) показатель расшифровки является мультипликативным обратным к e по модулю φ ( n ) . Таким образом, сложность вычисления φ ( n ) без знания факторизации n является сложностью вычисления d : это известно как проблема RSA, которая может быть решена путем факторизации n . Владелец закрытого ключа знает факторизацию, поскольку закрытый ключ RSA создается путем выбора n как произведения двух (случайно выбранных) больших простых чисел p и q . Публично раскрывается только n , и, учитывая сложность факторизации больших чисел, у нас есть гарантия, что никто другой не знает факторизации.
Другие формулы
- Обратите внимание на особые случаи
- Сравните это с формулой
- (См. Наименьшее общее кратное .)
- φ ( n ) четно при n ≥ 3 . Более того, если n имеет r различных нечетных простых множителей, 2 r | φ ( п )
- Для любых a > 1 и n > 6 таких, что 4 ∤ n, существует l ≥ 2 n такое, что l | φ ( a n - 1) .
- где rad ( n ) - радикал числа n (произведение всех различных простых чисел, делящих n ).
- [21]
- ( [22] цитируется в [23] )
- [22]
- [24]
- [24]
- (где γ - постоянная Эйлера – Маскерони ).
- где m > 1 - натуральное число, а ω ( m ) - количество различных простых делителей числа m . [25]
Личность Менона
В 1965 г. П. Кесава Менон доказал, что
где d ( n ) = σ 0 ( n ) - количество делителей числа n .
Формулы с золотым сечением
Шнайдер [26] нашел пару тождеств, соединяющих функцию totient, золотое сечение и функцию Мёбиуса μ ( n ) . В этом разделе φ ( n ) - функция тотализатора, а ϕ = 1 + √ 5/2= 1,618… это золотое сечение.
Они есть:
а также
Их вычитание дает
Применение экспоненциальной функции к обеим сторонам предыдущего тождества дает формулу бесконечного произведения для e :
Доказательство основано на двух формулах
Производящие функции
Ряд Дирихле для ф ( п ) можно записать в терминах дзета - функции Римана , как: [27]
Серии Ламберта производящей функцией является [28]
который сходится при | q | <1 .
Оба эти утверждения доказываются манипуляциями с элементарными рядами и формулами для φ ( n ) .
Скорость роста
По словам Харди и Райта, порядок φ ( n ) «всегда почти n ». [29]
Первый [30]
но поскольку n стремится к бесконечности, [31] для всех δ > 0
Эти две формулы можно доказать, используя немногим больше, чем формулы для φ ( n ) и функции суммы делителей σ ( n ) .
Фактически при доказательстве второй формулы неравенство
верно для n > 1 , доказано.
У нас также есть [20]
Здесь γ является постоянная Эйлера , γ = 0,577215665 ... , поэтому е γ = 1.7810724 ... и е - γ = 0.56145948 ... .
Для доказательства этого совсем не требуется теорема о простых числах . [32] [33] Поскольку log log n стремится к бесконечности, эта формула показывает, что
На самом деле, правда больше. [34] [35] [36]
а также
Второе неравенство показал Жан-Луи Николя . Рибенбойм говорит: «Метод доказательства интересен тем, что неравенство показано, во-первых, в предположении, что гипотеза Римана верна, а во-вторых, в противоположном предположении». [36]
Для среднего порядка имеем [22] [37]
благодаря Арнольду Вальфизу , в его доказательстве используются оценки экспоненциальных сумм, полученные И. М. Виноградовым и Н. М. Коробовым (в настоящее время это наиболее известная оценка такого типа). «Большой O » обозначает количество, которое ограничено константой , кратной функции п внутри круглых скобок (которая мала по сравнению с п 2 ).
Этот результат может быть использован для доказательства [38], что вероятность того, что два случайно выбранных числа будут взаимно простыми, равна 6/π 2.
Соотношение последовательных значений
В 1950 году Сомаяджулу доказал [39] [40]
В 1954 году Шинцель и Серпинский усилили это, доказав [39] [40], что множество
является плотным в положительных действительных чисел. Они также доказали [39], что множество
плотно в интервале (0,1).
Totient числа
Номер totient является значением Функция Эйлера: то есть, т , для которых имеется по меньшей мере один п , для которых ф ( п ) = т . Валентность или кратность из числа totient т есть число решений этого уравнения. [41] Не значащее число - это натуральное число, которое не является общим числом. Каждое нечетное целое число, превышающее 1, тривиально неточность. Существует также бесконечно много четных не значащих элементов [42], и действительно, каждое положительное целое число имеет кратное, которое не является четным не значе нием. [43]
Количество общих чисел до заданного предела x равно
для постоянной C = 0.8178146 ... . [44]
Если считать по кратности, количество общих чисел до заданного предела x равно
где погрешность R порядка не болееИкс/(журнал x ) kдля любого положительного k . [45]
Известно, что кратность m бесконечно часто превышает m δ при любом δ <0,55655 . [46] [47]
Теорема Форда
Форд (1999) доказал, что для любого целого числа k ≥ 2 существует общее число m кратности k : то есть, для которого уравнение φ ( n ) = m имеет ровно k решений; этот результат был ранее высказали предположение по Серпинскому , [48] , и это было получено в результате Шинцель в гипотезе H . [44] В самом деле, каждая встречающаяся множественность происходит бесконечно часто. [44] [47]
Однако неизвестно число m с кратностью k = 1 . Гипотеза Кармайкла о тотализирующей функции - это утверждение, что такой m не существует . [49]
Идеальные общие числа
Приложения
Циклотомия
В последнем разделе « Исследований» [50] [51] Гаусс доказывает [52], что правильный n -угольник можно построить с помощью линейки и циркуля, если φ ( n ) является степенью 2. Если n является степенью нечетной простое число формула для totient гласит, что его totient может быть степенью двойки, только если n - первая степень, а n - 1 - степень 2. Простые числа, которые на единицу больше, чем степень двойки, называются простыми числами Ферма , а известно только пять: 3, 5, 17, 257 и 65537. Ферма и Гаусс знали об этом. Никто не смог доказать, есть ли еще.
Таким образом, регулярный п - угольник имеет стрэйтэдж-и-компас строительство , если п является произведением различных простых чисел Ферма и любой степень 2. Первые несколько такого п являются [53]
- 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, ... (последовательность A003401 в OEIS ).
Криптосистема RSA
Настройка системы RSA включает выбор больших простых чисел p и q , вычисление n = pq и k = φ ( n ) и нахождение двух чисел e и d, таких что ed ≡ 1 (mod k ) . Числа n и e («ключ шифрования») публикуются, а d («ключ дешифрования») остается закрытым.
Сообщение, представленное целым числом m , где 0 < m < n , шифруется путем вычисления S = m e (mod n ) .
Он расшифровывается путем вычисления t = S d (mod n ) . Теорема Эйлера может быть использована, чтобы показать, что если 0 < t < n , то t = m .
Безопасность системы RSA будет поставлена под угрозу, если число n может быть разложено на множители или если φ ( n ) может быть вычислен без факторизации n .
Нерешенные проблемы
Гипотеза Лемера
Если p простое, то φ ( p ) = p - 1 . В 1932 году Д.Х. Лемер спросил, существуют ли какие-нибудь составные числа n такие, что φ ( n ) делит n - 1 . Никто не известен. [54]
В 1933 году он доказал, что если такое n существует, оно должно быть нечетным, бесквадратным и делимым не менее чем на семь простых чисел (т.е. ω ( n ) ≥ 7 ). В 1980 году Коэн и Хагис доказали, что n > 10 20 и ω ( n ) ≥ 14 . [55] Далее, Хагис показал, что если 3 делит n, то n > 10 1937042 и ω ( n ) ≥ 298848 . [56] [57]
Гипотеза Кармайкла
Это заявляет , что нет никакого числа п с тем свойством , что для всех остальных чисел т , т ≠ п , ф ( т ) ≠ ф ( п ) . См . Теорему Форда выше.
Как указано в основной статье, если существует единственный контрпример к этой гипотезе, должно быть бесконечно много контрпримеров, а самый маленький из них имеет не менее десяти миллиардов цифр в базе 10. [41]
Смотрите также
- Функция Кармайкла
- Гипотеза Даффина – Шеффера
- Обобщения малой теоремы Ферма
- Сильно составное число
- Мультипликативная группа целых чисел по модулю n
- Рамануджанская сумма
- Тотент сумматорная функция
Заметки
- ^ "Функция Эйлера" . Ханская академия . Проверено 26 февраля 2016 .
- ^ Длинный (1972 , стр. 85)
- ^ Pettofrezzo & Byrkit (1970 , стр. 72)
- ^ Длинный (1972 , стр.162)
- ^ Pettofrezzo & Byrkit (1970 , стр. 80)
- ^ См . Теорему Эйлера .
- ^ Л. Эйлер " Теорема arithmetica nova Methodo manifestrata " (Арифметическая теорема, доказываемая новым методом), Новые комментарии Академии наук Санкт-Петербурга, империалистический Петрополитан , 8 (1763), 74–104 . (Произведение было представлено в Петербургской Академии 15 октября 1759 г. Произведение с таким же названием было представлено в Берлинской Академии 8 июня 1758 г.). Доступно в Интернете в: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , том 1, в: Leonhardi Euleri Opera Omnia , серия 1, том 2 (Лейпциг, Германия, BG Teubner, 1915), страницы 531–555 . На странице 531 Эйлер определяет n как количество целых чисел, которые меньше N и относительно просты с N (… aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi,…), которая является функцией phi, φ ( N).
- ^ a b Сандифер, стр. 203
- ^ Graham et al. п. 133 примечание 111
- ^ Л. Эйлер, Спекуляции вокруг quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, т. 4, (1784), стр. 18–30, или Opera Omnia, Series 1, volume 4, pp. 105–115. (Произведение было представлено в Санкт-Петербургскую Академию 9 октября 1775 г.).
- ^ И φ ( n ), и ϕ ( n ) встречаются в литературе. Это две формы строчной греческой буквы фи .
- ↑ Gauss, Disquisitiones Arithmeticae, статья 38
- ^ Каджори, Флориан (1929). История математических обозначений Том II . Издательская компания «Открытый суд». §409.
- ^ JJ Sylvester (1879) «О некоторых уравнениях троичной кубической формы», American Journal of Mathematics , 2 : 357-393; Сильвестр вводит термин «totient» на странице 361 .
- ^ "totient". Оксфордский словарь английского языка (2-е изд.). Издательство Оксфордского университета . 1989 г.
- ^ Шрамм (2008)
- ↑ Gauss, DA, статья 39
- ↑ Gauss, DA art. 39, ст. 52-54
- ^ Graham et al. стр. 134-135
- ^ a b Харди и Райт 1979 , thm. 328
- ^ Динева (во внешних источниках), проп. 1
- ^ а б в Вальфиш, Арнольд (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie . Mathematische Forschungsberichte (на немецком языке). 16 . Берлин: VEB Deutscher Verlag der Wissenschaften . Zbl 0146.06003 .
- ^ Ломадсе, Г., "Научная работа Арнольда Вальфиса" (PDF) , Acta Arithmetica , 10 (3): 227–237
- ^ а б Ситарамачандрарао, Р. (1985). «О сроке ошибки Ландау II». Скалистые горы J. Math . 15 : 579–588.
- ^ Bordellès во внешних ссылках
- ^ Все формулы в разделе взяты из Schneider (во внешних ссылках)
- ^ Hardy & Wright 1979 , THM. 288
- ^ Hardy & Wright 1979 , THM. 309
- ↑ Харди и Райт, 1979 , введение к § 18.4.
- ^ Hardy & Wright 1979 , THM. 326
- ^ Hardy & Wright 1979 , THM. 327
- ^ Фактически теорема Чебышева ( Hardy & Wright 1979 , thm.7) и третья теорема Мертенса - это все, что нужно.
- ^ Hardy & Wright 1979 , THM. 436
- ^ Теорема 15 из Россер, Дж. Баркли; Шенфельд, Лоуэлл (1962). «Приближенные формулы для некоторых функций от простых чисел» . Иллинойс J. Math . 6 (1): 64–94.
- ^ Бах и Шаллит, thm. 8.8.7
- ^ а б Рибенбойм. Книга рекордов простых чисел . Раздел 4.IC[ требуется полная цитата ]
- ^ Шандор, Mitrinović & Crstici (2006) pp.24-25
- ^ Hardy & Wright 1979 , THM. 332
- ^ a b c Рибенбойм, стр.38
- ^ a b Sándor, Mitrinović & Crstici (2006) стр.16
- ^ a b Guy (2004) стр.144
- ^ Шандор & Crstici (2004) с.230
- ^ Чжан, Минчжи (1993). «О нетиентах». Журнал теории чисел . 43 (2): 168–172. DOI : 10,1006 / jnth.1993.1014 . ISSN 0022-314X . Zbl 0772.11001 .
- ^ а б в Форд, Кевин (1998). «Раздача тотиентов». Рамануджан Дж . 2 (1–2): 67–151. arXiv : 1104,3264 . DOI : 10.1007 / 978-1-4757-4507-8_8 . ISSN 1382-4090 . Zbl 0914.11053 .
- Перейти ↑ Sándor et al (2006) p.22
- ^ Sándor et al (2006) стр.21
- ^ a b Guy (2004) с.145
- ^ Шандор & Crstici (2004) p.229
- ^ Шандор & Crstici (2004) с.228
- Перейти ↑ Gauss, DA. 7-й § - это ст. 336–366
- ^ Гаусс доказал, что если n удовлетворяет определенным условиям, то n -угольник может быть построен. В 1837 году Пьер Ванцель доказал обратное: если n -угольник конструктивен, то n должно удовлетворять условиям Гаусса
- ^ Гаусс, Д.А., искусство 366
- ^ Гаусс, Д.А., искусство. 366. Этот список - последнее предложение в Disquisitiones.
- ^ Ribenboim, стр. 36-37.
- ^ Cohen, Graeme L .; Хагис, Питер младший (1980). «О количестве простых делителей числа n, если φ ( n ) делит n - 1 ». Nieuw Arch. Wiskd . III серия. 28 : 177–185. ISSN 0028-9825 . Zbl 0436.10002 .
- ^ Хагис, Питер младший (1988). «Об уравнении M · φ ( n ) = n - 1 ». Nieuw Arch. Wiskd . IV серия. 6 (3): 255–261. ISSN 0028-9825 . Zbl 0668.10006 .
- ^ Guy (2004) стр.142
Рекомендации
" Disquisitiones Arithmeticae" переведена с латыни на английский и немецкий языки. Немецкое издание включает все работы Гаусса по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.
Ссылки на Disquisitiones имеют форму Gauss, DA, art. nnn .
- Абрамовиц, М .; Стегун, И. А. (1964), Справочник по математическим функциям , Нью-Йорк: Dover Publications , ISBN 0-486-61272-4. См. Параграф 24.3.2.
- Бах, Эрик ; Шаллит, Джеффри (1996), теория алгоритмических чисел (том I: эффективные алгоритмы) , серия MIT Press по основам вычислений, Кембридж, Массачусетс: The MIT Press , ISBN 0-262-02405-5, Zbl 0873,11070
- Диксон, Леонард Юджин, «История теории чисел», том 1, глава 5 «Функция Эйлера, обобщения; ряд Фарея», Chelsea Publishing, 1952 г.
- Форд, Кевин (1999), "Количество решений ф ( х ) = т ", Анналы математики , 150 (1): 283-311, DOI : 10,2307 / 121103 , ISSN 0003-486X , JSTOR 121103 , МР 1715326 , Zbl 0978,11053.
- Гаусс, Карл Фридрих ; Кларк, Артур А. (переводчик на английский язык) (1986), Disquisitiones Arithmeticae (второе, исправленное издание) , Нью-Йорк: Springer , ISBN 0-387-96254-9
- Гаусс, Карл Фридрих ; Мазер, Х. (перевод на немецкий) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел) (второе издание) , Нью-Йорк: Челси, ISBN 0-8284-0191-8
- Грэм, Рональд ; Кнут, Дональд ; Паташник, Орен (1994), Конкретная математика : основа информатики (2-е изд.), Ридинг, Массачусетс: Аддисон-Уэсли, ISBN 0-201-55802-5, Zbl 0836,00001
- Гай, Ричард К. (2004), Нерешенные проблемы теории чисел , Проблемные книги по математике (3-е изд.), Нью-Йорк, Нью-Йорк: Springer-Verlag , ISBN 0-387-20860-7, Zbl 1058,11001
- Харди, GH ; Райт, EM (1979), Введение в теорию чисел (пятое изд.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
- Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Lexington: DC Heath and Company , LCCN 77-171950
- Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN 77-81766
- Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел (3-е изд.), Нью-Йорк: Springer , ISBN 0-387-94457-5, Zbl 0856,11001
- Сандифер, Чарльз (2007), Ранняя математика Леонарда Эйлера , MAA, ISBN 0-88385-559-3
- Шандор, Йожеф; Mitrinović, Dragoslav S .; Crstici, Борислав, ред. (2006), Справочник по теории чисел I , Дордрехт: Springer-Verlag , стр. 9–36, ISBN 1-4020-4215-9, Zbl 1151,11300
- Шандор, Йожеф; Crstici, Борислав (2004). Справочник по теории чисел II . Дордрехт: Kluwer Academic. стр. 179 -327. ISBN 1-4020-2546-7. Zbl 1079.11001 .
- Шрамм, Вольфганг (2008), "Преобразование Фурье функций наибольшего общего делителя" , Электронный журнал комбинаторной теории чисел , A50 (8 (1)).
Внешние ссылки
- "Totient function" , Энциклопедия математики , EMS Press , 2001 [1994]
- Фи-функция Эйлера и китайская теорема об остатках - доказательство мультипликативности φ ( n )
- Калькулятор функции Эйлера в JavaScript - до 20 цифр
- Динева, Розика, Тотиент Эйлера, Мёбиуса и функции делителя
- Плитадж, Лумис, Полхилл, подводя итоги функции Эйлера-Фи