Numere prime între ele

În matematică, două numere întregi sunt prime între ele sau coprime dacă ele nu au alt divizor comun în afară de 1, sau, altfel spus, dacă cel mai mare divizor comun al lor este divizorul impropriu 1.

Algoritmul lui Euclid reprezintă o metodă rapidă de a afla dacă două numere sunt sau nu prime între ele.

Gabriel Lamé a demonstrat că cel mai mare divizor comun a două numere întregi se află, aplicând algoritmul lui Euclid, în maximum 5*k pași, unde k este numărul cifrelor celui mai mic dintre cele două numere.

Numerele 14 și 25 sunt prime între ele sau coprime deoarece 1 este singurul divizor comun. Pe de altă parte, 14 și 21 nu sunt coprime, deoarece sunt ambele divizibile cu 7.

Ocurențe

Cel mai simplu caz de prezență sau ocurență simultană a unor numere coprime este în raporturi de astfel de numere care formează fracții ireductibile. De exemplu numerele co-prime 3 și 5 sau 7 și 9, 9 nefiind un număr prim, ci doar coprim cu 7.