Relazioni d'equivalenza, classi e compatibilità

[smartmouse]

Per classi dei resti intendi le classi di equivalenza ottenute per [0], [1], [10] e [81], giusto?
Quindi ad esempio una somma da provare potrebbe essere tra due elementi di una classe o tra un elemento di una classe con un elemento di un'altra classe?

Ad esempio, date le classi di equivalenza sopra ricavate:

\( \displaystyle {\left[{0}\right]}_{{9}}={\left\lbrace{0}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{0},{9},-{9},{18},-{18},\ldots\right\rbrace} \)
\( \displaystyle {\left[{1}\right]}_{{9}}={\left\lbrace{1}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{1},{10},-{8},{19},-{17},\ldots\right\rbrace} \)
\( \displaystyle {\left[{10}\right]}_{{9}}={\left\lbrace{10}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{10},{19},{1},{28},-{8},\ldots\right\rbrace} \)
\( \displaystyle {\left[{81}\right]}_{{9}}={\left\lbrace{81}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{81},{90},{72},{99},{63},\ldots\right\rbrace} \)

Delle somme da provare possono essere [9] + [-8] oppure [81] + [-17] ?


Per quanto riguarda il prodotto, partendo da quanto hai detto per l'addizione:

Allora per la somma procedi in questo modo:

\( \displaystyle \forall{\left[{a}\right]},{\left[{b}\right]}\in\mathbb{Z}_{{9}}{\mid}{\left[{a}\right]}+{\left[{b}\right]}={\left[{b}\right]}+{\left[{a}\right]}\in\mathbb{Z}_{{9}} \),

\( \displaystyle {\left({a}+{9}{k}\right)}+{\left({b}+{9}{h}\right)}={\left({a}+{b}\right)}+{9}{\left({k}+{h}\right)}={\left({b}+{a}\right)}+{9}{\left({h}+{k}\right)}\in\mathbb{Z}_{{9}} \)

Dovrebbe essere

\( \displaystyle \forall{\left[{a}\right]},{\left[{b}\right]}\in\mathbb{Z}_{{9}}{\mid}{\left[{a}\right]}\cdot{\left[{b}\right]}={\left[{b}\right]}\cdot{\left[{a}\right]}\in\mathbb{Z}_{{9}} \),

\( \displaystyle {\left({a}+{9}{k}\right)}\cdot{\left({b}+{9}{h}\right)}={\left({b}+{9}{h}\right)}\cdot{\left({a}+{9}{k}\right)}\in\mathbb{Z}_{{9}} \)

Giusto?

[GundamRX91]

Per classi dei resti intendi le classi di equivalenza ottenute per [0], [1], [10] e [81], giusto?

Si.

Quindi ad esempio una somma da provare potrebbe essere tra due elementi di una classe o tra un elemento di una classe con un elemento di un'altra classe?

Ad esempio, date le classi di equivalenza sopra ricavate:

\( \displaystyle {\left[{0}\right]}_{{9}}={\left\lbrace{0}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{0},{9},-{9},{18},-{18},\ldots\right\rbrace} \)
\( \displaystyle {\left[{1}\right]}_{{9}}={\left\lbrace{1}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{1},{10},-{8},{19},-{17},\ldots\right\rbrace} \)
\( \displaystyle {\left[{10}\right]}_{{9}}={\left\lbrace{10}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{10},{19},{1},{28},-{8},\ldots\right\rbrace} \)
\( \displaystyle {\left[{81}\right]}_{{9}}={\left\lbrace{81}+{9}{k}{\mid}{k}\in\mathbb{Z}\right\rbrace}={\left\lbrace{81},{90},{72},{99},{63},\ldots\right\rbrace} \)

Delle somme da provare possono essere [9] + [-8] oppure [81] + [-17] ?

No, la somma la esegui proprio con le classi dei resti/equivalenza:

\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{4}\right]}_{{9}}={\left[{3}+{4}\right]}_{{9}}={\left[{7}\right]}_{{9}} \) e come hai visto \( \displaystyle {\left[{7}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)
\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{7}\right]}_{{9}}={\left[{3}+{7}\right]}_{{9}}={\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)

Mi sai dire perchè \( \displaystyle {\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}} \) ?

Per quanto riguarda il prodotto, partendo da quanto hai detto per l'addizione:

Allora per la somma procedi in questo modo:

\( \displaystyle \forall{\left[{a}\right]},{\left[{b}\right]}\in\mathbb{Z}_{{9}}{\mid}{\left[{a}\right]}+{\left[{b}\right]}={\left[{b}\right]}+{\left[{a}\right]}\in\mathbb{Z}_{{9}} \),

\( \displaystyle {\left({a}+{9}{k}\right)}+{\left({b}+{9}{h}\right)}={\left({a}+{b}\right)}+{9}{\left({k}+{h}\right)}={\left({b}+{a}\right)}+{9}{\left({h}+{k}\right)}\in\mathbb{Z}_{{9}} \)

Dovrebbe essere

\( \displaystyle \forall{\left[{a}\right]},{\left[{b}\right]}\in\mathbb{Z}_{{9}}{\mid}{\left[{a}\right]}\cdot{\left[{b}\right]}={\left[{b}\right]}\cdot{\left[{a}\right]}\in\mathbb{Z}_{{9}} \),

\( \displaystyle {\left({a}+{9}{k}\right)}\cdot{\left({b}+{9}{h}\right)}={\left({b}+{9}{h}\right)}\cdot{\left({a}+{9}{k}\right)}\in\mathbb{Z}_{{9}} \)

Giusto?

\( \displaystyle {\left[{3}\right]}_{{9}}\cdot{\left[{4}\right]}_{{9}}={\left[{3}\cdot{4}\right]}_{{9}}={\left[{12}\right]}_{{9}}={\left[{3}\right]}_{{9}} \)

Però ti deve essere chiara la teoria che ti porta a questo risultato, ok?

[smartmouse]

No, la somma la esegui proprio con le classi dei resti/equivalenza:

\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{4}\right]}_{{9}}={\left[{3}+{4}\right]}_{{9}}={\left[{7}\right]}_{{9}} \) e come hai visto \( \displaystyle {\left[{7}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)
\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{7}\right]}_{{9}}={\left[{3}+{7}\right]}_{{9}}={\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)

E da dove escono 3 e 4 ad esempio? Cosa stai addizionando?

Mi sai dire perchè \( \displaystyle {\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}} \) ?

Perchè gli insieme dei numeri che si ottengono sono uguali, non so perchè, ma provando a calcolarne un pò, alla fine sembra che siano costituiti dagli stessi numeri.

\( \displaystyle {\left[{3}\right]}_{{9}}\cdot{\left[{4}\right]}_{{9}}={\left[{3}\cdot{4}\right]}_{{9}}={\left[{12}\right]}_{{9}}={\left[{3}\right]}_{{9}} \)

Però ti deve essere chiara la teoria che ti porta a questo risultato, ok?

A dire il vero non mi è chiara nemmeno la pratica! 3 e 4 da dove li hai presi?
Mentre la dimostrazione che ho fatto sulla compatibilità del prodotto è corretta?

Grazie per la tua pazienza!

[GundamRX91]

No, la somma la esegui proprio con le classi dei resti/equivalenza:

\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{4}\right]}_{{9}}={\left[{3}+{4}\right]}_{{9}}={\left[{7}\right]}_{{9}} \) e come hai visto \( \displaystyle {\left[{7}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)
\( \displaystyle {\left[{3}\right]}_{{9}}+{\left[{7}\right]}_{{9}}={\left[{3}+{7}\right]}_{{9}}={\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}}\in\mathbb{Z}_{{9}} \)

E da dove escono 3 e 4 ad esempio? Cosa stai addizionando?

Sono due elementi qualsiasi di \( \displaystyle \mathbb{Z}_{{9}} \)

Mi sai dire perchè \( \displaystyle {\left[{10}\right]}_{{9}}={\left[{1}\right]}_{{9}} \) ?

Perchè gli insieme dei numeri che si ottengono sono uguali, non so perchè, ma provando a calcolarne un pò, alla fine sembra che siano costituiti dagli stessi numeri.

\( \displaystyle {\left[{10}\right]}_{{9}}={\left\lbrace{10}+{9}{n}{\mid}{n}\in\mathbb{Z}\right\rbrace}={\left\lbrace{10},{19},{1},{28},-{8},{37},-{17},\ldots\right\rbrace} \)
ma
\( \displaystyle {\left[{1}\right]}_{{9}}={\left\lbrace{1}+{9}{n}{\mid}{n}\in\mathbb{Z}\right\rbrace}={\left\lbrace{1},{10},-{8},{19},-{17},{28},-{26},\ldots\right\rbrace} \)
cioè in pratica hanno gli stessi elementi, quindi sono uguali.

\( \displaystyle {\left[{3}\right]}_{{9}}\cdot{\left[{4}\right]}_{{9}}={\left[{3}\cdot{4}\right]}_{{9}}={\left[{12}\right]}_{{9}}={\left[{3}\right]}_{{9}} \)

Però ti deve essere chiara la teoria che ti porta a questo risultato, ok?

A dire il vero non mi è chiara nemmeno la pratica! 3 e 4 da dove li hai presi?
Mentre la dimostrazione che ho fatto sulla compatibilità del prodotto è corretta?

Si, ma non è completa... devi arrivare ad avere (rappresentare) un intero che è un multiplo di 9.

Grazie per la tua pazienza!

Di nulla, spero solo di esserti davvero d'aiuto

[smartmouse]

Dovrebbe essere

\( \displaystyle \forall{\left[{a}\right]},{\left[{b}\right]}\in\mathbb{Z}_{{9}}{\mid}{\left[{a}\right]}\cdot{\left[{b}\right]}={\left[{b}\right]}\cdot{\left[{a}\right]}\in\mathbb{Z}_{{9}} \),

\( \displaystyle {\left({a}+{9}{k}\right)}\cdot{\left({b}+{9}{h}\right)}={\left({b}+{9}{h}\right)}\cdot{\left({a}+{9}{k}\right)}\in\mathbb{Z}_{{9}} \)

Giusto?

Si, ma non è completa... devi arrivare ad avere (rappresentare) un intero che è un multiplo di 9.

Cioè devo arrivare a:

\( \displaystyle {a}{b}+{9}{k}{b}+{9}{a}{h}+{81}{h}{k}= \)
\( \displaystyle ={a}{b}+{9}{\left({k}{b}+{a}{h}+{9}{h}{k}\right)} \)

E' questo che intendi?

[GundamRX91]

Praticamente si.
Guarda, se fai \( \displaystyle {\left[{3}\right]}_{{9}}\cdot{\left[{7}\right]}_{{9}}={\left[{21}\right]}_{{9}} \), ovvero \( \displaystyle {\left({3}+{9}{h}\right)}\cdot{\left({7}+{9}{k}\right)} \) per \( \displaystyle {h},{k}\in\mathbb{Z} \), da cui \( \displaystyle {21}+{27}{k}+{63}{h}+{81}{h}{k} \).
Ora se poni \( \displaystyle {h}={1} \) e \( \displaystyle {k}={1} \) ottieni \( \displaystyle {21}+{27}+{63}+{81}={192} \), ma se dividi \( \displaystyle {192} \) per \( \displaystyle {9} \) (ricorda che siamo in modulo \( \displaystyle {9} \)),
ottieni:

\( \displaystyle {192}={21}\cdot{9}+{3} \) dove \( \displaystyle {3} \) è il resto e che corrisponde alla classe dei resti \( \displaystyle {\left[{3}\right]}_{{9}} \); infatti \( \displaystyle {\left[{21}\right]}_{{9}}={\left[{3}\right]}_{{9}} \).

[GundamRX91]

Più in generale la relazione di congruenza \( \displaystyle \equiv_{{n}} \) è compatibile con le operazioni di somma e prodotto in \( \displaystyle \mathbb{Z} \); ne consegue che \( \displaystyle {\left(\mathbb{Z}_{{n}},+,\cdot\right)} \) è un anello commutativo unitario.

Siano \( \displaystyle {a}\equiv{{a}}^{'}_{\left(\text{mod}{n}\right)} \) e \( \displaystyle {b}\equiv{{b}}^{'}_{\left(\text{mod}{n}\right)} \). Allora \( \displaystyle {a}+{b}\equiv{{a}}^{'}+{{b}}^{'}_{\left(\text{mod}{n}\right)} \) e \( \displaystyle {a}\cdot{b}\equiv{{a}}^{'}\cdot{{b}}^{'}_{\left(\text{mod}{n}\right)} \).

Se \( \displaystyle {a}\equiv{{a}}^{'}_{\left(\text{mod}{n}\right)}\Rightarrow{n}{\left|{a}-{{a}}^{'}\Rightarrow\exists{h}\in\mathbb{Z}\right|}{a}-{{a}}^{'}={n}\cdot{h} \)
e se \( \displaystyle {b}\equiv{{b}}^{'}_{\left(\text{mod}{n}\right)}\Rightarrow{n}{\left|{b}-{{b}}^{'}\Rightarrow\exists{k}\in\mathbb{Z}\right|}{b}-{{b}}^{'}={n}\cdot{k} \)

Se sommiamo membro a membro otteniamo \( \displaystyle {a}-{{a}}^{'}+{b}-{{b}}^{'}={n}{h}+{n}{k} \) e \( \displaystyle {\left({a}+{b}\right)}-{\left({{a}}^{'}+{{b}}^{'}\right)}={n}{\left({h}+{k}\right)}\Rightarrow{a}+{b}\equiv{{a}}^{'}+{{b}}^{'}_{\left(\text{mod}{n}\right)} \).

Per la moltiplicazione abbiamo:

\( \displaystyle {a}\equiv{{a}}^{'}_{\left(\text{mod}{n}\right)}\Rightarrow{n}{\left|{a}-{{a}}^{'}\Rightarrow\exists{h}\in\mathbb{Z}\right|}{a}-{{a}}^{'}={n}\cdot{h} \)
\( \displaystyle {b}\equiv{{b}}^{'}_{\left(\text{mod}{n}\right)}\Rightarrow{n}{\left|{b}-{{b}}^{'}\Rightarrow\exists{k}\in\mathbb{Z}\right|}{b}-{{b}}^{'}={n}\cdot{k} \)

\( \displaystyle {a}\cdot{b}-{{a}}^{'}\cdot{{b}}^{'}={a}\cdot{b}-{a}\cdot{{b}}^{'}+{a}\cdot{{b}}^{'}-{{a}}^{'}\cdot{{b}}^{'}={a}\cdot{\left({b}-{{b}}^{'}\right)}+{{b}}^{'}\cdot{\left({a}-{{a}}^{'}\right)}={a}{n}{h}+{n}{k}{{b}}^{'}={n}\cdot{\left({a}{h}+{k}{{b}}^{'}\right)} \)
da cui \( \displaystyle {a}\cdot{b}\equiv{{a}}^{'}\cdot{{b}}^{'}_{\left(\text{mod}{n}\right)} \)

[smartmouse]

Praticamente si.
Guarda, se fai \( \displaystyle {\left[{3}\right]}_{{9}}\cdot{\left[{7}\right]}_{{9}}={\left[{21}\right]}_{{9}} \), ovvero \( \displaystyle {\left({3}+{9}{h}\right)}\cdot{\left({7}+{9}{k}\right)} \) per \( \displaystyle {h},{k}\in\mathbb{Z} \), da cui \( \displaystyle {21}+{27}{k}+{63}{h}+{81}{h}{k} \).
Ora se poni \( \displaystyle {h}={1} \) e \( \displaystyle {k}={1} \) ottieni \( \displaystyle {21}+{27}+{63}+{81}={192} \), ma se dividi \( \displaystyle {192} \) per \( \displaystyle {9} \) (ricorda che siamo in modulo \( \displaystyle {9} \)),
ottieni:

\( \displaystyle {192}={21}\cdot{9}+{3} \) dove \( \displaystyle {3} \) è il resto e che corrisponde alla classe dei resti \( \displaystyle {\left[{3}\right]}_{{9}} \); infatti \( \displaystyle {\left[{21}\right]}_{{9}}={\left[{3}\right]}_{{9}} \).

Wow ci sono riuscito allora!
Inoltre, con il tuo controesempio è diventato tutto ancora più chiaro!
Grazie mille!

Peccato per il tuo ultimo post... nel quale non ci ho capito niente! Lo posso trascurare ai fini dell'esercizio?

[GundamRX91]

L'ultimo post è la dimostrazione della compatibilità della relazione di congruenza rispetto l'operazione binaria di somma e prodotto. Direi che è più che fondamentale per risolvere/capire gli esercizi

Comunque mi fa piacere averti in qualche modo aiutato.

[smartmouse]

Ok, grazie ancora.

Scusa se te lo scrivo qua, ma potresti aiutarmi anche con gli altri miei due topic?

Mi riferisco a questo e questo.