# GCD Calculator: Euclidean Algorithm

## How to calculate GCD with Euclidean algorithm

$$a$$ and $$b$$ are two integers, with $$0 \leq b < a$$.

1. if $$b=0$$ then $$GCD(a,b) = 0$$.
2. 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$$