(MCD) massimo comun divisore

Può essere definito su un anello commutativo arbitrario.

Sia $A$ è un anello commutativo e $a,b,d\in A$.

$$d=\text{MCD}(a,b)⟺\{\begin{array}{l}d>0,\\ d\mid a\text{e}d\mid b,\\ \forall x\in A,(x\mid a\wedge x\mid b)\Rightarrow x\mid d\end{array}$$

oppure

$$d=\text{MCD(a, b)}⟺d=\max (\{x\in \mathbb{Z}:x\mid a\wedge x\mid b\})$$

Osservazioni:

• $\text{MCD}(ua,ub)=u\cdot \text{MCD}(a,b)$;
• $\text{MCD}\left(\frac{a}{\text{MCD}\left(a,b\right)},\frac{b}{\text{MCD}(a,b)}\right)=1⟹$ i due numeri sono coprimi;
• $a\mathbb{Z}+b\mathbb{Z}=\text{MCD}(a,b)\mathbb{Z}$ (lemma 3 dei sottogruppi additivi).

Unicità del MCD

• Avendo un anello commutativo $A$, con $a,b\in A$, supponiamo per assurdo che ci sia più di un MCD tra $a$ e $b$. Chiamiamoli $d_1$ e $d_2$.
• Applicando la definizione di massimo comun divisore su $d_1$ e considerando $d_2$ come un semplice divisore di $a$ e $b$, poi facendo l’opposto per $d_2$, otteniamo che $d_1\mid d_2\wedge d_2\mid d_1⟹d_1=d_2$ per l’antisimmetria della relazione ”$x$ divide $y$” su ${\mathbb{R}}^{\star }$.
• Ciò contraddice l’assurdo, dimostrando che l’MCD è unico.

Algoritmo della divisione euclidea per il calcolo dell’MCD

L’algoritmo della divisione euclidea permette di calcolare l’MCD senza scomporre in primi i due numeri.

Siano $a,b\in \mathbb{Z}-\{0\}$

Si inizia con $b_0=b$, gli indici servono perché il processo è iterativo.

• $a=q_0{b}_0+r_{0}0\le r\le |b|-1$
• $b_0=q_1{r}_0+r_{1}0\le r_1\le r_0-1$
• $b_1=q_2{r}_1+r_{2}0\le r_2\le r_1-1$
• $\dots$
• $b_n=q_{n+1}{r}_n+r_{n+1}=r_{n-1}0\le r_{n+1}\le r_n-1$

$r_{n-1}=\text{MCD}(a,b)$

Ci si ferma all’ultimo resto non nullo.

Esempio: $a=3522,b=321$

1. $3522=10\cdot 321+312$
2. $321=1\cdot 312+9$
3. $312=34\cdot 9+6$
4. $9=1\cdot 6+\boxed{3}$

$\text{MCD}(3522,321)=3$

Seguendo i passi dell’algoritmo a ritroso e sostituendo come sotto, si può trovare l’identità di Bézout per $a=3522$ e $b=321$:

• $3=9-\boxed{6}\cdot 1$
• $\boxed{6}=312-\boxed{9}\cdot 34$
• $\boxed{9}=321-\boxed{312}\cdot 1$
• $\boxed{312}=3522-321\cdot 10$

$$3=9-\boxed{312-\boxed{321-\boxed{3522-321\cdot 10}\cdot 1}\cdot 34}\cdot 1=-36\cdot 3522+395\cdot 321$$

Esercizio

Dimostra che $\text{MCD}(ab,c)\mid (\text{MCD}(a,c)\cdot \text{MCD}(b,c))$.

Questa dimostrazione si basa sul teorema fondamentale dell’aritmetica.

$a$ e $b$ possono avere tutti o solo alcuni fattori primi in comune, quindi la dimostrazione si biforca in due situazioni.

1. Se $a$ e $b$ hanno tutti i fattori in comune, per l’unicità della scomposizione, $a=b$; quindi bisogna dimostrare che $\text{MCD}(a^2,c)\mid {\text{MCD}(a,c)}^2$.
   1. È evidente che $a^2$ ha solo fattori in comune con $a$, pertanto $\text{MCD}(a^2,c)=\text{MCD}(a,c)$.
   2. È evidente che $\text{MCD}(a,c)$ ha solo fattori in comune con ${\text{MCD}(a,c)}^2$, pertanto $\text{MCD}(a^2,c)\mid {\text{MCD}(a,c)}^2$.
2. Se $a$ e $b$ non hanno tutti i fattori in comune, vuol dire che esistono o più fattori $x_a$ di $a$ oppure uno o più fattori $x_b$ di $b$ tali che $x_b\nmid a$ oppure $x_a\nmid b$. Assumiamo senza perdita di generalità che, se esistono, $x_a\mid c$ e $x_b\mid c$ (se invece $x_a\nmid c$ o $x_b\nmid c$, $\text{MCD}(ab,c)$ sarebbe uguale a $\text{MCD}(a,c)$ o $\text{MCD}(b,c)$: in questo caso la dimostrazione è immediata).
3. Per definizione, $\text{MCD}(ab,c)$ è composto solo dai fattori comuni tra $ab$ e $c$, cioè da quelli di $a,b,c$, dato che $ab$ è composto solo dai fattori $a$ e $b$. Se $x_a$ (come definito nel punto precedente) esistesse, non sarebbe un fattore di $\text{MCD}(ab,c)$. Lo stesso si può dire si $x_b$. Invece $\exists x_a⟹x_a\mid \text{MCD}(a,c)⟹x_a\mid \text{MCD}(a,c)\cdot \text{MCD}(b,c)$, analogamente $\exists x_b⟹x_b\mid \text{MCD}(b,c)⟹x_b\mid \text{MCD}(a,c)\cdot \text{MCD}(b,c)$.
4. Per i punti 2 e 3, vale che $\text{MCD}(a,c)\cdot \text{MCD}(b,c)=x_a\cdot \text{MCD}(ab,c)$ oppure $\text{MCD}(a,c)\cdot \text{MCD}(b,c)=x_b\cdot \text{MCD}(ab,c)$, quindi $\text{MCD}(ab,c)\mid (\text{MCD}(a,c)\cdot \text{MCD}(b,c))$.

$\square$