Teoria liczb — liczby pierwsze, podzielność i arytmetyka modularna

Teoria liczb to dział matematyki zajmujący się liczbami całkowitymi. Jeśli chcesz zrozumieć liczby pierwsze, podzielność albo arytmetykę modularną, patrzysz właśnie na podstawowe idee teorii liczb.

Liczba pierwsza to liczba całkowita większa od $1$, która ma dokładnie dwa dodatnie dzielniki: $1$ i samą siebie. Podzielność pyta, czy jedna liczba całkowita dzieli drugą bez reszty. Arytmetyka modularna śledzi reszty z dzielenia, dlatego często nazywa się ją arytmetyką zegarową.

Co obejmuje teoria liczb

Te trzy idee łączą się ze sobą:

• Liczby pierwsze są podstawowymi cegiełkami dodatnich liczb całkowitych.
• Podzielność mówi, kiedy jedna liczba całkowita dzieli drugą dokładnie.
• Arytmetyka modularna przepisuje pytania o podzielność na pytania o reszty.

Na przykład stwierdzenie „$a$ jest podzielne przez $n$” oznacza to samo co

$$a \equiv 0 \pmod n$$

Dlatego pytanie o podzielność często można zapisać jako pytanie o resztę.

Liczby pierwsze: podstawowe cegiełki

Liczby pierwsze zaczynają się tak:

$$2, 3, 5, 7, 11, 13, \dots$$

Liczba $2$ jest jedyną parzystą liczbą pierwszą. Każda inna liczba parzysta jest podzielna przez $2$, więc nie może być pierwsza.

Jeśli dodatnia liczba całkowita większa od $1$ nie jest pierwsza, nazywa się ją liczbą złożoną. Na przykład $21$ jest liczbą złożoną, ponieważ

$$21 = 3 \cdot 7$$

Liczby pierwsze są ważne, ponieważ każdą liczbę całkowitą większą od $1$ można zapisać jako iloczyn liczb pierwszych, z dokładnością do kolejności czynników. Na tym opiera się rozkład na czynniki pierwsze.

Podzielność: kiedy jedna liczba dzieli drugą dokładnie

Jeśli $a$ i $b$ są liczbami całkowitymi oraz $b \ne 0$, to „$b$ dzieli $a$” oznacza, że istnieje liczba całkowita $k$ taka, że

$$a = bk$$

Zapisujemy to jako

$$b \mid a$$

Na przykład $4 \mid 20$, ponieważ $20 = 4 \cdot 5$. Ale $4 \nmid 22$, ponieważ przy dzieleniu $22$ przez $4$ zostaje reszta.

Podzielność to język, który stoi za dzielnikami, wielokrotnościami, największym wspólnym dzielnikiem i najmniejszą wspólną wielokrotnością. Wyjaśnia też znane testy:

• Liczba jest podzielna przez $2$, jeśli jej ostatnia cyfra jest parzysta.
• Liczba jest podzielna przez $5$, jeśli jej ostatnia cyfra to $0$ lub $5$.
• Liczba jest podzielna przez $3$, jeśli suma jej cyfr jest podzielna przez $3$.

Ta ostatnia reguła nie jest sztuczką. Wynika z arytmetyki modularnej.

Arytmetyka modularna: działanie na resztach

Gdy dwie liczby całkowite dają tę samą resztę przy dzieleniu przez $n$, mówimy, że są przystające modulo $n$. Zapisujemy to jako

$$a \equiv b \pmod n$$

To znaczy, że $n$ dzieli $a-b$.

Na przykład

$$17 \equiv 5 \pmod{12}$$

ponieważ zarówno $17$, jak i $5$ dają resztę $5$ przy dzieleniu przez $12$, a także dlatego, że $12$ dzieli $17 - 5 = 12$.

To jest przydatne, ponieważ możesz zastąpić liczbę prostszą liczbą z nią przystającą. Na zegarze $12$-godzinnym dodanie $15$ godzin daje ten sam efekt co dodanie $3$ godzin, ponieważ

$$15 \equiv 3 \pmod{12}$$

Przykład: dlaczego $231$ jest podzielne przez $3$?

Weźmy liczbę $231$.

Najpierw zapiszmy ją w postaci wynikającej z wartości miejsc:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

Teraz pracujemy modulo $3$. Ponieważ

$$10 \equiv 1 \pmod 3$$

to wynika stąd, że

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

Zatem

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

Ponieważ $231 \equiv 0 \pmod 3$, liczba jest podzielna przez $3$.

To wyjaśnia regułę sumy cyfr: w systemie dziesiętnym każda potęga liczby $10$ jest przystająca do $1$ modulo $3$, więc cała liczba ma tę samą resztę co suma jej cyfr.

A po wykonaniu dzielenia mamy

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

więc $231$ jest liczbą złożoną, a nie pierwszą.

Częste błędy w teorii liczb

Traktowanie $1$ jako liczby pierwszej

$1$ nie jest liczbą pierwszą. Liczba pierwsza musi mieć dokładnie dwa dodatnie dzielniki, a $1$ ma tylko jeden.

Zapominanie o warunku w podzielności

Zapis $b \mid a$ ma sens tylko wtedy, gdy $b \ne 0$. Dzielenie przez zero jest niedozwolone.

Mylenie równości z przystawaniem

$17 \equiv 5 \pmod{12}$ nie oznacza, że $17 = 5$. Oznacza, że różnią się o wielokrotność $12$.

Nadużywanie reguł podzielności

Niektóre testy są szybkie, ponieważ arytmetyka w systemie dziesiętnym sprawia, że dobrze działają. To nie znaczy, że każdy dzielnik ma prostą regułę opartą na cyfrach.

Gdzie pojawia się teoria liczb

Na poziomie szkolnym teoria liczb pojawia się przy rozkładzie na czynniki, zadaniach z resztami, dowodach podzielności i pytaniach typu zegarowego. Występuje też wtedy, gdy skracasz ułamki, szukasz wspólnych dzielników albo rozwiązujesz problemy z powtarzającymi się cyklami.

Na głębszym poziomie liczby pierwsze i arytmetyka modularna są też kluczowe w kryptografii i informatyce. Nie potrzebujesz tej wiedzy, żeby korzystać z tych idei, ale pomaga ona zrozumieć, dlaczego teoria liczb ciągle pojawia się w zastosowaniach.

Spróbuj samodzielnie

Spróbuj przeprowadzić to samo rozumowanie dla liczby $462$. Najpierw użyj sumy cyfr, aby sprawdzić podzielność przez $3$, a potem rozłóż ją na czynniki na tyle, by zdecydować, czy jest pierwsza, czy złożona.

Jeśli chcesz sprawdzić swoją metodę, rozwiąż podobne zadanie o podzielności lub resztach w solverze matematycznym i porównaj kroki arytmetyki modularnej ze swoimi.