Spiegazione Esercizio Gruppo

Messaggioda GiovanniMontanaro » 06/11/2019, 22:38

Salve,

Ho iniziato a studiare le Strutture Dati ma non ho la pallida idea di come si svolgano gli esercizi di cui sto trattando la parte teorica.
Gentilmente potreste spiegarmi la risoluzione dell'esercizio in modo che possa prendere spunto e provare a fare altri esercizi simili per conto mio ?? Grazie. [-o<

--------------------------------------------------------------------------------------------------------------------------
L'esercizio è questo, scusatemi se non abbozzo niente, ma non sò nemmeno da dove devo partire. :-k

Nel gruppo ($\Z_15$; +), Determinare l'ordine di tutti gli elementi. Stabilire
quali elementi sono generatori.
GiovanniMontanaro
Starting Member
Starting Member
 
Messaggio: 19 di 44
Iscritto il: 15/11/2017, 19:31

Re: Spiegazione Esercizio Gruppo

Messaggioda gugo82 » 06/11/2019, 22:47

Beh, comincia a fare due conti.

Quali sono gli elementi di $ZZ_(15)$?
Fissato $x in ZZ_(15)$, che cos’è l’ordine di $x$? (Ricorda che sei in un gruppo additivo…)
Come puoi fare a determinare l’ordine di $bar(1)$ e $bar(2)$, ad esempio?
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 22726 di 44916
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: Spiegazione Esercizio Gruppo

Messaggioda luca69 » 13/11/2019, 12:23

Nell'occasione ho ripreso un po' la teoria che porta alla "formula risolvente" $(5)$, che ti serve per il tuo esercizio. Spero di non aver preso abbagli, nel qual caso qualcuno ce lo dirà.
---------------------------------------------------------------------------------------------------------------------------
Dato $n \in ZZ$, definiamo $nZZ:=\{mn, m \in ZZ\}$ l'insieme degli interi multipli di $n$. Dato $a \in ZZ$, diremo che:
$$\mathbb{Z} \ni b \sim a \stackrel{(def.)}{\Longleftrightarrow} b-a \in n\mathbb{Z} \Longleftrightarrow \exists m \in \mathbb{Z} \mid b=a+mn \tag 1$$
La relazione $(1)$ è di equivalenza in $ZZ$. La classe di equivalenza di $a \in ZZ$ è l'insieme:
$$\bar a := \{b \in \mathbb{Z} \mid b \sim a\}= \{a+mn, m \in \mathbb{Z}\} \tag 2$$
Per l'algoritmo euclideo, dato $n$ intero positivo, per ogni $b \in ZZ$ esistono $s \in ZZ$ e $r \in \{0,...,n-1\}$ tali che $b=sn+r$, per cui:
\begin{alignat*}{1}
\bar b &= \{b+mn, m \in \mathbb{Z}\} \\
&=\{(sn+r)+mn, m \in \mathbb{Z}\} \\
&=\{r+(s+m)n, m \in \mathbb{Z}\} \\
&=\{r+tn, t \in \mathbb{Z}\} \\
&=\bar r \\
\tag 3
\end{alignat*}
Pertanto, $ZZ_n:=ZZ//nZZ= \{\bar 0$, ..., $\overline{n-1}\}$.

Ora, tra gli elementi (insiemi!) di $ZZ_n$ definiamo l'operazione "$+$" nel modo seguente:
$$\bar i + \bar j := \overline{i+j} \tag 4$$
(Poiché stiamo definendo un'operazione tra classi mediante dei loro rappresentanti, dobbiamo essere sicuri che il risultato di questa operazione non dipenda dalla scelta dei rappresentanti delle classi-termini. Quindi, vorremmo che $i' \in \bar i, j' \in \bar j \Rightarrow \bar{i'}+\bar{j'}=\overline{i+j}$; ma quest'ultima uguaglianza è vera, perchè $\bar{i'}+\bar{j'}=\overline{i'+j'}$, e $i'+j'$ e $i+j$ hanno lo stesso resto modulo $n$. Quindi $(4)$ è una "buona definizione".)

Ora, $(ZZ_n,+)$ è gruppo con elemento neutro $\bar 0$. L'ordine di $\bar a \in ZZ_n$ è (definizione) il più piccolo intero positivo, $o(\bar a)$, tale che $o(\bar a)\bar a=\bar 0$. Ma per $(4)$, $o(\bar a)\bar a=\overline{o(\bar a)a}$, per cui $o(\bar a)\bar a=\bar 0 \Leftrightarrow \overline{o(\bar a)a}=\bar 0 \Leftrightarrow o(\bar a)a \equiv 0 mod n \Leftrightarrow o(\bar a)a=mn$, per un opportuno $m$. In conclusione, l'ordine di $\bar a$ è il più piccolo intero positivo della forma $n//(a/m)$; quindi, esso si ottiene quando al denominatore c'è il più grande divisore di $a$ che sia anche divisore di $n$, ovvero:

$$o(\bar a)=\frac{n}{MCD(a,n)} \tag 5$$
In particolare, l'ordine di $\bar a$ coincide con l'ordine del gruppo ($n$) non appena $a$ è coprimo con $n$ ($MCD(a,n)=1$); se $n$ è primo, questo accade per ogni $a=1,...,n-1$.

Nel tuo caso, applica la $(5)$ per $n=15$ e $a=1,...,14$.
luca69
Junior Member
Junior Member
 
Messaggio: 105 di 319
Iscritto il: 14/06/2017, 12:44


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite