Spiegazione Esercizio Gruppo

[montanaro.giovanni]

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.

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

Nel gruppo ($\Z_15$; +), Determinare l'ordine di tutti gli elementi. Stabilire
quali elementi sono generatori.

[gugo82]

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?

[luca691]

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$.