Numere prime între ele

De ce contează?

Două roți dințate cu 8 și respectiv 15 dinți: după câte rotații revine fiecare în poziția de start simultan? Dacă numerele de dinți nu au „nimic în comun", roțile parcurg toate combinațiile posibile. Acel „nimic în comun" e cheia numerelor prime între ele.

Ce înseamnă „prime între ele"

Două numere a și b sunt prime între ele (coprime) dacă singurul lor divizor comun este 1, adică:

cmmdc(a, b) = 1

Atenție: numerele nu trebuie să fie ele însele prime. 8 și 15 sunt prime între ele, deși niciunul nu e număr prim.

Observația-cheie

„Număr prim" și „prime între ele" sunt noțiuni diferite. Prim = un singur număr cu doi divizori. Prime între ele = o pereche fără divizori comuni în afară de 1.

Algoritm pas cu pas: 8 și 15

Folosim Euclid:

`a`	`b`	`a % b`
15	8	7
8	7	1
7	1	0
1	0	stop

cmmdc(8, 15) = 1 → sunt prime între ele.

Implementare C++

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    if (cmmdc(a, b) == 1) {
        cout << "prime intre ele\n";
    } else {
        cout << "NU sunt prime intre ele\n";
    }
    return 0;
}

Pentru 8 15 → „prime intre ele". Pentru 12 18 → cmmdc = 6 → „NU".

Unde apare

Numerele prime între ele apar des în probleme:

Fracții ireductibile: o fracție a/b e simplificată complet ⟺ a și b sunt prime între ele.
Aritmetică modulară: inversul modular al lui a modulo m există ⟺ cmmdc(a, m) = 1.
Indicatorul lui Euler: numără câte numere până la n sunt prime cu n.

Complexitate

Caz	Timp	Spațiu
oricare	O(log(min(a, b)))	O(1)

Un singur apel Euclid — extrem de rapid.

Greșeli frecvente

Capcane reale la numere prime între ele:

Confuzi cu „număr prim": verifici dacă a și b sunt prime, în loc de cmmdc = 1. 8 și 15 sunt coprime fără să fie prime.
Descompunere inutilă: descompui în factori ca să cauți factori comuni — corect, dar lent. Euclid e mult mai rapid.
Cazul cu 1: cmmdc(1, n) = 1 pentru orice n, deci 1 e prim cu orice număr.
Numere negative: lucrează pe valori absolute înainte de cmmdc.

De reținut

Prime între ele ⟺ cmmdc(a, b) = 1 (nu „ambele prime").
Verifici cu un singur apel Euclid, O(log).
Stă la baza fracțiilor ireductibile și a inversului modular.