Podzielność, liczby pierwsze i reszty z dzielenia to rdzeń teorii liczb. Rozwiązujesz tu także zadania o ostatnich cyfrach potęg, NWD i NWW, równania w liczbach całkowitych, a przy wyższych poziomach kongruencje i funkcję Eulera.
Jak rozpoznać właściwe narzędzie
Pytanie o ostatnią cyfrę lub resztę z dużej potęgi oznacza szukanie cyklu. Liczba dzielników oraz NWD czy NWW wymagają rozkładu na czynniki pierwsze. Wyrażenie „dla każdego \(n\)” w połączeniu z podzielnością zapowiada rozumowanie ogólne, często przez rozkład na czynniki albo sprawdzenie reszt. Równanie, w którym szukasz liczb całkowitych, zwykle sprowadza się do iloczynu równego stałej lub do reszty, która wyklucza rozwiązania.
Techniki z krótkimi obliczeniami
- kongruencje: \(7 \equiv 2 \pmod 5\) oraz \(2^4 \equiv 1 \pmod 5\), więc \(7^{100} \equiv 1 \pmod 5\)
- ostatnia cyfra: potęgi trójki kończą się cyklicznie na 3, 9, 7, 1, zatem \(3^{10}\) kończy się na 9
- algorytm Euklidesa: \(84 = 2 \cdot 36 + 12\) i \(36 = 3 \cdot 12\), więc \(\operatorname{NWD}(84, 36) = 12\)
- liczba dzielników: \(360 = 2^3 \cdot 3^2 \cdot 5\) ma \(4 \cdot 3 \cdot 2 = 24\) dzielniki
- zera na końcu silni: \(100!\) kończy się \(\lfloor \frac{100}{5} \rfloor + \lfloor \frac{100}{25} \rfloor = 24\) zerami
O czym łatwo zapomnieć
Jedynka nie jest liczbą pierwszą, a dwójka jest jedyną parzystą, co często zamyka rozwiązanie. Kongruencji nie wolno dzielić stronami bez sprawdzenia NWD dzielnika i modułu. Liczby, które spełniają warunek dla kilku małych \(n\), niczego nie dowodzą, bo wzorzec może się załamać. Przy reszcie modulo 4 i 3 warto pamiętać, że kwadrat daje tylko reszty 0 lub 1. Przy równaniach sprawdzaj też dzielniki ujemne, jeśli zadanie mówi o liczbach całkowitych.
Kolejność zadań z teorii liczb
Łatwe to cechy podzielności i proste NWD. Średnie, zgodne z egzaminem ósmoklasisty i maturą, dotyczą reszt i ostatnich cyfr, a także dzielników i NWD. Trudne, na miarę pierwszego etapu Olimpiady Matematycznej, wymagają swobodnego korzystania z kongruencji. Wyzwanie to olimpijskie równania i funkcje arytmetyczne, które warto zaczynać od sprawdzenia małych przypadków.
Podstawy zebrano w lekcji cechy podzielności, liczby pierwsze, NWD i NWW, a rachunek na resztach w lekcji kongruencje i małe twierdzenie Fermata.