Teoria liczb to jedna z najstarszych i najbardziej fundamentalnych dziedzin matematyki, która zajmuje się badaniem własności liczb, szczególnie liczb całkowitych. Jest to dziedzina o dużym znaczeniu teoretycznym, ale ma też praktyczne zastosowania w kryptografii, informatyce, fizyce i innych obszarach.

Podstawowe zagadnienia teorii liczb:

Podstawowe pojęcia:
- Liczby naturalne (\mathbb{N}) – liczby całkowite dodatnie: 1, 2, 3, ...
- Liczby całkowite (\mathbb{Z}) – liczby naturalne, ich przeciwności i zero: ..., -2, -1, 0, 1, 2, ...
- Liczby pierwsze – liczby naturalne większe od 1, które mają dokładnie dwa dzielniki: 1 i siebie samą (np. 2, 3, 5, 7, 11).
Podzielność:
- Dzielnik – liczba d jest dzielnikiem liczby n, jeśli istnieje liczba całkowita k, taka że n=d \cdot k.
- Największy wspólny dzielnik (NWD) – największa liczba, która dzieli dwie liczby bez reszty.
- Algorytm Euklidesa – metoda znajdowania NWD dwóch liczb.
Kongruencje:
- Kongruencja – mówimy, że a\equiv b\ (\text{mod }m), jeśli m dzieli różnicę a-b.
- Chińskie twierdzenie o resztach – pozwala rozwiązywać układy kongruencji.
Liczby pierwsze i ich własności:
- Rozkład na czynniki pierwsze – każda liczba naturalna większa od 1 może być jednoznacznie przedstawiona jako iloczyn liczb pierwszych.
- Twierdzenie o liczbach pierwszych – opisuje asymptotyczny rozkład liczb pierwszych.

Zadanie

Rozwiązanie

O zadaniu