Interi coprimi

Cosa sono i numeri coprimi

I coprimi ( co-primi ) sono una coppia di interi (a,b) che hanno il massimo comune divisore uguale a 1. $$ MCD(a,b)=1 $$

Sono anche detti numeri relativamente primi ossia contemporaneamente primi tra loro.

Il Massimo Comune Divisore (MCD) dei numeri co-primi è 1.

Nota. Non necessariamente i numeri co-primi devono essere numeri primi. Anche coppie di numeri "non primi" possono essere co-primi. Sicuramente, le coppie numeri primi sono co-primi. Tuttavia, il fatto che uno dei due numeri sia un numero primo, non necessariamente vuol dire che siano co-primi.

Per capire se due numeri \( a \) e \( b \) sono relativamente primi, basta costruire una frazione \( \frac{a}{b} \), se la frazione è irriducibile allora sono coprimi.

Esempio

I numeri 6 e 35 sono interi co-primi perché non hanno divisori in comune.

$$ MCD(6,35)=1 $$

I numeri 6 e 36 non sono co-primi perché hanno un divisore in comune (6).

$$ MCD(6,36)=6 $$

I numeri 15 e 28 sono co-primi.

$$ MCD(15,28)=1 $$

Note

Alcune note aggiuntive sui numeri coprimi.

• Proprietà di Bézout
  Se due numeri \( a \) e \( b \) sono coprimi, allora esistono due numeri interi \( x \) e \( y \) tali che: \[ ax + by = 1
  \] Questa proprietà è utile nella crittografia (es. Algoritmo RSA) e nella risoluzione di equazioni diofantee.

  Nota. L'algoritmo RSA utilizza numeri coprimi per la generazione delle chiavi pubbliche e private. Due numeri \( e \) e \( \varphi(n) \) devono essere coprimi affinché l'algoritmo funzioni.

• Moltiplicazione con numeri coprimi
  Se \( a \) e \( b \) sono coprimi, allora qualsiasi loro potenza è ancora coprima: \[ MCD(a^n, b^m) = 1 \]
  per qualsiasi \( n, m \geq 1 \).
• Funzione di Eulero
  La funzione di Eulero \( \varphi(n) \) conta quanti numeri interi tra \( 1 \) e \( n \) sono coprimi con \( n \). Ad esempio:
  \[ \varphi(10) = 4 \] perché i numeri coprimi con \( 10 \) tra 1 e 10 sono \( 1, 3, 7, 9 \).
• Inverso moltiplicativo nelle congruenze modulari
  Se \( a \) e \( m \) sono coprimi, allora \( a \) ha un inverso moltiplicativo modulo \( m \), cioè esiste un numero \( b \) tale che: \[ a \cdot b \equiv 1 \pmod{m} \]  Questo è un concetto centrale nella teoria dei numeri modulari.
• Teorema cinese del resto
  Questo teorema sfrutta numeri coprimi per risolvere sistemi di congruenze.

Nota. Due numeri scelti a caso hanno una probabilità di essere coprimi pari a \( \frac{6}{\pi^2} \approx 0.607 \), che è sorprendentemente alta.

E così via.