В математике гипотеза тотизирующей функции Кармайкла касается множественности значений тотической функции Эйлера φ ( n ), которая подсчитывает количество целых чисел, меньших чем и взаимно простых с n . Он утверждает, что для каждого n существует хотя бы одно целое число m ≠ n такое, что φ ( m ) = φ ( n ). Роберт Кармайкл впервые высказал эту гипотезу в 1907 году, но как теоремаа не как предположение. Однако его доказательство было ошибочным, и в 1922 году он отказался от своего утверждения и объявил гипотезу открытой проблемой .
Примеры
Общая функция φ ( n ) равна 2, когда n является одним из трех значений 3, 4 и 6. Таким образом, если мы возьмем любое из этих трех значений в качестве n , то можно будет использовать любое из двух других значений. как m, для которого φ ( m ) = φ ( n ).
Точно так же totient равно 4, когда n является одним из четырех значений 5, 8, 10 и 12, и равно 6, когда n является одним из четырех значений 7, 9, 14 и 18. В каждом из них В этом случае существует несколько значений n, имеющих одинаковое значение φ ( n ).
Гипотеза утверждает, что это явление повторяющихся значений справедливо для любого n .
k | числа n такие, что φ ( n ) = k (последовательность A032447 в OEIS ) | количество таких n 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 |
Нижние оценки
У гипотезы Кармайкла очень высокие нижние оценки , которые относительно легко определить. Сам Кармайкл доказал, что любой контрпример к его гипотезе (то есть такое значение n , что φ ( n ) отличается от всех остальных чисел) должен быть не менее 10 37 , и Виктор Клее расширил этот результат до 10 400 . Нижняя границабыло дано Шлафли и Вагоном, а нижняя граница был определен Кевином Фордом в 1998 году. [1]
Вычислительная техника, лежащая в основе этих нижних оценок, зависит от некоторых ключевых результатов Кли, которые позволяют показать, что наименьший контрпример должен делиться на квадраты простых чисел, делящих его общее значение. Результаты Кли подразумевают, что 8 и простые числа Ферма (простые числа формы 2 k + 1), исключая 3, не делят наименьший контрпример. Следовательно, доказательство гипотезы эквивалентно доказательству того, что гипотеза верна для всех целых чисел, конгруэнтных 4 (mod 8).
Другие результаты
Форд также доказал, что если существует контрпример к гипотезе, то положительная пропорция (в смысле асимптотической плотности) целых чисел также является контрпримером. [1]
Хотя эта гипотеза широко распространена, Карл Померанс дал достаточное условие для того, чтобы целое число n было контрпримером к гипотезе ( Pomerance 1974 ). Согласно этому условию n является контрпримером, если для любого простого числа p, такого что p - 1 делит φ ( n ), p 2 делит n . Однако Померанс показал, что существование такого целого числа крайне маловероятно. По сути, можно показать, что если все первые k простых чисел p, конгруэнтных 1 (mod q ) (где q - простое число), меньше q k +1 , то такое целое число будет делиться на каждое простое число и, следовательно, не может существовать. В любом случае доказательство того, что контрпример Померанса не существует, далеко от доказательства гипотезы Кармайкла. Однако, если он существует, то существует бесконечно много контрпримеров, как утверждает Форд.
Другой способ сформулировать гипотезу Кармайкла: если A ( f ) обозначает количество натуральных чисел n, для которых φ ( n ) = f , то A ( f ) никогда не может равняться 1. Соответственно, Вацлав Серпинский предположил, что каждое положительное целое число другое чем 1 встречается как значение A ( f ), гипотеза, которая была доказана в 1999 году Кевином Фордом. [2]
Заметки
Рекомендации
- Carmichael, RD (1907), "О Эйлера ф -функции", Бюллетень Американского математического общества , 13 (5): 241-243, DOI : 10,1090 / S0002-9904-1907-01453-2 , MR 1558451.
- Carmichael, RD (1922), "Замечание о Эйлера ф -функции", Бюллетень Американского математического общества , 28 (3): 109-110, DOI : 10.1090 / S0002-9904-1922-03504-5 , MR 1560520.
- Форд, К. (1999), "Количество решений ф ( х ) = т ", Анналы математики , 150 (1): 283-311, DOI : 10,2307 / 121103 , JSTOR 121103 , MR 1715326 , ZBL 0978.11053.
- Гай, Ричард К. (2004), Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag , B39, ISBN 978-0-387-20860-2, Zbl 1058,11001.
- Кли, VL-младший (1947), "Об одной гипотезе Кармайкл", Бюллетень Американского математического общества , 53 (12): 1183-1186, DOI : 10,1090 / S0002-9904-1947-08940-0 , MR 0022855 , Zbl 0035,02601.
- Pomerance, Карл (1974), "О гипотезе Кармайкла" (PDF) , Труды Американского математического общества , 43 (2): 297-298, DOI : 10,2307 / 2038881 , JSTOR 2038881 , Zbl 0254,10009.
- Шандор, Йожеф; Crstici, Borislav (2004), Справочник по теории чисел II , Dordrecht: Kluwer Academic, стр. 228–229, ISBN 978-1-4020-2546-4, Zbl 1079,11001.
- Schlafly, A .; Вагон, S. (1994), "гипотеза Кармайкла на функции Эйлера справедлива ниже 10 10000000 ", Математика вычислений , 63 (207): 415-419, DOI : 10,2307 / 2153585 , JSTOR 2153585 , MR 1226815 , Zbl 0801,11001.
Внешние ссылки
- Вайсштейн, Эрик У. "Гипотеза Тотентиентной функции Кармайкла" . MathWorld .