Prvočíselné testy

Věta (prvočíselná).

\lim_{n \to \infty} \frac{π (n)}{\frac{n}{\ln (n)}} = 1

Předpoklad: zkoumáme pouze lichá čísla vyšší než $1$

Fermatův test prvočíselnosti

Věta.

(\forall n \in ℕ) (n \in ℙ ⟺ (\forall a \in \hat{n - 1}) (a^{n - 1} \equiv 1 m o d n))

Důkaz.

$(\Rightarrow)$ Přímo vyplývá z malé Fermatovy věty.

$(\Leftarrow)$ Předpokládejme pro spor, že platí pravá strana implikace a $n = c \cdot d; c, d \geq 2$ . Poté $c^{n - 1} \equiv 1 m o d n$ , tedy $(\exists k \in ℤ) (1 = c^{n - 1} + k \cdot n = c^{n - 1} + k \cdot c \cdot d)$ . Z toho plyne $c | 1$ , což je spor.

Definice. Nechť

n

je složené číslo a

a \in \hat{n - 1}

. Poté

$a$ je svědek složenosti, pokud $a^{n - 1} \equiv̸ 1 m o d n$ .
$a$ je lhář, pokud $a^{n - 1} \equiv 1 m o d n$ . Také je říká, že $n$ je pseudoprvočíslo vůči základu $a$ .

Věta. Nechť

n

je liché složené číslo. Potom

$1$ a $n - 1$ jsou lháři
každé číslo soudělné s $n$ je svědek složenosti

Definice. Složené

n

se nazývá Carmichaelovo číslo, pokud

(\forall a \in \hat{n - 1}) (a ⟂ n ⟹ a^{n - 1} \equiv 1 m o d n)

Nejmenší Carmichaelovo číslo je $561$ .
Pro každé $k \in ℕ$ je $(6 k + 1) (12 k + 1) (18 k + 1)$ Carmichaelovo číslo, pokud všichni tři činitelé jsou prvočísla.
Existuje nekonečně mnoho Carmichaelových čísel.

Věta (Fermatův test prvočíselnosti). Nechť

n \in ℕ, n > 1,2 ∤ n

n

není Carmichaelovo číslo. Zvolíme náhodně

N

čísel

a_{i}

\hat{n - 1}

, potom

$(\exists a_{i}) (a_{i}^{n - 1} \equiv̸ 1 m o d n) ⟹ n \notin ℙ$
$(\forall a_{i}) (a_{i}^{n - 1} \equiv 1 m o d n) ⟹ n \in ℙ s p r a v d \overset{ˇ}{e} p o d o b n o s t \overset{ˊ}{ı} \geq 1 - 2^{- N}$