Prvočísla

Definice. Nechť

p \in ℕ, p \geq 2

p

je prvočíslo, je-li dělitelné pouze

1

a sebou samým.

Věta.

\forall p \in ℕ, p \geq 2 : p \in ℙ ⟺ (\forall a, b \in ℕ : p | a b ⟹ p | a \lor p | b

Důkaz.

$(\Rightarrow)$ $p | a b ⟹ {\begin{matrix} \gcd (p, a) > 1 ⟹ p | a \\ \gcd (p, b) = 1 ⟹ p | b \end{matrix}$

$(\Leftarrow)$ $p = d_{1} d_{2}, 1 < d_{1}, d_{2} < p ⟹ p | d_{1} d_{2} \land \neg (p | d_{1} \lor p | d_{2}) ⟹ SPOR s (\Rightarrow)$

Věta (základní věta aritmetiky). Nechť

n \in ℕ^{+}

. Pak existuje právě jeden (až na pořadí) rozklad

n

na součin prvočísel.

Důkaz.

Existence: $n = 1 \lor n \in ℙ \lor n = a b, 2 \leq a, b < n$

Jednoznačnost: Vezměme nejmenší $n$ , pro které věta neplatí, tedy $n = \prod_{i} p_{i} = \prod_{i} q_{i}$ . $p_{1} | \prod_{i} q_{i} ⟹ \exists i : p_{1} | q_{i} ⟹ p_{1} = q_{i}$ . Potom však věta neplatí také pro $n \div p_{1}$ , což je spor s minimalitou $n$ .

Věta. Nechť

n = \prod_{i} p_{i}^{k_{i}}

. Pak počet dělitelů

n

(

τ (n)

) je

\prod_{i} (k_{i} + 1)

Důkaz.

d = \prod_{i} p_{i} j_{i} | n ⟺ \forall i : j_{i} \leq k_{i}

. Tedy počet možností, jak zvolit každé

j_{i}

, je

k_{i} + 1

Věta. Nechť

a = \prod_{i} p_{i}^{k_{i}}, b = \prod_{i} p_{i}^{l_{i}}

. Pak

\gcd (a, b) = \prod_{i} p_{i}^{\min (k_{i}, l_{i})}

Věta. Prvočísel existuje nekonečně mnoho.

Důkaz (Euklidův; první důkaz sporem v historii matematiky). Předpokládejme, že existuje konečně mnoho prvočísel

p_{i}

. Nechť

n = (\prod_{i} p_{i}) + 1

n

nemůže být dělitelné žádným prvočíslem, tudíž jde o prvočíslo, což je spor.

Věta. Pro každé

n \in ℕ

existuje

n

po sobě jdoucích složených čísel.

Důkaz. Vezměme čísla od

(n + 1)! + 2

(n + 1)! + n + 1

; každé musí být složené.