Algebra Lineare: dimostrazione relazione di equivalenza con MCD e mcm

[PrInCeSs Of MuSiC]

Ciao a tutti.
Ho un esercizio dato dal professore che recita:
"Consideriamo l'insieme A tutti i numeri naturali minori o uguali di un dato valore N diverso da 0. Per a, b in A poniamo aRb se e solo se a, N hanno lo stesso minimo comune multiplo di b, N. Si provi che R è una relazione di equivalenza. Se ne descrivano le classi per N=10 e per N=12.
Si riesegua lo stesso esercizio con il massimo comune divisore al posto del minimo comune multiplo."

Ora, per il mcm è stato facile, perché mi sono aiutata con N=10 e N=12.

[math]A = {\forall a \in \mathbb{N} : a \leq N, N\neq0}[/math]

[math]a, b \in A aRb \iff mcm(a,N)=mcm(b,N)[/math]

Dunque, per essere uguali occorre che a e b siano frutto della scomposizione di N.

N=10=5*2 --> mcm(2,10)=mcm(5,10)=10
N=12=4*3 --> mcm(4,12)=mcm(3,12)=12

La relazione perché sia di equivalenza, occorre che abbia tre proprietà:

• riflessiva: mcm(a,a)=a --> aRa


• simmetrica: se mcm(a,N)=mcm(b,N) e quindi aRb --> bRa


• transitiva: se mcm(a,N)=mcm(b,N) --> aRb

classe di equivalenza:

[math]a|\mathbb{N}={b \in A:a\leq N, N\neq 0}[/math]

Ora, non riesco a trovare una strada semplice per il MCD.
L'unica cosa che mi è venuta in mente è che i tre numeri siano primi tra loro e quindi il MCD è 1.

Come posso andare avanti?

[carlogiannini]

Se posso permettermi, mi sembra che la parte più difficile, quella concettuale, tu l'abbia già risolta e bene.
Considera che mcm e MCD si calcolano entrambi coi FATTORI COMUNI:
mcm = FATTORI COMUNI e NON COMUNI, presi una sola volta con l'esponente MAGGIORE (e contrariamente a quanto suggerito dal primo termine "minimo" è in realtà un numero "grande")
MCD = solo FATTORI COMUNI, presi una sola volta con l'esponente MINORE (e anche qui la parola "massimo" trae in inganno perché in realtà è un numero piccolo)
Quindi con questa precisazione il ragionamento fatto per il mcm è valido anche per il MCD.
L'unica differenza, ma non è influente nella dimostrazione, sta nel fatto che hai già evidenziato tu cioè che la maggior parte dei MCD saranno uguali a UNO.
In segno di pace,
Carlo

[ce8c0e31f941cc14ed8def9a9c5c3a60a8400d85]

Mostro la risoluzione completa dell'esercizio.

Dato l'insieme

[math]A := \left\{ n \in \mathbb{N} : n \le N\, ; N \ne 0 \right\}[/math]

e dati

[math]a,\,b \in A[/math]

,
poniamo

[math]a\mathfrak{R} b \; \Leftrightarrow \; \text{lcm}(a,\,N) = \text{lcm}(b,\,N)[/math]

. Si provi che

[math]\mathfrak{R}[/math]

è
una relazione di equivalenza e se ne descrivano le classi per

[math]N = 10[/math]

,
per

[math]N = 12\\[/math]

.

i)

[math]\mathfrak{R}[/math]

è riflessiva:
per ogni

[math]a \in A[/math]

si ha

[math]a\mathfrak{R} a[/math]

perché

[math]\small \text{lcm}(a,\,N) = \text{lcm}(a,\,N)\\[/math]

;

ii)

[math]\mathfrak{R}[/math]

è simmetrica:
per ogni

[math]a,\,b \in A[/math]

si ha

[math]a\mathfrak{R} b \; \Rightarrow \; b\mathfrak{R} a[/math]

perché

[math]\small \text{lcm}(a,\,N) = \text{lcm}(b,\,N) \; \Rightarrow \; \text{lcm}(b,\,N) = \text{lcm}(a,\,N)\\[/math]

;

iii)

[math]\mathfrak{R}[/math]

è transitiva:
per ogni

[math]a,\,b,\,c \in A[/math]

si ha

[math]a\mathfrak{R} b \; \land \; b\mathfrak{R} c \; \Rightarrow \; a\mathfrak{R} c[/math]

perché

[math]\small \text{lcm}(a,\,N) = \text{lcm}(b,\,N) = \text{lcm}(c,\,N) \; \Rightarrow \; \text{lcm}(a,\,N) = \text{lcm}(c,\,N)\\[/math]

;

dunque, come volevasi dimostrare,

[math]\mathfrak{R}\\[/math]

è una relazione di equivalenza.

Ora, la classe di equivalenza dell'elemento

[math]a \in A[/math]

è, per definizione:

[math][a]\mathfrak{R} := \left\{ b \in A : a\mathfrak{R} b \right\} = \left\{ b \in A : \text{lcm}(a,\,N) = \text{lcm}(b,\,N) \right\}\\[/math]

.

Quindi, fissato

[math]N = 10[/math]

, per

[math]a = 1,\,2,\,\dots,\, 10[/math]

si ha:

[math]\text{lcm}(1,\,10) = \text{lcm}(2,\,10) = \text{lcm}(5,\,10) = \text{lcm}(10,\,10) = 10[/math]

;

[math]\text{lcm}(3,\,10) = \text{lcm}(6,\,10) = 30[/math]

;

[math]\text{lcm}(4,\,10) = 20[/math]

;

[math]\text{lcm}(7,\,10) = 70[/math]

;

[math]\text{lcm}(8,\,10) = 40[/math]

;

[math]\text{lcm}(9,\,10) = 90[/math]

;

[math]\Rightarrow \; A/\mathfrak{R} = \{\{1,\,2,\,5,\,10\},\,\{3,\,6\},\,\{4\},\,\{7\},\,\{8\},\,\{9\}\}\\[/math]

.

Analogamente, fissato

[math]N = 12[/math]

, per

[math]a = 1,\,2,\,\dots,\, 12[/math]

si ha:

[math]\small \text{lcm}(1,\,12) = \text{lcm}(2,\,12) = \text{lcm}(3,\,12) = \text{lcm}(4,\,12) = \text{lcm}(6,\,12) = \text{lcm}(12,\,12) = 12[/math]

;

[math]\text{lcm}(5,\,12) = \text{lcm}(10,\,12) = 60[/math]

;

[math]\text{lcm}(7,\,12) = 84[/math]

;

[math]\text{lcm}(8,\,12) = 24[/math]

;

[math]\text{lcm}(9,\,12) = 36[/math]

;

[math]\text{lcm}(11,\,12) = 132[/math]

;

[math]\Rightarrow \; A/\mathfrak{R} = \{\{1,\,2,\,3,\,4,\,6,\,12\},\,\{5,\,10\},\,\{7\},\,\{8\},\,\{9\},\,\{11\}\}\\[/math]

.


Sostituendo

[math]\text{lcm}[/math]

con

[math]\text{gcd}[/math]

, la relazione che si ottiene è

[math]\small a\mathfrak{S}b \; \Leftrightarrow \; \text{gcd}(a,\,N) = \text{gcd}(b,\,N)[/math]

ed è ancora una relazione
di equivalenza; la dimostrazione è analoga alla precedente.

Ora, la classe di equivalenza dell'elemento

[math]a \in A[/math]

è, per definizione:

[math][a]\mathfrak{S} := \left\{ b \in A : a\mathfrak{S} b \right\} = \left\{ b \in A : \text{gcd}(a,\,N) = \text{gcd}(b,\,N) \right\}\\[/math]

.

Quindi, fissato

[math]N = 10[/math]

, per

[math]a = 1,\,2,\,\dots,\, 10[/math]

si ha:

[math]\text{gcd}(1,\,10) = \text{gcd}(3,\,10) = \text{gcd}(7,\,10) = \text{gcd}(9,\,10) = 1[/math]

;

[math]\text{gcd}(2,\,10) = \text{gcd}(4,\,10) = \text{gcd}(6,\,10) = \text{gcd}(8,\,10) = 2[/math]

;

[math]\text{gcd}(5,\,10) = 5[/math]

;

[math]\text{gcd}(10,\,10) = 10[/math]

;

[math]\Rightarrow \; A/\mathfrak{S} = \{\{1,\,3,\,7,\,9\},\,\{2,\,4,\,6,\,8\},\,\{5\},\,\{10\}\}\\[/math]

.

Analogamente, fissato

[math]N = 12[/math]

, per

[math]a = 1,\,2,\,\dots,\, 12[/math]

si ha:

[math]\text{gcd}(1,\,12) = \text{gcd}(5,\,12) = \text{gcd}(7,\,12) = \text{gcd}(11,\,12) = 1[/math]

;

[math]\text{gcd}(2,\,12) = \text{gcd}(10,\,12) = 2[/math]

;

[math]\text{gcd}(3,\,12) = \text{gcd}(9,\,12) = 3[/math]

;

[math]\text{gcd}(4,\,12) = \text{gcd}(8,\,12) = 4[/math]

;

[math]\text{gcd}(6,\,12) = 6[/math]

;

[math]\text{gcd}(12,\,12) = 12[/math]

;

[math]\Rightarrow \; A/\mathfrak{S} = \{\{1,\,5,\,7,\,11\},\,\{2,\,10\},\,\{3,\,9\},\,\{4,\,8\},\,\{6\},\,\{12\}\}\\[/math]

.

È tutto. ;)