De ce contează?
Două roți dințate se învârt una în alta. Dacă au 8 și 15 dinți, aceeași pereche de dinți se reîntâlnește abia după 8 × 15 = 120 de dinți — fiecare dinte al uneia ajunge, pe rând, lângă fiecare dinte al celeilalte, pentru că nimic mai mic nu „le sincronizează". Dar dacă au 12 și 18 dinți, se resincronizează mult mai repede, fiindcă împart un factor comun. Numerele care nu împart niciun factor (în afară de 1) se numesc prime între ele.
Intuiția
Două numere sunt prime între ele dacă singurul lor divizor comun este 1.
Cu alte cuvinte, nu există niciun număr mai mare ca 1 care să le împartă pe
amândouă. Asta nu înseamnă că numerele în sine sunt prime — 8 și 15 nu sunt
prime (8 = 2·2·2, 15 = 3·5), dar nu au niciun factor comun, deci sunt prime
între ele. Cheia este o singură mărime: cel mai mare divizor comun, cmmdc.
A fi prime între ele înseamnă cmmdc(a, b) = 1 — nicidecum „ambele numere
sunt prime". Sunt două lucruri complet diferite: primalitatea privește un singur
număr, pe când „prime între ele" descrie relația dintre două numere. Testul
corect este mereu unul singur: calculează cmmdc și vezi dacă iese 1.