Esercizi su Gruppi, Anelli & CO

[MatematiNO]

Ciao a tutti, l'esame di Matematica Discreta si avvicina e purtroppo continuo ad avere dubbi esistenziali!!
Mi scuso in anticipo per la quantità di esercizi che propongo e se impiego più del tempo a capirli ma sono uno studente lavoratore e purtroppo in questo semestre, causa orari di lavoro che coincidono con le lezioni, non riesco a frequentare e sono costretto a studiare tramite le dispense del corso (che non sono fatte dal mio prof. quindi molte volte deviano da quello che lui propone sul portale) e ciò che trovo su internet.
Detto ciò espongo i miei dubbi:
ESERCIZIO 1



Sugli appunti del mio prof. non spiega cos'è o come svolgerlo. Cercando su internet ho trovato che bisogna decomporla in cicli (e l'ho fatto perché era anche il punto a) dell'esercizio) e poi moltiplicare la decomposizione per se stessa MA... non riesco a capire come si svolge la moltiplicazione
Quindi vi chiedo... come si svolge?

ESERCIZIO 2



Anche qui, appunti del prof inesistenti e su internet non riesco a trovare niente di concreto.
Credo che bisogna utilizzare Il teorema di Eulero/Fermat ma non so bene come .
Inoltre, domanda stupida.... vedo comparire spesso in questi esercizi proposti il segno "___" che c'è sul 39 ma nelle dispense del prof. non compare mai quindi mi chiedo...cosa vuol dire?

ESERCIZIO 3



Per il punto b) ho fatto questo:



Però non riesco a concludere l'esercizio perché:
1) La soluzione suggerisce:



Non riesco a capire da dove deriva $578 = 24 * 24 + 2$ nè il $31^2$ nè il $961 = 45 * 21 + 16$. Cosa mi sono perso?

2) Applicando Il Teorema di Fermat ottengo gli elementi invertibili (tipo il 24) che posso poi utilizzare nel punto c) ?

Punto c : confusione totale, non so come procedere con un anello prodotto R x S.

ESERCIZIO 4



Stesso problema, sugli appunti da giusto la definizione di zero-divisore ma nessun esempio quindi non so come procedere per la verifica.
Per determinare invece il numero di elementi invertibili mi verrebbe da verificare gli [a]n tali che $MCD (a,n)=1$ ma anche qui, l'anello prodotto mi blocca e non so come procedere

[spugna2]

"MatematiNO":
ESERCIZIO 1



Sugli appunti del mio prof. non spiega cos'è o come svolgerlo. Cercando su internet ho trovato che bisogna decomporla in cicli (e l'ho fatto perché era anche il punto a) dell'esercizio) e poi moltiplicare la decomposizione per se stessa MA... non riesco a capire come si svolge la moltiplicazione
Quindi vi chiedo... come si svolge?

Due modi:

1) Trovi direttamente la decomposizione in cicli di $\sigma^2$, quindi ad esempio parti da $1$ e trovi:

$\sigma^2(1)=\sigma(\sigma(1))=\sigma(6)=4$
$\sigma^2(4)=\sigma(\sigma(4))=\sigma(2)=3$

e così via finché non ottieni di nuovo $1$, e così facendo troverai che un ciclo di $\sigma^2$ è $(14362)$; con un ragionamento analogo si vede che gli altri tre numeri sono punti fissi.

2) La decomposizione in cicli di $\sigma$ è $(16423)(78)$, e per elevarla al quadrato basta elevare al quadrato i singoli cicli: il primo diventa $(14362)$ (parti da un numero a caso e ne scrivi uno ogni due che incontri nel ciclo di partenza, eventualmente ripartendo da capo; nota che, così facendo, i cicli di ordine dispari rimangono tali e quelli di ordine pari "si spezzano in due"), mentre $(78)$ diventa $(7)(8)$, cioè due cicli banali che puoi evitare di scrivere (in generale i cicli di ordine $2$ scambiano due elementi, e scambiarli due volte è come non fare nulla).

Ricapitolando, $\sigma^2=(14362)$

"MatematiNO":ESERCIZIO 2



Anche qui, appunti del prof inesistenti e su internet non riesco a trovare niente di concreto.
Credo che bisogna utilizzare Il teorema di Eulero/Fermat ma non so bene come .
Inoltre, domanda stupida.... vedo comparire spesso in questi esercizi proposti il segno "___" che c'è sul 39 ma nelle dispense del prof. non compare mai quindi mi chiedo...cosa vuol dire?

b) Detto diversamente, devi calcolare $5011^{803} \mod 1000$: per prima cosa puoi ridurre $5011$ modulo $1000$, ottenendo così $11^{803}$: ora il teorema di Eulero ti dice che $11^{\phi(1000)} \mod 1000=1$ (perché $11$ e $1000$ sono coprimi), ma $\phi(1000)=400$, quindi $11^{803}=11^{400+400+3}=11^{400} * 11^{400} * 11^3 -= 1*1*1331 -= 331$, dove "$-=$" indica la congruenza modulo $1000$ (più brevemente, puoi sostituire $803$ con il suo resto modulo $400$, che è $3$).

c) Innanzitutto tieni presente che gli elementi di $ZZ_{67}$ non sono numeri, ma classi di equivalenza di numeri: in questo caso, due numeri interi sono considerati equivalenti se la loro differenza è un multiplo di $67$, e con $\overline{39}$ si indica semplicemente la classe di equivalenza contenente il numero $39$. Detto questo, vogliamo risolvere $\overline{39} * \overline{x}=\overline{1}$, che è come dire $39x -= 1 (\mod 67)$, che a sua volta equivale a $39x+67y=1$, che ammette soluzioni in quanto $39$ e $67$ sono coprimi (nota che le soluzioni sono infinite, ma la classe di equivalenza $\overline{x}$ è univocamente determinata), e per trovarne una puoi usare il metodo delle divisioni successive:

$67=1*39+28$
$39=1*28+11$
$28=2*11+6$
$11=2*6-1$ (oppure $1*6+5$, ma così fai prima)

$1=2*6-11=2(28-2*11)-11=2*28-5*11=2*28-5(39-28)=7*28-5*39=7(67-39)-5*39=7*67-12*39$

Si trova quindi la soluzione $x=-12$, quindi l'inverso cercato è semplicemente la classe $\overline{-12}$, o se preferisci $\overline{-12+67}=\overline{55}$.

"MatematiNO":ESERCIZIO 3



Per il punto b) ho fatto questo:



Però non riesco a concludere l'esercizio perché:
1) La soluzione suggerisce:



Non riesco a capire da dove deriva $578 = 24 * 24 + 2$ nè il $31^2$ nè il $961 = 45 * 21 + 16$. Cosa mi sono perso?

2) Applicando Il Teorema di Fermat ottengo gli elementi invertibili (tipo il 24) che posso poi utilizzare nel punto c) ?

b) è identico all'esercizio 2, quindi se hai capito quello sai fare anche questo: in particolare, tieni presente che, sempre per il teorema di Eulero, puoi sostituire l'esponente con il suo resto modulo $\phi(n)$, quindi in questo caso bisogna dividere $578$ per $24$, e si ottiene appunto $578=24*24+2$, ma l'unica cosa che ti interessa è che il resto è $2$, cioè che il risultato è $31^2=961$, ma per concludere devi trovare il suo resto nella divisione per $45$, e $961=21*45+16$ ti dice proprio che il resto è $16$.

"MatematiNO":ESERCIZIO 4



Stesso problema, sugli appunti da giusto la definizione di zero-divisore ma nessun esempio quindi non so come procedere per la verifica.
Per determinare invece il numero di elementi invertibili mi verrebbe da verificare gli [a]n tali che $MCD (a,n)=1$ ma anche qui, l'anello prodotto mi blocca e non so come procedere

c) Non avere fretta, basta riflettere un attimo sulla definizione di prodotto tra anelli: in generale hai a che fare con delle coppie $(a,b)$, e il prodotto è $(a,b)*(c,d)=(ac,bd)$, quindi dire che $(a,b)$ è un divisore di zero è come dire che esistono $c$ e $d$ appartenenti ai rispettivi anelli e non entrambi nulli tali che $ac=0$ e $bd=0$ (la condizione di invertibilità è analoga). Possono esserti utili i seguenti fatti:

- In un prodotto di anelli, un elemento è invertibile se e solo se lo sono tutte le sue componenti, ed è un divisore di $0$ se e solo se lo è almeno una delle sue componenti;

- $ZZ_{45} \times ZZ_{43}$ è isomorfo a $ZZ_5 \times ZZ_9 \times ZZ_{43}$.

[MatematiNO]

"spugna":

b) Detto diversamente, devi calcolare $5011^{803} \mod 1000$: per prima cosa puoi ridurre $5011$ modulo $1000$, ottenendo così $11^{803}$: ora il teorema di Eulero ti dice che $11^{\phi(1000)} \mod 1000=1$ (perché $11$ e $1000$ sono coprimi), ma $\phi(1000)=400$, quindi $11^{803}=11^{400+400+3}=11^{400} * 11^{400} * 11^3 -= 1*1*1331 -= 331$, dove "$-=$" indica la congruenza modulo $1000$ (più brevemente, puoi sostituire $803$ con il suo resto modulo $400$, che è $3$).

Non riesco a capire:

1) come si riduce, $5011$ modulo $1000$ per ottenere $11^{803}$

2)perché prendiamo in considerazione $11^{\phi(1000)}$ e non $11^{\phi(803)}$ ?

3) Fin qui $11^{803}=11^{400+400+3}=11^{400} * 11^{400} * 11^3$ ok... ma poi perché è $= 1*1*1331 -= 331$ ?? da dove derivano $1$ e $331$ ??

Secondo

"spugna":

$\overline{-12+67}=\overline{55}$.

Non ho capito solo questa parte!

Terzo

"spugna":
b) è identico all'esercizio 2

Commento dopo aver capito l'esercizio 2

[spugna2]

"MatematiNO":
Non riesco a capire:

1) come si riduce, $5011$ modulo $1000$ per ottenere $11^{803}$

2)perché prendiamo in considerazione $11^{\phi(1000)}$ e non $11^{\phi(803)}$ ?

3) Fin qui $11^{803}=11^{400+400+3}=11^{400} * 11^{400} * 11^3$ ok... ma poi perché è $= 1*1*1331 -= 331$ ?? da dove derivano $1$ e $331$ ??

1) Intendevo dire che $5011-=11 (mod 1000)$, e di conseguenza $5011^{803}-=11^{803} (mod 1000)$.

2) Perché il teorema di Eulero suggerisce di fare così. Sappiamo che se $a$ e $n$ sono coprimi, si ha $a^{phi(n)}-=1 (mod n)$: nel tuo caso $a=11$ e $n=1000$, da cui $11^{phi(1000)}-=1 (mod 1000)$.

3) Si tratta semplicemente di sostituire ogni fattore con il suo resto modulo $1000$: abbiamo appena visto che $11^{400}$ si può sostituire con $1$, mentre $1331$ diventa $331$.

"MatematiNO":Secondo

[quote="spugna"]

$\overline{-12+67}=\overline{55}$.

Non ho capito solo questa parte!

[/quote]

Ricorda che stai lavorando con le classi di resto modulo $67$, quindi puoi aggiungere o togliere multipli di $67$ a tuo piacimento: in poche parole, il numero cambia, ma la classe di equivalenza (che è ciò che ti viene chiesto dal problema) è sempre la stessa.