Numere prime între ele și simplificarea fracțiilor

Am învățat deja despre CMMDC (Cel Mai Mare Divizor Comun). Acum vom vedea două aplicații foarte utile ale lui.

Ce înseamnă „numere prime între ele”?

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

Cu alte cuvinte:

a și b sunt prime între ele dacă CMMDC(a, b) = 1

Exemple

a	b	CMMDC	Prime între ele?
8	15	1	DA
12	18	6	NU
7	10	1	DA
9	6	3	NU
14	25	1	DA
4	4	4	NU

Observații importante

Două numere prime diferite sunt întotdeauna prime între ele (de exemplu 7 și 13).
Dar numerele nu trebuie să fie prime! De exemplu, 8 și 15 sunt prime între ele, deși niciunul nu e prim.
1 este prim cu orice număr.

Verificarea: sunt prime între ele?

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    int x = a, y = b;

    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }

    if (x == 1) {
        cout << "DA";
    } else {
        cout << "NU";
    }

    return 0;
}

Input:
8 15

Output:
DA

Input:
12 18

Output:
NU

Ce este simplificarea unei fracții?

O fracție a/b este simplificată (sau ireductibilă) dacă a și b sunt prime între ele.

De exemplu:

12/18 nu este simplificată (CMMDC = 6)
12/18 = 2/3 - aceasta este forma simplificată

Cum simplificăm?

Împărțim atât numărătorul cât și numitorul la CMMDC(a, b).

a_simplificat = a / CMMDC(a, b)
b_simplificat = b / CMMDC(a, b)

Codul pentru simplificarea unei fracții

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    // Calculam CMMDC
    int x = a, y = b;

    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }

    int cmmdc = x;

    cout << a / cmmdc << "/" << b / cmmdc;

    return 0;
}

Input:
12 18

Output:
2/3

Pas cu pas

CMMDC(12, 18):
- (12, 18) → r = 12 % 18 = 12 → (18, 12)
- (18, 12) → r = 18 % 12 = 6 → (12, 6)
- (12, 6) → r = 12 % 6 = 0 → (6, 0)
- CMMDC = 6
Simplificare:
- 12 / 6 = 2
- 18 / 6 = 3
- Fracția simplificată: 2/3

Mai multe exemple

Fracție	CMMDC	Simplificată
4/8	4	1/2
15/25	5	3/5
7/3	1	7/3 (deja simplificată)
100/75	25	4/3
36/48	12	3/4
9/9	9	1/1

Verificarea dacă o fracție este deja simplificată

O fracție a/b este simplificată dacă CMMDC(a, b) = 1 - adică dacă a și b sunt prime între ele.

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    int x = a, y = b;

    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }

    if (x == 1) {
        cout << "Fractia este deja simplificata";
    } else {
        cout << "Fractia se poate simplifica";
        cout << endl;
        cout << a / x << "/" << b / x;
    }

    return 0;
}

Input:
7 3

Output:
Fractia este deja simplificata

Input:
36 48

Output:
Fractia se poate simplifica
3/4

Câte perechi prime între ele există de la 1 la n?

O problemă mai interesantă: dat un număr n, câte perechi (a, b) cu 1 <= a < b <= n sunt prime între ele?

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int cnt = 0;

    for (int a = 1; a < n; a++) {
        for (int b = a + 1; b <= n; b++) {
            int x = a, y = b;

            while (y != 0) {
                int r = x % y;
                x = y;
                y = r;
            }

            if (x == 1) {
                cnt++;
            }
        }
    }

    cout << cnt;

    return 0;
}

Input:
6

Output:
11

Care sunt cele 11 perechi?

(1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5), (5,6)

Observă că 1 este prim cu orice număr, deci dă n - 1 perechi singur.

Greșeli frecvente

1. Confuzia: „prime între ele” ≠ „numere prime”

8 și 15 sunt prime între ele (CMMDC = 1), deși niciunul nu e prim.
6 și 35 sunt prime între ele (CMMDC = 1).
2 și 4 nu sunt prime între ele (CMMDC = 2), deși 2 e prim.

2. Uitarea salvării valorilor originale

Algoritmul lui Euclid distruge valorile a și b. Dacă ai nevoie de ele după (pentru simplificare sau afișare), salvează-le în copii:

int x = a, y = b; // copii pentru Euclid

3. Simplificarea doar a numărătorului

Trebuie împărțite ambele la CMMDC:

// GREȘIT:
cout << a / cmmdc << "/" << b;

// CORECT:
cout << a / cmmdc << "/" << b / cmmdc;

Ce să reții

Două numere sunt prime între ele dacă CMMDC(a, b) = 1.
Nu trebuie să fie numere prime - doar să nu aibă divizori comuni.
O fracție se simplifică împărțind numărătorul și numitorul la CMMDC.
Fracția este ireductibilă dacă CMMDC = 1.
1 este prim cu orice număr.
Salvează valorile originale înainte de algoritmul lui Euclid.

Probleme

pbinfoFractii→

pbinfoPrimeintreele1→