GCD Calculator: Euclidean Algorithm
How to calculate GCD with Euclidean algorithm
\(a\) and \(b\) are two integers, with \(0 \leq b < a\).
- if \(b=0\) then \(GCD(a,b) = 0\).
- if \(b \neq 0\) then you can do the following successive divisions:
\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}
Result: \(GCD(a,b) = r_{k-1}\), (if \(r_1 = 0 ,\ GCD(a,b) = b\))
Online tool to find the GCD of two integers with the Euclidean algorithm
Enter two integers greater than zero to calculate \(GCD(a,b)\).
Example
Assuming we must calculate \(GCD(165,102)\), we carry out the successive divisions:
\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}
Result: \( GCD(165,102)=3 \)
