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.