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....