liczba Carmichaela

[gelo21]

Pokazać, że \(\displaystyle{ 2821}\) jest liczbą Carmichaela.

[Afish]

"Oto algorytm podany przez J.Chernicka[7] dla liczb Carmichaela o trzech czynnikach pierwszych:

podstawiając kolejne liczby naturalne za \(\displaystyle{ m}\) wyznaczamy \(\displaystyle{ M(m) = (6m + 1)(12m + 1)(18m + 1)}\). Jeżeli dla pewnego \(\displaystyle{ m}\) wszystkie czynniki w nawiasach są liczbami pierwszymi, to \(\displaystyle{ M(m)}\) jest liczbą Carmichaela."
Wikipedia

[mol_ksiazkowy]

podstawiając kolejne liczby naturalne za m wyznaczamy \(\displaystyle{ M(m) = (6m + 1)(12m + 1)(18m + 1)}\). Jeżeli dla pewnego m wszystkie czynniki w nawiasach są liczbami pierwszymi, to M(m) jest liczbą Carmichaela

*
Zadanie ze 101.... inny dowód

Ukryta treść:    

Liczba Carmichaela to taka liczba złożona \(\displaystyle{ n}\), że jeśli \(\displaystyle{ a}\) jest liczbą całkowitą względnie pierwsza z \(\displaystyle{ n}\) i \(\displaystyle{ 1< a < n}\) to \(\displaystyle{ a^{n-1} \equiv 1 \ (mod \ n)}\)
; np. \(\displaystyle{ n=15}\) nie jest l. Carmichaela gdyż np. \(\displaystyle{ 2^{14} \equiv 4 \ (mod \ 15)}\)
(najmniejsza liczba Carmichaela jest \(\displaystyle{ 561 = 3 \cdot 11 \cdot 17}\))

prawdopodobnie chodzi i dowód lematu:
Niech \(\displaystyle{ n}\) będzie liczbą bezkwadratową , złożoną i nieparzystą. Wtedy jeśli dla dowolnego dzielnika pierwszego \(\displaystyle{ p}\) liczby \(\displaystyle{ n}\), \(\displaystyle{ p-1}\) dzieli \(\displaystyle{ n-1}\) to \(\displaystyle{ n}\) jest liczbą Carmichaela

Dowód: Niech \(\displaystyle{ a}\) bedzie jw. tj. w definicji liczby Carmichaela i niech \(\displaystyle{ p}\) to dzielnik pierwszy liczby \(\displaystyle{ n}\). A wiec \(\displaystyle{ a}\) i \(\displaystyle{ p}\) są względnie pierwsze i: \(\displaystyle{ a^{p-1} \equiv 1 \ (mod \ p)}\) czyli
\(\displaystyle{ a^{n-1} = a^{p-1}^{\frac{n-1}{p-1}} \equiv 1^{\frac{n-1}{p-1}} \equiv 1 \ (mod \ p)}\)

A zatem liczba \(\displaystyle{ a^{n-1} - 1}\) jest podzielna przez \(\displaystyle{ n}\) bo \(\displaystyle{ n}\) jest liczbą bezkwadratową.

\(\displaystyle{ 2821 = 7 \cdot 13 \cdot 31}\) spełnia założenia tego lematu, tj. jest liczbą Carmichaela
Uwagi: Mozna udowodnić tez Twierdzenie odwrotne (do lematu)

* Analogicznie dla \(\displaystyle{ k \geq 4}\) i \(\displaystyle{ m \geq 1}\) niech
\(\displaystyle{ M_k(m) = (6m+1)(12m+1) \prod_{i=1}^{k-2} (9 \cdot 2^i m+ 1)}\)
Jesli dla pewnego \(\displaystyle{ m}\) wszystkie czynniki w nawiasach (jest ich k) są liczbami pierwszymi , a ponadto \(\displaystyle{ 2^{k-4}}\) dzieli \(\displaystyle{ m}\), to \(\displaystyle{ M_{k} (m)}\) jest liczba Carmichaela o \(\displaystyle{ k}\) czynnikach pierwszych.

Zródło: P . Ribenboim - Mała księga wielkich....