Liczba pierwsza ma dokładnie dwa dzielniki naturalne: $1$ i samą siebie. Liczba złożona ma ich więcej. Jedynka nie jest ani pierwsza, ani złożona - ma tylko jeden dzielnik.
Rozkład na czynniki pierwsze
Podstawowe twierdzenie arytmetyki mówi, że każdą liczbę naturalną większą od 1 da się zapisać jako iloczyn liczb pierwszych i to na dokładnie jeden sposób (z dokładnością do kolejności). Na przykład $360 = 2^3 \cdot 3^2 \cdot 5$. Ten rozkład to „kod genetyczny" liczby - z niego odczytuje się wszystko inne.
NWD i NWW z rozkładu
Mając rozkłady dwóch liczb: do NWD bierzemy wspólne czynniki pierwsze w najniższych potęgach, a do NWW wszystkie czynniki w najwyższych. Zachodzi też wygodna tożsamość $\mathrm{NWD}(a,b) \cdot \mathrm{NWW}(a,b) = a \cdot b$ - stąd znając jedno, drugie liczy się dzieleniem.
Algorytm Euklidesa
Szybszy sposób na NWD, bez rozkładania: dzielimy większą liczbę przez mniejszą i zastępujemy parę $(a, b)$ parą $(b, a \bmod b)$, aż reszta wyniesie zero. Ostatnia niezerowa wartość to NWD. Tak liczy ten kalkulator.
Systemy pozycyjne
W systemie o podstawie $p$ każda pozycja oznacza kolejną potęgę $p$. Zapis $156$ dziesiętnie to $1\cdot10^2 + 5\cdot10^1 + 6\cdot10^0$, a dwójkowo ta sama liczba to $10011100$, czyli suma potęg dwójki. System szesnastkowy potrzebuje szesnastu cyfr, więc po $9$ używa liter $A$-$F$ o wartościach od $10$ do $15$.
