Теорема Кармайкла

О простых делителях в последовательностях Фибоначчи и Люка

В теории чисел теорема Кармайкла , названная в честь американского математика Р. Д. Кармайкла , утверждает, что для любой невырожденной последовательности Люка первого рода U _n ( P , Q ) с взаимно простыми параметрами P , Q и положительным дискриминантом элемент U _n с n ≠ 1, 2, 6 имеет по крайней мере один простой делитель, который не делит ни один более ранний, кроме 12-го числа Фибоначчи F(12) = U ₁₂ (1, −1) = 144 и его эквивалента U ₁₂ (−1, −1) = −144.

В частности, для n больше 12 n -е число Фибоначчи F( n ) имеет по крайней мере один простой делитель, который не делит ни одно более раннее число Фибоначчи.

Кармайкл (1913, теорема 21) доказал эту теорему . Недавно Ябута (2001) ^[1] дал простое доказательство. Билу, Ханрот, Вотье и Миньотт (2001) ^[2] распространили ее на случай отрицательных дискриминантов (где она верна для всех n > 30).

Заявление

Даны два взаимно простых целых числа P и Q , такие, что и $PQ$ $\neq 0$ , пусть $U$ $n$ $($ $P$ $,$ $Q$ $)$ — последовательность Люка первого рода, определяемая формулой $D=P^{2}-4Q>0$

{\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q)\qquad {\mbox{ для }}n>1.\end{aligned}}

Тогда для n ≠ 1, 2, 6 число U _n ( P , Q ) имеет по крайней мере один простой делитель, который не делит ни одно число U _m ( P , Q ) с m < n , за исключением U ₁₂ (±1, −1) = ±F(12) = ±144. Такое простое число p называется характеристическим множителем или примитивным простым делителем числа U _n ( P , Q ). Действительно, Кармайкл показал немного более сильную теорему: для n ≠ 1, 2, 6, U _n ( P , Q ) имеет по крайней мере один примитивный простой делитель, не делящий D ^[3], за исключением U ₃ (±1, −2) = 3, U ₅ (±1, −1) = F(5) = 5 или U ₁₂ (1, −1) = − U ₁₂ (−1, −1) = F(12) = 144.

В теореме Камишареля D должно быть больше 0; таким образом, случаи U ₁₃ (1, 2), U ₁₈ (1, 2) и U ₃₀ (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- го числа Пелля являются

1, 2, 5, 3, 29, 7, 13, 17, 197, 41, 5741, 11, 33461, 239, 269, 577, 137, 199, 37, 19, 45697, 23, 229, 1153, 1549, 79, 53, 113, 44560482149, 31, 61, 665857, 52734529, 103, 1800193921, 73, 593, 9369319, 389, 241, ... (последовательность A246556 в OEIS )

Смотрите также

Теорема Зигмонди

Ссылки

^ Ябута, Минору (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Fibonacci Quarterly . 39 (5): 439– 443. doi :10.1080/00150517.2001.12428701 . Получено 4 октября 2018 г. .
^ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "Существование примитивных делителей чисел Люка и Лемера" (PDF) . J. Reine Angew. Math. 2001 (539): 75– 122. doi :10.1515/crll.2001.080. MR 1863855. S2CID 122969549. В этой статье описываются последовательности в терминах P и D (которые она называет a и b ); Q = ( P ² − D)/4, поэтому, когда в статье говорится о последовательности с ( a , b ) = (1, −7), это означает P = 1, Q = 2. Полный список чисел Люка без примитивного простого делителя — n = 1, 23 особых случая, перечисленных в Таблице 1, и общие случаи, перечисленные в Таблице 3. (Таблицы 2 и 4 применяются к связанной последовательности Лемера .)
^ При определении примитивного простого делителя p часто требуется, чтобы p не делил дискриминант.

Кармайкл, РД (1913), «О числовых множителях арифметических форм α ⁿ ±β ⁿ », Annals of Mathematics , 15 (1/4): 30–70 , doi :10.2307/1967797, JSTOR 1967797.

[1] Ябута, Минору (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Fibonacci Quarterly . 39 (5): 439– 443. doi :10.1080/00150517.2001.12428701 . Получено 4 октября 2018 г. .

[2] Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "Существование примитивных делителей чисел Люка и Лемера" (PDF) . J. Reine Angew. Math. 2001 (539): 75– 122. doi :10.1515/crll.2001.080. MR 1863855. S2CID 122969549. В этой статье описываются последовательности в терминах P и D (которые она называет a и b ); Q = ( P ² − D)/4, поэтому, когда в статье говорится о последовательности с ( a , b ) = (1, −7), это означает P = 1, Q = 2. Полный список чисел Люка без примитивного простого делителя — n = 1, 23 особых случая, перечисленных в Таблице 1, и общие случаи, перечисленные в Таблице 3. (Таблицы 2 и 4 применяются к связанной последовательности Лемера .)

[3] При определении примитивного простого делителя p часто требуется, чтобы p не делил дискриминант.