Metodo per trovare gli elementi invertibili in Zn

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Metodo per trovare gli elementi invertibili in Zn #45291

avt
Calliope
Punto
Buon pomeriggio ragazzi, non riesco a capire come devo comportarmi con gli elementi invertibili in Zn. Sono disperata!

Potreste gentilmente dirmi se c'è un metodo semplice, veloce e sopratutto che valga sempre, per trovare gli elementi invertibili in Zn?

Per esempio

35x=1 in \mathbb{Z}_6
5x=1\ Mod(6)
x=5^{-1}\ Mod(6)

Confido nella vostra cortesia!
 
 

Re: Metodo per trovare gli elementi invertibili in Zn #45345

avt
Galois
Coamministratore
Ciao Calliope emt

Inizio dicendo che non capisco cosa voglia dire con:

Per esempio

35x=1 in \mathbb{Z}_6
5x=1\ Mod(6)
x=5^{-1}\ Mod(6)


Con la speranza che mi chiarisca questo dubbio, ti posso dire che c'è un metodo per trovare gli elementi invertibili di Zn

ed è anche molto semplice.

Iniziamo col dire che gli elementi di Zn sono classi e non numeri. Nello specifico:

Zn := \left\{\left[0\right]_{\equiv n}, \left[1\right]_{\equiv n}, \left[2\right]_{\equiv n}, ... \left[n-1\right]_{\equiv n}\right\}

Nel caso Z6:

Z6 := \left\{\left[0\right]_{\equiv 6}, \left[1\right]_{\equiv 6}, \left[2\right]_{\equiv 6}, \left[3\right]_{\equiv 6}, \left[4\right]_{\equiv 6}, \left[5\right]_{\equiv 6}\right\}

Dove, ricordo che, in generale:

\left[a\right]_{\equiv n}= \left\{b\in Z | a \equiv_{n} b\right\}

detto in parole povere \left[a\right]_{\equiv n} è l'insieme di tutti gli interi tali che, divisi per n danno lo stesso resto che da' la divisione di a per n

Ciò dovrebbe esserti noto, ma ho voluto chiarirlo a scanso di equivoci.

Quindi, detto ciò, gli elementi invertibili di Zn e si indicano con

U(Zn)

sono quegli elementi (ovvero classi) \left[a\right]_{\equiv n} tali che

mcd(a,n)=1

Facciamo degli esempi.

Prendiamo sempre

Z6 := \left\{\left[0\right]_{\equiv 6}, \left[1\right]_{\equiv 6}, \left[2\right]_{\equiv 6}, \left[3\right]_{\equiv 6}, \left[4\right]_{\equiv 6}, \left[5\right]_{\equiv 6}\right\}

Allora

U(Z6) = \left\{ \left[1\right]_{\equiv 6}, \left[5\right]_{\equiv 6}\right\}

in quanto mcd(1,6)=mcd(5,6)=1

mentre

mcd(2,6) = mcd(4,6) = 2 \neq 1

e

mcd(3,6)=3 \neq 1

e

mcd(0,6)=6 \neq 1

Altro esempio:

U(Z10) = \left\{ \left[1\right]_{\equiv 10}, \left[3\right]_{\equiv 10}, \left[7\right]_{\equiv 10}, \left[9\right]_{\equiv 10} \right\}

in quanto

mcd(1,10)=mcd(3,10)=mcd(7,10)=mcd(9,10)=1

Quindi:

per trovare gli elementi invertibili di Zn
e ribadisco che tali elementi sono in realtà CLASSI DI EQUIVALENZA, basta prendere le classi che hanno come rappresentante quei numeri interi minori di n, che sono primi con esso

Ho ribadito più volte che sono classi perché, come ben saprai e dalla definizione che ti ho dato sopra si vede subito, ogni classe ha sì un unico rappresentante, ma ad esse appartengono infiniti interi.

Spero di aver esaudito la tua richiesta emt
Ringraziano: Omega, Pi Greco, Calliope, CarFaby, dany.collu

Re: Metodo per trovare gli elementi invertibili in Zn #45370

avt
Calliope
Punto
Ciao Galois,grazie per aver risposto. Allora, innanziutto cerco di essere più chiara: quel 35x = 1 modulo 6 era una parte di un problema più lungo, in cui in sostanza si doveva impostare un sistema di congruenze.

Io intendevo dire: ho l'equazione 35x=1 in \mathbb{Z}. La voglio in \mathbb{Z}_6.

Qual è il resto di 35 diviso 6?

6 * 5 = 30 + 5 = 35

L'equazione diventa 5x=1 mod(6).

La soluzione dovrebbe essere x=1*5^{-1}\ mod(6)

Spero di essere stata più chiara, ovviamente correggimi se sbaglio emt

Quello che hai scritto tu è giusto,però a mio avviso risulta un po' scomodo se si lavora con numeri alti, come per esempio \mathbb{Z}_{145}, inoltre è la pura applicazione della teoria.
Io so una specie di trucchetto, vorrei, se possibile, che mi diceste se vale sempre e il motivo per cui vale, allora:

se io voglio calcolare a^{-1} \in \mathbb{Z}_n imposto una specie di ciclo for: se n*1 + 1/a dà un resto finito quello è l'inverso,
altrimenti continuo con n*2 + 1/a se da resto finito bene altrimenti continuo...Questo è l'ennesimo trucchetto che mi hanno proposto,quelli precedenti non funzionavano sempre...questo però mi sembra più efficace. Chiedo conferma a voi!

Scusate per la lunghezza del messaggio,era solo per essere il più chiara possibile!

Re: Metodo per trovare gli elementi invertibili in Zn #45381

avt
Galois
Coamministratore
Scusami, ma continuo a non capire.. forse sono io.. ci ho pensato un sacco ma non riesco a trovare il motivo per cui il "trucchetto" che dici tu deve valere.

Supposto sempre che stiamo lavorando con classi,

Trovare l'inverso di a modulo n, vuol dire trovare un intero x, tale che:

ax \equiv_{n} 1

Facciamo un esempio stupido.

Ci proponiamo di trovare l'inverso di 2 modulo 7.

Ovviamente tale inverso è 4, in quanto:

2 * 4 = 8 \equiv_{7} 1

Pertanto l'invero di 2 modulo 7 è 4, ovvero

2^{-1} = 4(mod 7)

Vediamo ora il tuo "trucchetto":

se io voglio calcolare a^{-1} \in \mathbb{Z}_n imposto una specie di ciclo for: se n*1 + 1/a dà un resto finito quello è l'inverso,
altrimenti continuo con n*2 + 1/a se da resto finito bene altrimenti continuo...


Cioè, non capisco cosa fai e soprattutto come fai a basarti su un resto finito, visto che, per il teorema sull'algoritmo euclideo, dati due qualunque interi a e b, con b\neq 0 esistono e sono unici:

q \in Z ed r \in N

tali che:

a = bq + r

o analogamente:

a:b = q, resto r

ovvero da una QUALSIASI divisione tra interi di ottiene sempre un resto intero.

Detto ciò analizziamo nel dettaglio il tuo "trucco"

Ci proponiamo sempre di trovare l'inverso di a=2 mod n=7.

Se ho ben capito fai in questo modo:

vedi innanzitutto che resto ti da:

n*1 + \frac{1}{a}

nel nostro caso:

7 + \frac{1}{2}

Ora,

7 + \frac{1}{2} = \frac{15}{2}

che dà quoziente 7 e resto 1 che è un resto finito.

Questo quindi, secondo il tuo modo di procedere di porta a dire cosa?
emt

Mi sto davvero sforzando di capire.. scusami ma non ci riesco..

Fammi un esempio e vedo se riesco ad esserti utile emt

Scusami ancora
Ringraziano: Omega, Pi Greco, Calliope, CarFaby

Re: Metodo per trovare gli elementi invertibili in Zn #45408

avt
Calliope
Punto
Innanzi tutto si,stiamo lavorando con le classi di resto.
scusami forse non hai capito la procedura perchè mi sono scordata a mettere una parentesi.emt ieri quando ho risposto era tardi...si dovrebbe scrivere a mente lucida...colpa mia
nell'esempio che proponi il trucco funziona
tu cerchi l'inverso di 2 modulo 7

7*1=7
7+1=8
8/2=4

Io intendevo questo.in questo caso bastava il primo tentativo.
Io ti propongo un'esempio in cui il primo tentativo non andava bene

cerchiamo l'inverso di 5 modulo 18.
18*1=18
18+1=19 ,5 non divide 19,o meglio 19/5=3.8,non va bene,scarto questo risultato e vado avanti:
18*2=36
36+1=37 no va bene,vado avanti
18*3=54
54+1=55
55/5=11

11 dovrebbe essere l'inverso di 5 in Z18.


Comunque tenevo a precisare che la mia conoscenza sull'argomento non è sufficiente ancora,quindi critiche o correzioni sono le benvenute.

Re: Metodo per trovare gli elementi invertibili in Zn #45455

avt
Galois
Coamministratore
OK! Ora ci siamo!

Bene! Tu ora vuoi sapere se il tuo procedimento va sempre bene o ci sono dei casi in cui non vale.. giusto?

Siamo matematici, e come tali, l'unico modo di verificare se una cosa è sempre vera è quello di dimostrarla!

Vediamo un po' ..

Consideriamo Z_{n} e sia a un elemento di Zn (ricordiamo che sono sempre classi) tale che

mcd(a,n)=1 (*)

Ci proponiamo di determinare l'inverso (moltiplicativo) a^{-1} di a modulo n

Per definizione di inverso:

a*a^{-1} \equiv_{n} 1

che equivale a dire:

n | (a*a^{-1})-1

ovvero:

\exists q \in Z | nq=(a*a^{-1})-1

da cui:

(a*a^{-1}) = nq + 1

e quindi:

a^{-1} = \frac{nq+1}{a}

a patto che

\frac{nq+1}{a}

sia un intero!


(*) Ricordo infatti che gli elementi invertibili di Z_{n}, ovvero gli elementi per cui si può trovare l'inverso sono gli interi a tali che sono primi con n.. Questo te l'avevo già detto nella mia prima risposta, ma è sempre bene ricordarlo, inoltre dovendo essere

mcd(a,n)=1

questo assicura che a \neq 0 e quindi ha senso l'ultima divisione fatta. -Fine (*)-




Ecco quindi dimostrato il tuo trucchetto!

Infatti tu ogni volta non fai altro se non fare:

\frac{nq+1}{a}

e verificare se è un intero o meno.

Se è un intero quel numero è l'invero (e l'abbiamo dimostrato).

Se non è un intero vai avanti...

Nel tuo esempio, di determinare l'inverso di 5 modulo 18 (che esiste in quanto 5 e 18 sono primi fra loro), hai:

n=18

a=5

e hai preso, all'inizio:

q=1

poi:

18*1 = 18 = nq (l'

nq

della cosa che abbiamo dimostrato)

18 + 1 = 19 (l'

(nq+1)

della cosa che abbiamo dimostrato)

e infine

\frac{19}{5} (l'

\frac{nq+1}{a}

della cosa che abbiamo dimostrato)

e, non essendo un intero sei andata avanti...

Spero di essere stato chiaro.

In ogni caso il tuo trucchetto va sempre bene! E puoi affermarlo con certezza perché l'abbiamo dimostrato!

Se hai dubbi chiedi pure emt
Ringraziano: Omega, Pi Greco, Calliope, CarFaby

Re: Metodo per trovare gli elementi invertibili in Zn #45519

avt
Calliope
Punto
Grazie mille per la dimostrazione! emt
si quindi la prima cosa che devo verificare è che MCD(a,n)=1
poi fatto questo procedo con il trucchetto.
perfetto mi sei stato di grande aiuto!emt
Ringraziano: Galois

Re: Metodo per trovare gli elementi invertibili in Zn #45521

avt
Galois
Coamministratore
si quindi la prima cosa che devo verificare è che MCD(a,n)=1


esatto!

Ribadisco infatti, fino alla nausea (emt) che un elemento a è invertibile in Zn se e solo se

mcd(a,n)=1

PS: se vuoi, anzi te lo propongo, fai la dimostrazione di ciò. come ogni dimostrazione è molto istruttiva .. e se hai dubbi non esitare a chiedere emt

E mi raccomando.. perché se ad esempio ti chiedessi di trovare l'invero di a=6 in Zn=Z18, la risposta deve essere:

tale elemento non ha inverso in Z18 in quanto

mcd(6,18) = 6 \neq 1

emt
Ringraziano: Omega, Pi Greco, Calliope, CarFaby
  • Pagina:
  • 1
Os