MCD online: l'Algoritmo di Euclide
Come calcolare l'MCD con l'algoritmo di Euclide
Siano \(a\) e \(b\) due interi, con \(0 \leq b < a\).
- Se \(b=0\) allora \(MCD(a,b) = 0\).
- Se \(b \neq 0\) allora procedi nello svolgimento delle seguenti divisioni succesive:
\begin{array} {ll}
a = bq_1 + r_1 & r_1 \neq 0 \\
b = r_1q_2 + r_2 & r_2 \neq 0 \\
r_1 = r_2q_3 + r_3 & r_3 \neq 0 \\
\,\,\,\,\,\,\,\,\,\,\,\,\,\ \vdots & \,\,\,\,\,\,\ \vdots \\
r_{k-3} = r_{k-2}q_{k-1} + r_{k-1} & r_{k-1} \neq 0 \\
r_{k-2} = r_{k-1}q_k & \\
\end{array}
Risultato: \(MCD(a,b) = r_{k-1}\), (se \(r_1 = 0 ,\ MCD(a,b) = b\))
Tool online per trovare l'MCD tra due interi con l'algoritmo di Euclide
Inserisci due interi maggiori di zero per calcolare \(MCD(a,b)\) (\(GCD(a,b)\) in inglese).
Example
Supponiamo di dover calcolare \(MCD(165,102)\). Svolgiamo le divisioni successive:
\begin{array} {ll}
165=102\cdot1+63\\
102=63\cdot1+39\\
63=39\cdot1+24\\
39=24\cdot1+15\\
24=15\cdot1+9\\
15=9\cdot1+6\\
9=6\cdot1+3\\
6=3\cdot2+0\\
\end{array}
Risultato: \( MCD(165,102)=3 \)
