Inverso ... tramite Eulero
Ho trovato questo esercizio in rete, ma non riesco a capire perchè alla fine esce 19.
b) Calcolare l’inverso di 17 modulo 23 (cio ́ trovare x tale che 17x ≡ 1 (mod 23)).
RISPOSTA L’inverso esiste poichè (17, 23) = 1. Grazie all’identità di Bezout troviamo
x = −4. Modulo 23 la soluzione è quindi 19.
Lo chiedo perchè sto facendo questo esrcizio. devo trovare l'inverso di 7 in $ZZ_18$
Tramite Bezout ottengo questo:
18= 7*2 + 4
7= 4*1 + 3
4= 3*1 + 1
Arrivo ad avere questo:
1 = 18 * 2 + 7 * (-5)
Poi???
b) Calcolare l’inverso di 17 modulo 23 (cio ́ trovare x tale che 17x ≡ 1 (mod 23)).
RISPOSTA L’inverso esiste poichè (17, 23) = 1. Grazie all’identità di Bezout troviamo
x = −4. Modulo 23 la soluzione è quindi 19.
Lo chiedo perchè sto facendo questo esrcizio. devo trovare l'inverso di 7 in $ZZ_18$
Tramite Bezout ottengo questo:
18= 7*2 + 4
7= 4*1 + 3
4= 3*1 + 1
Arrivo ad avere questo:
1 = 18 * 2 + 7 * (-5)
Poi???
Risposte
Poi hai finito, direi. $-5=13 (mod 18)$ e quindi l'inverso di $7$ in $ZZ_18$ è $13$. Enough.
perche -5 = 13 mod 18 ???
Sinceramente non vedo il problema, ma potrebbe essere miopia (o dintorni).
In generale, dato un intero x, $x=a (mod n)$ se appartiene all'insieme $a+nk$ con $k$ intero. In questo modo, $n|x-a$. La relazione di congruenza sugli interi è una relazione di equivalenza, si dimostra banalmente, e quindi partiziona $ZZ$ in classi di equivalenza: le classi di resto modulo $n$. Quando si chiede di determinare l'inverso di un intero $mod n$, si chiede di mostrare un rappresentante della classe di equivalenza, di solito si usa l'unico compreso tra $1$ e $n$.
Nel tuo ultimo esempio $3$ è banalmente congruo a se stesso e tra le altre cose è anche la soluzione.
Spero di essere stato chiaro, in caso contrario non esitare a domandare. Proverò a rispondere, competenze e cinema di stasera permettendo
.
In generale, dato un intero x, $x=a (mod n)$ se appartiene all'insieme $a+nk$ con $k$ intero. In questo modo, $n|x-a$. La relazione di congruenza sugli interi è una relazione di equivalenza, si dimostra banalmente, e quindi partiziona $ZZ$ in classi di equivalenza: le classi di resto modulo $n$. Quando si chiede di determinare l'inverso di un intero $mod n$, si chiede di mostrare un rappresentante della classe di equivalenza, di solito si usa l'unico compreso tra $1$ e $n$.
Nel tuo ultimo esempio $3$ è banalmente congruo a se stesso e tra le altre cose è anche la soluzione.
Spero di essere stato chiaro, in caso contrario non esitare a domandare. Proverò a rispondere, competenze e cinema di stasera permettendo
.
E' scomparso "il tuo ultimo esempio" e il $3$ di sopra sembra campato in aria. Non modifico perchè penso che la definizione data sia utile anche per rispondere alla tua nuova domanda. Anche se per questo è sufficiente notare che $18|-13-5$.
(piccola distrazione
)
(piccola distrazione
)
Si scusa credevo di aver scritto una cavolata. non vorrei sembrare pesante, ma io nn ho ancora capito. mi puo dire come devo ragionare passo passo partendo da: 1 = 18 * 2 + 7 * (-5).
Forse quello che nn ho capito è davvero l'operazione modulo? Mi sembro deficiente. Perchè in base a quello che hai scritto precedentemente mi sono fatto un idea. ho visto altri esempi e il risultato viene giusto. Ma nell'esempio: 16 * -2 + 11 * 3 ... ho problemi.
Forse quello che nn ho capito è davvero l'operazione modulo? Mi sembro deficiente. Perchè in base a quello che hai scritto precedentemente mi sono fatto un idea. ho visto altri esempi e il risultato viene giusto. Ma nell'esempio: 16 * -2 + 11 * 3 ... ho problemi.
"Jack Durden":
perche -5 = 13 mod 18 ???
perché $-5+18=13$
"amelia":
[quote="Jack Durden"]perche -5 = 13 mod 18 ???
perché $-5+18=13$[/quote]
Quindi avendo: 16 * (-2) + 11 * 3
Avrei 3 + 16 = 19??
deve uscire 3!!
EDIT in $U_16$
Spiegazione informale:
l'equazione si può scrivere come $18*(-2)=7*(-5)-1$. Questo vuol dire che sottraendo $1$ a $7*(-5)$ si ottiene un multiplo di $18$. Nel linguaggio delle congruenze possiamo scrivere $7*(-5)=1 (mod 18)$. Per definizione di inverso la classe di equivalenza di $-5$ è proprio quello che stiamo cercando. Per concludere troviamo l'unico $x$ intero compreso tra $1$ e $18$ per il quale risulta $x=-5 (mod 18)$. Per verificare che $x=13$ basta far vedere che $18|13+5$ e questo è ovvio.
Consiglio pratico (più utile della spiegazione informale):
ripassa congruenze, moduli e affini.
Ciao
l'equazione si può scrivere come $18*(-2)=7*(-5)-1$. Questo vuol dire che sottraendo $1$ a $7*(-5)$ si ottiene un multiplo di $18$. Nel linguaggio delle congruenze possiamo scrivere $7*(-5)=1 (mod 18)$. Per definizione di inverso la classe di equivalenza di $-5$ è proprio quello che stiamo cercando. Per concludere troviamo l'unico $x$ intero compreso tra $1$ e $18$ per il quale risulta $x=-5 (mod 18)$. Per verificare che $x=13$ basta far vedere che $18|13+5$ e questo è ovvio.
Consiglio pratico (più utile della spiegazione informale):
ripassa congruenze, moduli e affini.
Ciao
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo