Inverso in classe Resto
Salve, qualcuno mi potrebbe spiegare come posso determinare tutti gli elementi invertibili in una classe resto senza effettuare indagini dirette. Ad esempio come determino tutti gli elementi invertibili in Z38?
Grazie
Grazie
Risposte
Senza indagine diretta non so....io intanto partirei dalla funzione di Eulero $\phi(38)$ che mi dice almeno quanti sono gli invertibili, e in fondo anche quali sono, in $ZZ_38$.
HO pensato avesse a che fare con bezout però non ho idea di come andare avanti.
Se è primo, tutti tranne lo zero.
Se non è primo, sono invertibili gli elementi che con esso fanno MCD = 1; quindi ti metti ad escludere tutti i suoi fattori primi e i loro multipli.
Es. $38 = 2*19 -> Z_38° = {1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37}$
Ho escluso l'insieme $D = {2k : k in Z, 2k in Z_38} U {19k : k in Z, 2k in Z_38}$
Inoltre sono sempre sicuro che gli elementi 1 e -1 sono sempre invertibili, mentre lo zero mai.
p.s.: potresti implementare un algoritmo utile su C o C++ che svolga questo lavoro al posto tuo...
Se non è primo, sono invertibili gli elementi che con esso fanno MCD = 1; quindi ti metti ad escludere tutti i suoi fattori primi e i loro multipli.
Es. $38 = 2*19 -> Z_38° = {1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 25, 27, 29, 31, 33, 35, 37}$
Ho escluso l'insieme $D = {2k : k in Z, 2k in Z_38} U {19k : k in Z, 2k in Z_38}$
Inoltre sono sempre sicuro che gli elementi 1 e -1 sono sempre invertibili, mentre lo zero mai.
p.s.: potresti implementare un algoritmo utile su C o C++ che svolga questo lavoro al posto tuo...
"Simonixx":
Se non è primo, sono invertibili gli elementi che con esso fanno MCD = 1;
Corretto. Certo, se avete voglia, potreste provare a dimostrarlo... E' un bell'esercizio.
Proposizione. Sia $ZZ_n ":" = ZZ/(nZZ)$ l'insieme delle classi di resto modulo $n$. Allora $a \in ZZ_n$ è invertibile (rispetto al prodotto!) se e solo se $(a,n)=1$.
Il corollario immediato è che il numero di elementi invertibili in $ZZ_n$ è esattamente $phi(n)$.
Perfetto grazie mille il procedimento è molto semplice 
Invece se io volessi trovare l' inverso di 6 all' interno della classe resto Z19 (prendo questa che è un campo così non sbaglio) che procedimento dovrei usare?
Grazie
Invece se io volessi trovare l' inverso di 6 all' interno della classe resto Z19 (prendo questa che è un campo così non sbaglio) che procedimento dovrei usare?
Grazie
"gabry45":
Perfetto grazie mille il procedimento è molto semplice
Invece se io volessi trovare l' inverso di 6 all' interno della classe resto Z19 (prendo questa che è un campo così non sbaglio) che procedimento dovrei usare?
Grazie
1. Vai a tentativi e speri;
2. Bézout: siccome $(a,n)=1$, esistono $x,y$ interi tali che $ax+ny=1$ e da qui è immediato concludere.
Nel tuo caso, direi che è semplice, tieni presente la tabellina del 6 (in particolare, $6*3=$...)
Grazie mille, ma un metodo meccanico non esiste? Questo mi sembra un po casuale 
Credo di avere trovato. Allora ho preso 12 in Z19 che mi sembra più complesso. Cerco l' inverso di 12 sapendo che:
ax+by=1 cioè che [a]= 1 faccio quindi l' MCD (è invertibile solo se MCD da 1) quindi:
$ 19= 12 +7 $
$12=7+5$
$7=5+2$
$5=2*2 + 1$
$2= 1*2 +0$
$MCD (19,12)=1 $
Ora risalgo l' algoritmo euclideo tramite identità di Bezout:
$ 1= 5- 2*2 $
$ = 5- [7-5] * 2 $
$ = 5- [7-(12-7)] * 2 $
$ = (12-7)- [(19-12)-(12-(19-12)] * 2 $
$ = (12-(19-12))- [(19-12)-(12-(19-12)] * 2 $
$ = 12 (8) - 19 (5) $
Avremo che 12*(8) - 19(5)= 1 quindi l' inverso di 12 in Z19 è 8
Sembra funzioni
Sei io ora volessi calcolare in Z12 quali sono i multipli di 3 senza fare indagine diretta come protrei fare invece? Qualcuno mi da una traccia da seguire?
ax+by=1 cioè che [a]= 1 faccio quindi l' MCD (è invertibile solo se MCD da 1) quindi:
$ 19= 12 +7 $
$12=7+5$
$7=5+2$
$5=2*2 + 1$
$2= 1*2 +0$
$MCD (19,12)=1 $
Ora risalgo l' algoritmo euclideo tramite identità di Bezout:
$ 1= 5- 2*2 $
$ = 5- [7-5] * 2 $
$ = 5- [7-(12-7)] * 2 $
$ = (12-7)- [(19-12)-(12-(19-12)] * 2 $
$ = (12-(19-12))- [(19-12)-(12-(19-12)] * 2 $
$ = 12 (8) - 19 (5) $
Avremo che 12*(8) - 19(5)= 1 quindi l' inverso di 12 in Z19 è 8
Sembra funzioni
Sei io ora volessi calcolare in Z12 quali sono i multipli di 3 senza fare indagine diretta come protrei fare invece? Qualcuno mi da una traccia da seguire?
Alla fine nemmeno questi metodi sono "meccanici", comunque devi svolgere qualcosa...
Che significa multipli di 3 in Z12?
E poi quale Z12 prendi in considerazione? Gruppo additivo o moltiplicativo?
Che significa multipli di 3 in Z12?
E poi quale Z12 prendi in considerazione? Gruppo additivo o moltiplicativo?
Praticamente ho trovato un esercizio che mi chiedeva "Trovare tutti gli elementi di Z12 che sono multipli di 3". Gruppo moltiplicativo. Sinceramente non so bene cosa intenda perchè non riesco proprio a risolvere
Io non sono riuscito a trovare nulla neanche in internet al riguardo, quindi ci provo.
Abbiamo che MCD tra 12 e 3
12= 3*4 + 0
Avremo che (3*4)a + 12b= 0 cioè per tutti i multipli di 12 ricadremo nella classe 0 quindi avremo [a] = 0;
Per quanto riguarda i restanti multipli di tre che non sono divisibili per 12 avremo queste possibilità:
$ 3a + 12b = 6 $
$ 3a + 12b = 3 $
$3a + 12b = 9 $
Visto che $[3]*[4]= 0 $ i resti possibili in $Z12$ per 3 sono quelli minori di 4, quindi (9,6,3).
Queste sono tutte le soluzioni possibili. Dovrebbe essere corretto no?
Abbiamo che MCD tra 12 e 3
12= 3*4 + 0
Avremo che (3*4)a + 12b= 0 cioè per tutti i multipli di 12 ricadremo nella classe 0 quindi avremo [a] = 0;
Per quanto riguarda i restanti multipli di tre che non sono divisibili per 12 avremo queste possibilità:
$ 3a + 12b = 6 $
$ 3a + 12b = 3 $
$3a + 12b = 9 $
Visto che $[3]*[4]= 0 $ i resti possibili in $Z12$ per 3 sono quelli minori di 4, quindi (9,6,3).
Queste sono tutte le soluzioni possibili. Dovrebbe essere corretto no?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo