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.

     

     


     

    Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

    FacebookTwitterLinkedinLinkedin
    knowledge base

    I numeri primi

    FAQ