Le classi invertibili e inverse della congruenza modulo n

Cos'è una classe invertibile

Una classe dell'insieme Zn delle classi resto modulo n $$ a \equiv b \mod n $$ è invertibile se il massimo comune divisore MCD(a,n) è uguale a uno $$ MCD(a,n)=1 $$

Un esempio pratico

L'insieme delle classi di resto Z8 modulo 8 è

$$ Z_8= \{ \bar{0}, \bar{1}, \bar{2}, \bar{3}, \bar{4}, \bar{5}, \bar{6}, \bar{7} \} $$

Cerco le classi (a) che rispettano la condizione MCD(a,n)=1 ossia le coppie (a,n) di numeri interi relativamente primi (coprimi).

$$ MCD(1,8)=1 \\ MCD(3,8)=1 \\ MCD(5,8)=1 \\ MCD(7,8)=1 $$

Quindi, le classi invertibili di Z8 sono

$$ U(Z_8) = \{ \bar{1}, \bar{3}, \bar{5}, \bar{7}, \} $$

Nota. L'insieme delle classi invertibili di un insieme Zn è indicato con la lettera U(Zn).

Ora devo cercare le classi inverse risolvendo le rispettive congruenze

$$ \bar{1} \cdot x \equiv 1 \mod 8 \\ \bar{3} \cdot x \equiv 1 \mod 8 \\ \bar{5} \cdot x \equiv 1 \mod 8 \\ \bar{7} \cdot x \equiv 1 \mod 8 $$

Le soluzioni x delle congruenze sono 1, 3, 5, 7

$$ \bar{1} \cdot 1 \equiv 1 \mod 8 \\ \bar{3} \cdot 3 \equiv 1 \mod 8 \\ \bar{5} \cdot 5 \equiv 1 \mod 8 \\ \bar{7} \cdot 7 \equiv 1 \mod 8 $$

$$ \bar{1} \equiv 1 \mod 8 \\ \bar{9} \equiv 1 \mod 8 \\ \bar{25} \equiv 1 \mod 8 \\ \bar{49} \equiv 1 \mod 8 $$

$$ \bar{1} \equiv 1 \mod 8 \\ \bar{1} \equiv 1 \mod 8 \\ \bar{1} \equiv 1 \mod 8 \\ \bar{1} \equiv 1 \mod 8 $$

Pertanto, le classi inverse di Z8 sono

$$ \{ \bar{1}, \bar{3}, \bar{5}, \bar{7}, \} $$

Quante sono le classi invertibili?

Per conoscere quante classi di Zn sono invertibili posso usare la funzione di Eulero.

Nell'insieme Zn esistono φ(n) classi invertibili.

Esempio

La funzione di Eulero applicata all'insieme Z8 è

$$ φ(8) = 4 $$

Nota. I numeri relativamente primi da 1 a 8 sono { 1,3,5,7 }. Pertanto sono quattro. Le classi invertibili dell'insieme Z8 sono U(Z8)={ 1, 3, 5, 7}

Dimostrazione e spiegazione

Una classe a è invertibile se esiste una classe x tale che

$$ \bar{a} \cdot \bar{x} = 1 $$

Quindi, per capire se una classe è invertibile devo risolvere la congruenza

$$ ax \equiv 1 \mod n $$

Questa congruenza ammette soluzioni soltanto se il massimo comune divisore MCD(a,n) è uguale a 1.

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

Quindi, le condizioni sono due

$$ \begin{cases} 1 \le a < n \\ MCD(a,n)=1 \end{cases} $$

Sono le stesse condizioni rispettate dai numeri della funzione di Eulero.

Quindi, usando la formula di Eulero posso individuare quante classi φ(n) di Zn soddisfano queste caratteristiche.

    Le classi dell'insieme resto di un numero primo

    In un insieme delle classi di resto Zp tutte le classi non nulle sono invertibili se il modulo p è un numero primo.

    Nell'insieme Zp ci sono p-1 classi invertibili ( la classe nulla è esclusa ).

    Esempio

    L'insieme Z5 è composto dalle seguenti classi

    $$ Z_5= \{ \bar{0}, \bar{1}, \bar{2}, \bar{3}, \bar{4} \} $$

    Le classi invertibili sono

    $$ U(Z_5)= \{ \bar{1}, \bar{2}, \bar{3}, \bar{4} \} $$

    Tutte le classi non nulle di Z5 sono invertibili.

    Le classi invertibili sono p-1 ossia 5-1 = 4 come confermato anche dalla funzione di Eulero.

    $$ φ(5) = 4 $$

    Nota. I numeri relativamente primi modulo 5 sono { 1,2,3,4 }. Il massimo comune divisore tra ognuno di questi numeri e il modulo p=5 è sempre uguale a 1. $$ MCD(1,5)=1 \\ MCD(2,5)=1 \\ MCD(3,5)=1 \\ MCD(4,5)=1 $$

    E così via.

     


     

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

    FacebookTwitterLinkedinLinkedin
    knowledge base

    Tool