...inverso moltiplicativo...
Buongiorno a tutti.
Ho un problema nel calcolare l'inverso moltiplicativo di $34$ $mod55$.
Suggerimenti?
Ho un problema nel calcolare l'inverso moltiplicativo di $34$ $mod55$.
Suggerimenti?
Risposte
Prima di tutto vedi se è effetivamente invertibile; lo è poichè 34 e 55 sono primi tra loro.
Io farei così: vedrei quali sono gli elementi inveribili di $Z_55$; in sostanza sono invertibili solo le classi i cui rappresentanti cono coprimi con 55; quindi nel tuo caso devi togliere i rappresentanti : 0, i multipli di 5 e 11;
Poi gli altri saranno invertibili.
Adesso prendi ognuno di essi e moltiplicali per la classe il cui rappresentante è 34; se il risultato sarà 1 hai trovato l'inverso.
Io farei così: vedrei quali sono gli elementi inveribili di $Z_55$; in sostanza sono invertibili solo le classi i cui rappresentanti cono coprimi con 55; quindi nel tuo caso devi togliere i rappresentanti : 0, i multipli di 5 e 11;
Poi gli altri saranno invertibili.
Adesso prendi ognuno di essi e moltiplicali per la classe il cui rappresentante è 34; se il risultato sarà 1 hai trovato l'inverso.
Nota che ogni equazione alle congruenze della forma
[tex]ax\equiv m \mod n\;\;\;a,x,m,n\in\mathbb{Z}[/tex]
può essere scritta nella forma equivalente di equazione diofantea come
[tex]ax-ny=m[/tex]
che si risolve per opportuni [tex]x,y\in\mathbb{Z}[/tex]. Le soluzioni della congruenza saranno date limitatamente dalla [tex]x[/tex].
[tex]ax\equiv m \mod n\;\;\;a,x,m,n\in\mathbb{Z}[/tex]
può essere scritta nella forma equivalente di equazione diofantea come
[tex]ax-ny=m[/tex]
che si risolve per opportuni [tex]x,y\in\mathbb{Z}[/tex]. Le soluzioni della congruenza saranno date limitatamente dalla [tex]x[/tex].
Semplifichiamo un po' il suggerimento di biggest usando semplicemente le tabelline (che credo note a tutti... Sempre che alle elementari le insegnino ancora! 
) 
Se [tex]$34\ x\equiv 1 \mod 55$[/tex], allora [tex]$34\ x$[/tex] è un numero che differisce da un multiplo di [tex]$55$[/tex] per una unità; dato che i multipli di [tex]$55$[/tex] hanno cifra finale [tex]$0$[/tex] oppure [tex]$5$[/tex], il nostro [tex]$34\ x$[/tex] ha come cifra finale o [tex]$1$[/tex] oppure [tex]$6$[/tex]; nessun numero moltiplicato per [tex]$34$[/tex] dà come risultato un numero con cifra finale [tex]$1$[/tex], ergo il nostro [tex]$34\ x$[/tex] deve avere [tex]$6$[/tex] come ultima cifra; gli unici numeri che moltiplicati per [tex]$34$[/tex] danno come risultato un numero con cifra finale [tex]$6$[/tex] sono quelli che hanno come cifra finale [tex]$4$[/tex] o [tex]$9$[/tex].
Conseguentemente i possibili candidati ad essere l'inverso di [tex]$34$[/tex] in [tex]$\mathbb{Z}_{55}$[/tex] sono:
[tex]$4$[/tex], [tex]$9$[/tex], [tex]$14$[/tex], [tex]$19$[/tex], [tex]$24$[/tex], [tex]$29$[/tex], [tex]$34$[/tex], [tex]$39$[/tex], [tex]$44$[/tex], [tex]$49$[/tex],
considerevolmente meno di tutti gli elementi di [tex]$\mathbb{Z}_{55}^\star$[/tex] (che sono [tex]$\phi (55)=\phi (5)\ \phi(11)=4\ 10=40$[/tex]!).
) Se [tex]$34\ x\equiv 1 \mod 55$[/tex], allora [tex]$34\ x$[/tex] è un numero che differisce da un multiplo di [tex]$55$[/tex] per una unità; dato che i multipli di [tex]$55$[/tex] hanno cifra finale [tex]$0$[/tex] oppure [tex]$5$[/tex], il nostro [tex]$34\ x$[/tex] ha come cifra finale o [tex]$1$[/tex] oppure [tex]$6$[/tex]; nessun numero moltiplicato per [tex]$34$[/tex] dà come risultato un numero con cifra finale [tex]$1$[/tex], ergo il nostro [tex]$34\ x$[/tex] deve avere [tex]$6$[/tex] come ultima cifra; gli unici numeri che moltiplicati per [tex]$34$[/tex] danno come risultato un numero con cifra finale [tex]$6$[/tex] sono quelli che hanno come cifra finale [tex]$4$[/tex] o [tex]$9$[/tex].
Conseguentemente i possibili candidati ad essere l'inverso di [tex]$34$[/tex] in [tex]$\mathbb{Z}_{55}$[/tex] sono:
[tex]$4$[/tex], [tex]$9$[/tex], [tex]$14$[/tex], [tex]$19$[/tex], [tex]$24$[/tex], [tex]$29$[/tex], [tex]$34$[/tex], [tex]$39$[/tex], [tex]$44$[/tex], [tex]$49$[/tex],
considerevolmente meno di tutti gli elementi di [tex]$\mathbb{Z}_{55}^\star$[/tex] (che sono [tex]$\phi (55)=\phi (5)\ \phi(11)=4\ 10=40$[/tex]!).
gugo 82 davvero bella considerazione...mi ha colpito molto...complimenti...io uso questi ragionamenti nel calcolo delle potenze ma in questo caso non ci avevo pensato...ottima intuizione...
Come ti hanno fatto notare l'inverso moltiplicativo di $34x-=1_mod_55$ lo ottieni in questo modo:
sai che $55|34x-1$ e cioè $34x-1=55k$ (con $k in ZZ$) da cui $34x-55k=1$.
Tu sai che il $MCD(55,34)=1$ e cioè $34$ e $55$ sono coprimi, ma se lo calcoli (il $MCD$) ottieni anche la "struttura" per risolvere l'equazione $34x-55k=1$.
Con l'algoritmo derivato da Euclide, con metodo delle divisioni successive, calcoli il $MCD$ ottenendo i resti delle varie divisioni da cui a ritroso calcoli il valore della $x$ e di $k$:
$55 = 34*1 + 21$ ; $21 = 55 - 34*1$
$34 = 21*1 + 13$ ; $12 = 34 - 21*1$
$21 = 13*1 + 8$ ; $8 = 21 - 13*1$
$13 = 8*1 + 5$ ; $5 = 13 - 8*1$
$8 = 5*1 + 3$ ; $3 = 8 - 5*1$
$5 = 3*1 + 2$ ; $2 = 5 - 3*1$
$3 = 2*1 + 1$ ; $1 = 3 - 2*1$
$2 = 1*2 + 0$ (questa non la consideri perchè il resto è zero)
ora parti dal penultimo resto, cioè $1 = 3 - 2*1$, che puoi anche scrivere come $1 = 3*1 - 2*1$ a cui sostituisci il valore di $2$ con il resto $2 = 5 - 3*1$, e avrai che $1 = 3*1 - (5*1 - 3*1)*1 = 3*1 - 5*1 +3*1 = 3*2 - 5*1$; ora sostituisci il $3$ con $3 = 8 - 5*1$ e procedi in questo modo sino ad arrivare ad ottenere quanto richiesto.
Dovresti arrivare ad ottenere il seguente risultato $1 = 55*13 - 34*21$
sai che $55|34x-1$ e cioè $34x-1=55k$ (con $k in ZZ$) da cui $34x-55k=1$.
Tu sai che il $MCD(55,34)=1$ e cioè $34$ e $55$ sono coprimi, ma se lo calcoli (il $MCD$) ottieni anche la "struttura" per risolvere l'equazione $34x-55k=1$.
Con l'algoritmo derivato da Euclide, con metodo delle divisioni successive, calcoli il $MCD$ ottenendo i resti delle varie divisioni da cui a ritroso calcoli il valore della $x$ e di $k$:
$55 = 34*1 + 21$ ; $21 = 55 - 34*1$
$34 = 21*1 + 13$ ; $12 = 34 - 21*1$
$21 = 13*1 + 8$ ; $8 = 21 - 13*1$
$13 = 8*1 + 5$ ; $5 = 13 - 8*1$
$8 = 5*1 + 3$ ; $3 = 8 - 5*1$
$5 = 3*1 + 2$ ; $2 = 5 - 3*1$
$3 = 2*1 + 1$ ; $1 = 3 - 2*1$
$2 = 1*2 + 0$ (questa non la consideri perchè il resto è zero)
ora parti dal penultimo resto, cioè $1 = 3 - 2*1$, che puoi anche scrivere come $1 = 3*1 - 2*1$ a cui sostituisci il valore di $2$ con il resto $2 = 5 - 3*1$, e avrai che $1 = 3*1 - (5*1 - 3*1)*1 = 3*1 - 5*1 +3*1 = 3*2 - 5*1$; ora sostituisci il $3$ con $3 = 8 - 5*1$ e procedi in questo modo sino ad arrivare ad ottenere quanto richiesto.
Dovresti arrivare ad ottenere il seguente risultato $1 = 55*13 - 34*21$
@GundamRX91: Il che significa che [tex]$-21$[/tex] è il reciproco di [tex]$34$[/tex] in [tex]$\mathbb{Z}_{55}$[/tex], però ciò non contrasta con quanto detto più sopra: infatti è evidente che [tex]$-21\equiv 34 \mod 55$[/tex], ergo [tex]$34^{-1}=34$[/tex].
Si, si certo, infatti sono assolutamente equivalenti 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo