Numeri invertibili modulo N

Un numero $ a $ è invertibile modulo $ n $ se esiste un numero $ b $ tale che \[ a \cdot b \equiv 1 \pmod{n} \]

Gli invertibili modulo $ n $ sono i numeri che hanno un inverso rispetto alla moltiplicazione modulo $ n $.

In altre parole, moltiplicando $ a $ per $ b $, otteniamo un resto di 1 quando dividiamo per $ n $. In questo caso, $ b $ si chiama inverso moltiplicativo di $ a $ modulo $ n $.

Quindi, gli invertibili in un modulo $ n $ esistono solo se il numero $ a $ è coprimo (relativamente primo) con $ n $. Cioé se il massimo comune divisore tra $ a $ e $ n $ è uguale a 1.

$$ MCD(a, n) = 1 $$

Nota. Il numero di invertibili è dato dalla funzione di Eulero $ \varphi(n) $ che restituisce gli interi coprimi da 1 a $ n $. Inoltre, l'insieme degli invertibili modulo $ n $ formano un gruppo moltiplicativo che in genere viene indicato con $ U(\mathbb{Z}_n) $. All'interno del gruppo moltiplicativo possono trovarsi anche le radici primitive modulo n, ossia quei numeri le cui potenze generano l'intero gruppo .

Un esempio pratico

Considero il modulo $ n = 7 $. Quali numeri sono invertibili?

Cerco gli inversi moltiplicativi da 0 a 6:

$ 0 $ non è mai invertibile perché $ 0 \cdot x \equiv 0 \pmod{7} $ per ogni numero $ x \in [0,6] $
$ 1 $ è invertibile perché $ 1 \cdot 1 \equiv 1 \pmod{7} $ Quindi, l'inverso di 1 è 1.
$ 2 $ è invertibile perché $ 2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} $ Quindi l'inverso di 2 è 4, e viceversa.
$ 3 $ è invertibile perché $ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7} $ Quindi l'inverso di 3 è 5, e viceversa.
$ 4 $ è invertibile perché $ 4 \cdot 2 \equiv 8 \equiv 1 \pmod{7} $ (già visto)
$ 5 $ è invertibile perché $ 5 \cdot 3 \equiv 15 \equiv 1 \pmod{7} $ (già visto)
$ 6 $ è invertibile perché $ 6 \cdot 6 \equiv 36 \equiv 1 \pmod{7} $

Da notare che lo zero non è mai invertibile, per questa ragione spesso non si considera mai.

Quindi, gli invertibili modulo 7 sono:

$$ U(\mathbb{Z}_7) = \{1, 2, 3, 4, 5, 6\} $$

Questi numeri formano il gruppo moltiplicativo modulo 7.

Tra questi invertibili si trovano alcuni elementi speciali, detti "radici primitive modulo n" che sono in grado di generare l'intero gruppo.

Ad esempio, il numero 2 non è una radice perché le sue potenze non generano tutti i numeri del gruppo. $$ 2^1 = 2 \pmod{7} \\ 2^2 = 4 \pmod{7} \\ 2^3 = 8 \equiv 1 \pmod{7} $$ Il numero 3 è, invece, una radice modulo 7 perché le sue potenze generano tutti gli elementi del gruppo. $$ 3^1 = 3 \pmod{7} \\ 3^2 = 9 \equiv 2 \pmod{7} \\ 3^3 = 27 \equiv 6 \pmod{7} \\ 3^4 = 3^2 \cdot 3^2 = 9 \cdot 9 = 81 \equiv 4 \pmod{7} \\ 3^5 = 3^3 \cdot 3^2 = 6 \cdot 9 = 54 \equiv 5 \pmod{7} \\ 3^6 = 3^3 \cdot 3^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$

Esempio 2

In questo esercizio devo cercare gli invertibili modulo 14.

Un numero $ a $ è invertibile se e solo se è primo con 14, cioè $ MCD(a, 14) = 1 $. Cioé se $ a $ NON è un divisore di $ n=14 $

I numeri da 1 a 13 sono:

\[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 \]

Ora elimino quelli che non sono coprimi con 14.

Il numero 14 è divisibile per 2 e per 7. Quindi non sono invertibili modulo 15 tutti i numeri che sono divisibili per 2 e per 7.

2, 4, 6, 8, 10, 12 sono divisibili per 2, quindi NON invertibili nel modulo 14
7 è divisibile per 7, quindi NON invertibile nel modulo 14

I numeri rimanenti sono invertibili modulo 14:

\[ U(\mathbb{Z}_{14}) = \{1, 3, 5, 9, 11, 13\} \]

Questi sono i numeri che compaiono nel gruppo moltiplicativo modulo 14, ed è qui che entrano in gioco le radici primitive: una radice primitiva è un numero le cui potenze generano tutti questi invertibili.

Ad esempio, nel caso del modulo 14, una radice primitiva è il numero $ r = 5 $, perché le sue potenze generano tutti i numeri invertibili modulo 14: \[ 5^1 \equiv 5 \pmod{14} \\ 5^2 \equiv 11 \pmod{14} \\ 5^3 \equiv 13 \pmod{14} \\5^4 \equiv 5 \pmod{14} \\ 5^5 \equiv 3 \pmod{14} \\ 5^6 \equiv 1 \pmod{14} \] Dopo 6 potenze, il ciclo si ripete. Altre radici primitive sono il numero $ r=3 $ e $ r=5 $. Viceversa, i numeri $ r=9 $, $ r=11 $ e il numero $ r=13 $ non sono radici primitive modulo 14 perché le loro potenze non generano tutto il gruppo. Ad esempio, le potenze di $ r=9 $ generano solo tre elementi del gruppo. \[ 9^1 \equiv 9 \pmod{14} \\ 9^2 = 81 \equiv 11 \pmod{14} \\ 9^3 = 9^2 \cdot 9^1 = 11 \cdot 9 = 99 \equiv 1 \pmod{14} \]

E così via.