Esistenza e unicità del Massimo Comune Divisore

Teorema

Siano $n, m \in N$ con $n, m$ non entrambi nulli. Diremo che $d \in N, d \geq 1$ è $Massimo Comune Divisore (M.C.D) di n, m$ se:

$d | m \land d | n$
$c | m \land c | n ⟹ c | d$ per qualche $c \in N$

Inoltre, $\exists x, y \in Z : d = x n + y m$ , ovvero $d$ è esprimibile come combinazione lineare di $n, m$ con $x, y$ .
Se $\exists MCD$ tra $n, m$ , è unico e lo indicheremo con $(n, m) .$

Dimostrazione

Unicità

Poniamo esistano $d_{1}, d_{2}$ entrambi MCD di $n, m$ . Applicando la proprietà (1) di $d_{1}$ e la (2) di $d_{2}$ otteniamo:

$(1) d_{1} | m \land d_{1} | n$
$(2) dato c = d_{1,} d_{1} | m \land d_{1} | n ⟹ d_{1} | d_{2}$

Applicando l'inverso otteniamo che $d_{2} | d_{1} \land d_{1} | d_{2} ⟹ d_{1} = \pm d_{2}$ .
Essendo $d_{1}, d_{2} \in N$ , otteniamo che $d_{1} = d_{2}$ .

Esistenza

Sia $S := {s \in Z | s > 0, x n + y m per qualche x, y \in Z}$ .
Osserviamo che $S \neq \emptyset$ , in quanto se $x = n$ e $y = m$ otteniamo $s = n n + m m > 0 ⟹ n n + m m \in S$ .
Grazie al teorema di buon ordinamento dei numeri naturali, $S$ ammette un minimo $d$ , cioè $d := min S$ . Proviamo che d soddisfa le proprietà 1 e 2.

Verifichiamo che vale 2.
Se $c | n$ e $c | m$ allora $n = c k$ e $m = c h$ , quindi $d = n x + m x = c k x + c h y = c (k x + h y)$ , ossia $c | d . (LEMMA UTILE)$

Verifichiamo che d soddisfa la proprietà 1, ovvero $d | n$ e $d | m$ . Dimostriamo che $d | n .$
Eseguiamo la divisione di $n$ per $d$ , ottenendo il quoziente $q$ e il resto $r$ .

{\begin{cases} n = q d + r \\ 0 \leq r < d \end{cases}

Rimane da provare che $r = 0$ . Supponiamo che $r > 0$ . Osserviamo che:

\begin{aligned} 0 < r & = n - q d \\ = n - q (x n + y m) \\ = n - q x n - q y m \\ = n (1 - q x) + (- q y) m \end{aligned}

\begin{array}{r} ⟹ r \in S, r < d = m i n (S) \\ IMPOSSIBILE ⟹ r = 0 ovvero d | n \end{array}

Analogalmente si dimostra che $d | m$ .