Гипотеза Кармайклса о функции тотиент-функции - Википедия - Carmichaels totient function conjecture
В математике Гипотеза кармайкла о функции тотализатора касается множественность ценностей Функция Эйлера φ(п), который считает количество целых чисел меньше и совмещать к п. В нем говорится, что для каждого п есть хотя бы одно целое число м ≠ п такой, что φ(м) = φ(п).Роберт Кармайкл впервые заявил об этом догадка в 1907 году, но как теорема а не как предположение. Однако его доказательство было ошибочным, и в 1922 году он отказался от своего утверждения и сформулировал гипотезу как открытая проблема.
Примеры
Тотальная функция φ(п) равно 2, когда п - одно из трех значений 3, 4 и 6. Таким образом, если мы возьмем любое из этих трех значений как п, то любое из двух других значений можно использовать в качестве м для которого φ(м) = φ(п).
Точно так же totient равно 4, когда п - одно из четырех значений 5, 8, 10 и 12, и оно равно 6, когда п - одно из четырех значений 7, 9, 14 и 18. В каждом случае существует более одного значения п имеющий такую же ценность φ(п).
Гипотеза утверждает, что это явление повторяющихся значений справедливо для любогоп.
| k | числа п такой, что φ(п) = k (последовательность A032447 в OEIS ) | количество таких пs (последовательность A014197 в OEIS ) |
| 1 | 1, 2 | 2 |
| 2 | 3, 4, 6 | 3 |
| 4 | 5, 8, 10, 12 | 4 |
| 6 | 7, 9, 14, 18 | 4 |
| 8 | 15, 16, 20, 24, 30 | 5 |
| 10 | 11, 22 | 2 |
| 12 | 13, 21, 26, 28, 36, 42 | 6 |
| 16 | 17, 32, 34, 40, 48, 60 | 6 |
| 18 | 19, 27, 38, 54 | 4 |
| 20 | 25, 33, 44, 50, 66 | 5 |
| 22 | 23, 46 | 2 |
| 24 | 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 | 10 |
| 28 | 29, 58 | 2 |
| 30 | 31, 62 | 2 |
| 32 | 51, 64, 68, 80, 96, 102, 120 | 7 |
| 36 | 37, 57, 63, 74, 76, 108, 114, 126 | 8 |
| 40 | 41, 55, 75, 82, 88, 100, 110, 132, 150 | 9 |
| 42 | 43, 49, 86, 98 | 4 |
| 44 | 69, 92, 138 | 3 |
| 46 | 47, 94 | 2 |
| 48 | 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 | 11 |
| 52 | 53, 106 | 2 |
| 54 | 81, 162 | 2 |
| 56 | 87, 116, 174 | 3 |
| 58 | 59, 118 | 2 |
| 60 | 61, 77, 93, 99, 122, 124, 154, 186, 198 | 9 |
| 64 | 85, 128, 136, 160, 170, 192, 204, 240 | 8 |
| 66 | 67, 134 | 2 |
| 70 | 71, 142 | 2 |
| 72 | 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270 | 17 |
Нижние границы
Есть очень высокие нижняя граница гипотезы Кармайкла, которые относительно легко определить. Сам Кармайкл доказал, что любой контрпример к его гипотезе (то есть ценность п такое, что φ (п) отличается от тотиентов всех других чисел) должно быть не менее 1037, и Виктор Клее расширил этот результат до 10400. Нижняя граница было дано Шлафли и Вагоном, а нижняя граница был определен Кевин Форд в 1998 г.[1]
Вычислительная техника, лежащая в основе этих нижних оценок, зависит от некоторых ключевых результатов Кли, которые позволяют показать, что наименьший контрпример должен делиться на квадраты простых чисел, делящих его общее значение. Результаты Кли подразумевают, что 8 и простые числа Ферма (простые числа формы 2k + 1) за исключением 3 не делим наименьший контрпример. Следовательно, доказательство гипотезы эквивалентно доказательству того, что гипотеза верна для всех целых чисел, конгруэнтных 4 (mod 8).
Другие результаты
Форд также доказал, что если существует контрпример к гипотезе, то положительная пропорция (в смысле асимптотической плотности) целых чисел также является контрпримером.[1]
Хотя эта гипотеза широко распространена, Карл Померанс дал достаточное условие для целого числа п быть контрпримером к гипотезе (Померанс 1974 ). Согласно этому условию, п является контрпримером, если для каждого простого числа п такой, что п - 1 делит φ(п), п2 разделяетп. Однако Померанс показал, что существование такого целого числа маловероятно. По сути, можно показать, что если первый k простые числа п конгруэнтно 1 (modq) (куда q простое число) все меньше, чем qk+1, то такое целое число будет делиться на все простые числа и, следовательно, не может существовать. В любом случае доказательство того, что контрпример Померанса не существует, далеко от доказательства гипотезы Кармайкла. Однако, если он существует, то существует бесконечно много контрпримеров, как утверждает Форд.
Другой способ сформулировать гипотезу Кармайкла: еслиА(ж) обозначает количество натуральных чисел п для которого φ(п) = ж, тогда А(ж) никогда не может равняться 1. Соответственно, Вацлав Серпинский предположил, что каждое положительное целое число, кроме 1, встречается как значение A (ж), гипотеза, которая была доказана в 1999 году Кевином Фордом.[2]
Примечания
Рекомендации
- Кармайкл, Р. Д. (1907), "Об Эйлере φ-функция », Бюллетень Американского математического общества, 13 (5): 241–243, Дои:10.1090 / S0002-9904-1907-01453-2, МИСТЕР 1558451.
- Кармайкл, Р. Д. (1922), "Заметка о книге Эйлера. φ-функция », Бюллетень Американского математического общества, 28 (3): 109–110, Дои:10.1090 / S0002-9904-1922-03504-5, МИСТЕР 1560520.
- Форд, К. (1999), "Количество решений φ(Икс) = м", Анналы математики, 150 (1): 283–311, Дои:10.2307/121103, JSTOR 121103, МИСТЕР 1715326, Zbl 0978.11053.
- Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag, B39, ISBN 978-0-387-20860-2, Zbl 1058.11001.
- Клее, В. Л., мл. (1947), «О догадке Кармайкла», Бюллетень Американского математического общества, 53 (12): 1183–1186, Дои:10.1090 / S0002-9904-1947-08940-0, МИСТЕР 0022855, Zbl 0035.02601.
- Померанс, Карл (1974), "По догадке Кармайкла" (PDF), Труды Американского математического общества, 43 (2): 297–298, Дои:10.2307/2038881, JSTOR 2038881, Zbl 0254.10009.
- Шандор, Йожеф; Crstici, Борислав (2004), Справочник по теории чисел II, Dordrecht: Kluwer Academic, стр. 228–229, ISBN 978-1-4020-2546-4, Zbl 1079.11001.
- Schlafly, A .; Вагон, С. (1994), "Гипотеза Кармайкла о функции Эйлера верна ниже 1010,000,000", Математика вычислений, 63 (207): 415–419, Дои:10.2307/2153585, JSTOR 2153585, МИСТЕР 1226815, Zbl 0801.11001.