В теории чисел , теорема Кармайкла , названную в честь американского математика R.D. Carmichael , утверждают , что для любой невырожденной последовательности Лукаса первого рода U п ( P , Q ) с относительно простых параметров P, Q и положительного дискриминанта, элемент U п с n ≠ 1, 2, 6 имеет хотя бы один простой делитель, который не делит ни один из предыдущих, кроме 12-го числа Фибоначчи F (12) = U 12 (1, -1) = 144 и его эквивалента U 12(-1, -1) = - 144.
В частности, для n больше 12 n- е число Фибоначчи F ( n ) имеет по крайней мере один простой делитель, который не делит любое предыдущее число Фибоначчи.
Кармайкл (1913, теорема 21) доказал эту теорему. Недавно Ябута (2001) [1] дал простое доказательство.
Заявление
Даны два взаимно простых целых числа P и Q , таких чтои PQ ≠ 0 , пусть U n ( P , Q ) - последовательность Люка первого рода, определенная формулой
Тогда при n 1, 2, 6 U n ( P , Q ) имеет хотя бы один простой делитель, который не делит никакой U m ( P , Q ) с m < n , за исключением U 12 (1, -1) = F (12) = 144, U 12 (-1, -1) = - F (12) = - 144. Такое простое число p называется характеристическим множителем или примитивным простым делителем числа U n ( P , Q ). В самом деле, Кармайкл показал немного более сильную теорему: для n ≠ 1, 2, 6 U n ( P , Q ) имеет хотя бы один примитивный простой делитель, не делящий D [2], за исключением U 3 (1, -2) = U 3. (-1, -2) = 3, U 5 (1, -1) = U 5 (-1, -1) = F (5) = 5, U 12 (1, -1) = F (12) = 144, U 12 (-1, -1) = - F (12) = - 144.
Обратите внимание, что D должно быть> 0, поэтому случаи U 13 (1, 2), U 18 (1, 2) и U 30 (1, 2) и т. Д. Не включаются, так как в этом случае D = −7 < 0.
Случаи Фибоначчи и Пелла
Единственные исключения в случае Фибоначчи для n до 12:
- F (1) = 1 и F (2) = 1, у которых нет простых делителей
- F (6) = 8, единственный простой делитель которого равен 2 (что является F (3))
- F (12) = 144, чьи единственные простые делители равны 2 (F (3)) и 3 (F (4))
Наименьшие примитивные простые делители числа F ( n ) равны
- 1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, ... (последовательность A001578 в OEIS )
Теорема Кармайкла гласит, что каждое число Фибоначчи, за исключением перечисленных выше исключений, имеет по крайней мере один примитивный простой делитель.
Если n > 1, то n- е число Пелла имеет по крайней мере один простой делитель, который не делит любое предыдущее число Пелла. Наименьший примитивный простой делитель n- го числа Пелля равен
Смотрите также
Рекомендации
- ^ Yabuta, M (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Ежеквартальный отчет Фибоначчи . 39 : 439–443 . Проверено 4 октября 2018 года .
- ^ В определении примитивного простого делителя p часто требуется, чтобы p не делило дискриминант.
- Кармайкл, РД (1913), "О численных факторов арифметических форм & alpha ; п ± & beta ; п ", Анналы математики , 15 (1/4): 30-70, DOI : 10,2307 / 1967797 , JSTOR 1967797.