Reciproco in $ZZ_n$
salve,
per favore, come faccio a calcolare il reciproco di un numero in $ZZ_n$?, per esempio di $18$ in $ZZ_70$?
se ho per esempio (lo butto così sul momento questo esempio...)
$18x -= 40 (mod 70)$
dovrei ottenere
$x -= 40*(18)^(-1) (mod 70)$
come si rappresenta tale numero $18^(-1)$ o $1/18$, che dir si voglia, in $ZZ_70$?
non mi interessa risolvere la congruenza ma solo il reciproco
grazie mille.
per favore, come faccio a calcolare il reciproco di un numero in $ZZ_n$?, per esempio di $18$ in $ZZ_70$?
se ho per esempio (lo butto così sul momento questo esempio...)
$18x -= 40 (mod 70)$
dovrei ottenere
$x -= 40*(18)^(-1) (mod 70)$
come si rappresenta tale numero $18^(-1)$ o $1/18$, che dir si voglia, in $ZZ_70$?
non mi interessa risolvere la congruenza ma solo il reciproco
grazie mille.
Risposte
Pensa all'identità di Bezout!
Dall'essere [tex]gcd(a,b)=d[/tex] segue che esistono [tex]\lambda, \mu[/tex] tali che [tex]a\cdot \lambda + b \mu = d[/tex], per trovare il reciproco deve essere necessario che il [tex]gcd[/tex] sia [tex]1[/tex].
Dall'essere [tex]gcd(a,b)=d[/tex] segue che esistono [tex]\lambda, \mu[/tex] tali che [tex]a\cdot \lambda + b \mu = d[/tex], per trovare il reciproco deve essere necessario che il [tex]gcd[/tex] sia [tex]1[/tex].
gcd=MCD=massimo comune divisore; gcd è l'acronimo inglese!
Insomma deve [tex]\exists k\in\mathbb{Z}\mid 18x-40=k70[/tex] da cui l'aiuto del teorema di Bezeòut generalizzato!
Insomma deve [tex]\exists k\in\mathbb{Z}\mid 18x-40=k70[/tex] da cui l'aiuto del teorema di Bezeòut generalizzato!
grazie.
Allora facciamo un esempio più semplice e adeguato:
$4x -= 5 (mod 9)$
$MCD(4,9) = 1$
calcolando l'identità di bezout ottengo:
$(1)9 + (-2)4 = 1$
moltiplico per 5:
$(5)9 + (-10)4 = 5$
soluzioni:
$x = x_0 + kb = 5+4k$
$y = y_0 - ak = -10-9k$
da quanto ho trovato come faccio a dire qual è l'inverso di 4?
Allora facciamo un esempio più semplice e adeguato:
$4x -= 5 (mod 9)$
$MCD(4,9) = 1$
calcolando l'identità di bezout ottengo:
$(1)9 + (-2)4 = 1$
moltiplico per 5:
$(5)9 + (-10)4 = 5$
soluzioni:
$x = x_0 + kb = 5+4k$
$y = y_0 - ak = -10-9k$
da quanto ho trovato come faccio a dire qual è l'inverso di 4?
Ricordiamo la definizione di inverso:
Dato $x in ZZ_n$ (tale che $MCD(x,n)=1$, altrimenti l'inverso non esiste), $y in ZZ_n$ è l'inverso di $x$ se e solo se $xy = yx -= 1 " mod " n$.
Ti basta quindi trovare un numero in $ZZ_n$ che moltiplicato per $4$ faccia $1$. Puoi benissimo andare "a tentativi" se $n$ è piccolo, ad esempio qui si vede subito che $4 * 7 = 28 -= 1 " mod " 9$, quindi $4^(-1) = 7$.
Però se i numeri sono più grandi, bezout è la scelta migliore:
partendo dal fatto che hai trovato che $(1)9 + (-2)4 = 1$, se riduci modulo 9 questa equazione ti accorgi che $0 + (-2)4 -= 1 " mod " 9$ e cioò che $(-2)*4 -= 1 " mod " 9$ che è proprio la definizione di inverso, quindi $4^-1 -= -2 -= 7 " mod " 9$.
Ciao!
Ah, nota che se $MCD(x.n) != 1$, fare l'inverso non ha senso, ad esempio in $ZZ_6$ se cercassimo di fare l'inverso di $2$, si vede subito che $2*0 -=0$, $2*1 -= 2$, $2*2 -=4$, $2*3 -= 6 -= 0$, $2*4 -= 8 -= 2$, $2*5 -= 10 -=4$, e quindi non esiste nessun numero tale che $2*y -=1 " mod " 6$.
Quindi nel tuo post iniziale, l'inverso di $18$ in $ZZ_(70)$ non può esistere...
Però prova a fare per esercizio l'inverso di $19$ e di $59$ in $ZZ_(70)$
Dato $x in ZZ_n$ (tale che $MCD(x,n)=1$, altrimenti l'inverso non esiste), $y in ZZ_n$ è l'inverso di $x$ se e solo se $xy = yx -= 1 " mod " n$.
Ti basta quindi trovare un numero in $ZZ_n$ che moltiplicato per $4$ faccia $1$. Puoi benissimo andare "a tentativi" se $n$ è piccolo, ad esempio qui si vede subito che $4 * 7 = 28 -= 1 " mod " 9$, quindi $4^(-1) = 7$.
Però se i numeri sono più grandi, bezout è la scelta migliore:
partendo dal fatto che hai trovato che $(1)9 + (-2)4 = 1$, se riduci modulo 9 questa equazione ti accorgi che $0 + (-2)4 -= 1 " mod " 9$ e cioò che $(-2)*4 -= 1 " mod " 9$ che è proprio la definizione di inverso, quindi $4^-1 -= -2 -= 7 " mod " 9$.
Ciao!
Ah, nota che se $MCD(x.n) != 1$, fare l'inverso non ha senso, ad esempio in $ZZ_6$ se cercassimo di fare l'inverso di $2$, si vede subito che $2*0 -=0$, $2*1 -= 2$, $2*2 -=4$, $2*3 -= 6 -= 0$, $2*4 -= 8 -= 2$, $2*5 -= 10 -=4$, e quindi non esiste nessun numero tale che $2*y -=1 " mod " 6$.
Quindi nel tuo post iniziale, l'inverso di $18$ in $ZZ_(70)$ non può esistere...
Però prova a fare per esercizio l'inverso di $19$ e di $59$ in $ZZ_(70)$
quindi l'inverso di $19$ in $ZZ_70$
$MCD(70,19) = 1$ quindi $19$ è invertibile.
identità di Bezout:
$(3)70 + (-11)19 = 1$
$(-11)19 -= 1 (mod 70)$
$19^(-1) -= -11 -= 59 (mod 70)$
l'inverso di $19$ in $ZZ_70$ è $59$
quindi dalla definizione di inverso data nel post precedente
si ha che l'inverso di $59$ in $ZZ_70$ è $19$.
giusto no?
$MCD(70,19) = 1$ quindi $19$ è invertibile.
identità di Bezout:
$(3)70 + (-11)19 = 1$
$(-11)19 -= 1 (mod 70)$
$19^(-1) -= -11 -= 59 (mod 70)$
l'inverso di $19$ in $ZZ_70$ è $59$
quindi dalla definizione di inverso data nel post precedente
Dato $x in ZZ_n$ (tale che $MCD(x,n)=1$, altrimenti l'inverso non esiste), $y in ZZ_n$ è l'inverso di $x$ se e solo se $xy = yx -= 1 " mod " n$.
si ha che l'inverso di $59$ in $ZZ_70$ è $19$.
giusto no?
ora che vedo meglio sul mio testo non c'è nulla riguardo la definizione di inverso data precedentemente se non la seguente proposizione che penso sia equivalente?
al massimo ho la definizione di invertibile:
Se $ac -= bc (mod n)$ e $MCD(c,n)=1$, allora $a -= b (mod n)$.
al massimo ho la definizione di invertibile:
Un elemento $u \in ZZ$ che divide $1$ si dice unità (o elemento invertibile) di $ZZ$. E' immediato riconoscere che le sole unità di $ZZ$ sono $1$ e $-1$.
Tutto esatto l'esercizio
No, quella che dici tu è la definizione di "elemento invertibile", quella di "se $EE y " t.c. " xy=yx=1 => x^-1 :=y$ è la definizione di "inverso" (ovviamente per esistere l'inverso, l'elemento deve essere invertibile). Dire $MCD(x,n)=1$ garantisce che $x$ è invertibile in $ZZ_n$, ma trovare poi chi sia effettivamente l'inverso bisogna fare i conti...
Comunque se ancora non hai incontrato quella definizione, la incontrerai molto presto appena inizi a studiare i gruppi
No, quella che dici tu è la definizione di "elemento invertibile", quella di "se $EE y " t.c. " xy=yx=1 => x^-1 :=y$ è la definizione di "inverso" (ovviamente per esistere l'inverso, l'elemento deve essere invertibile). Dire $MCD(x,n)=1$ garantisce che $x$ è invertibile in $ZZ_n$, ma trovare poi chi sia effettivamente l'inverso bisogna fare i conti...
Comunque se ancora non hai incontrato quella definizione, la incontrerai molto presto appena inizi a studiare i gruppi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo