Cosa devi sapere sui numeri primi

Funzione φ(n) di Eulero

Dati due numeri naturali a e b maggiori di zero, viene detto massimo comune divisore di a e b il più grande dei divisori comuni ad a e b e tale numero viene indicato con il simbolo

MCD(a, b)

Ad esempio, determiniamo il massimo comune divisore di 18 e 30. I divisori di 18 sono:

1, 2, 3, 6, 9, 18

I divisori di 30 sono:

1, 2, 3, 5, 6, 10, 15, 30

i divisori comuni sono:

1, 2, 3, 6

Il più grande divisore è 6 e quindi:

MCD(18, 30) = 6

La ricerca del MCD(a, b) può essere resa più semplice scomponendo in fattori primi a e b. Ad esempio, scomponiamo in fattori primi 18 e 30

18 = 2⋅3²;      30 = 2⋅3⋅5

Ora, il massimo comune divisore è dato dal prodotto dei fattori primi comuni, presi con l'esponente più piccolo e nel nostro caso sono il 2 e il 3 e quindi:

MCD(18, 30) = 2 ⋅ 3 = 6

Se i due numeri a e b non hanno nessun fattore primo in comune allora il loro massimo comune divisore è uguale a 1 in tal caso i numeri a e b si dicono primi tra loro oppure coprimi. Ad esempio, 15 e 28 non avendo fattori primi in comune sono coprimi e MCD(15, 28) = 1.

Eulero introdusse una nuova relazione detta funzione di Eulero indicata con la notazione φ(n) si legge phi di n:

Per ogni intero n positivo φ(n) è il numero di interi compresi tra 1 e n che sono coprimi con n.

Ad esempio, φ(18) = 6 perchè i numeri minori o uguali a 18 e relativamente primi con 18 sono 1, 5, 7, 11, 13, 17. Ecco ad esempio, i valori della funzione φ(n) per alcuni valori di n .

In partiicolare se n = p dove p è un numero primo allora:

φ(p) = p - 1

La funzione φ(n) possiede particolari proprietà:

• Se a e b sono due numeri coprimi allora:

  φ(a ⋅ b) = φ(a) ⋅ φ(b)

  Ad esempio, 52 = 4 ⋅ 13 e 4 e 13 sono coprimi e quindi:

  φ(52) = φ(4 ⋅ 13) = φ(4) ⋅ φ(13) = 2 ⋅ 12 = 24

• Se p è un numero primo allora per ogni h≥1 intero si ha:

  φ(p^h) = p^h - p^h-1

  Ad esempio, per 2⁵ si ha:

  φ(2⁵) = 2⁵ - 2^5-1 = 32 - 16 = 16

  Infatti i numeri relativamente primi con 2⁵ = 32 sono:

  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31.

Utilizzando queste due proprietà possiamo facilmente calcolare qualsiasi φ(n) per ogni n naturale del quale si conosca la fattorizzazione. Infatti, se

Possiamo scrivere

E se raccogliamo a fattor comune la potenza massima all'interno di ogni parentesi si ottiene:

Cioè

Ad esempio, calcoliamo φ(120). La scomposizione in fattori primi di 120 è:

120 = 2³ ⋅ 3 ⋅ 5

Per cui:

La funzione φ(n) ha molte applicazioni. Ad esempio, se un numero intero positivo n è prodotto di due primi distinti, la conoscenza di φ(n) consente di poter fattorizzare n. Infatti, se n = p ⋅ q, allora si ha

φ(n) = (p - 1)(q - 1)

e risolvendo il sistema

si determina p e q e quindi la fattorizzazione di n. Ad esempio, se n=2867 e φ(2867)=2760 sapendo che n=p⋅q e risolvendo il sistema

si ottiene p=47 e q=61 e quindi 2867=47⋅61.