Două numere întregi "a" și "b" sunt prime între ele dacă nu au alt factor comun în afară de 1, sau, altfel spus, dacă cel mai mare divizor comun al lor este 1.

De exemplu, 16 și 17 sunt numere coprime, însă 16 și 24 nu sunt, pentru că ambele se divid cu 8. 1 e coprim cu orice număr întreg; 0 e coprim doar cu 1 și -1. Algoritmul lui Euclid reprezintă o metodă rapidă de a afla dacă două numere sunt sau nu prime între ele: Algoritmul lui Euclid