0
<
b
≤
a
0 < b \leq a
a
=
q
0
b
+
r
0
a = q_0 b + r_0
q
0
q_0
:
r
0
<
b
r_0 < b
:
b
=
q
1
r
0
+
r
1
b = q_1 r_0 + r_1
a
=
q
0
b
+
r
0
b
=
q
1
r
0
+
r
1
r
0
=
q
2
r
1
+
r
2
r
1
=
q
3
r
2
+
r
3
⋮
=
⋮
r
N
-
1
=
q
N
+
1
r
N
+
r
N
+
1
r
N
≠
0
=
r
N
+
1
\begin{aligned} a &= q_0 b + r_0 \\ b &= q_1 r_0 + r_1 \\ r_0 &= q_2 r_1 + r_2 \\ r_1 &= q_3 r_2 + r_3 \\ \vdots &= \vdots \\ r_{N-1} &= q_{N+1} r_N + r_{N+1} \\ & r_{N} \neq 0 = r_{N+1} \end{aligned}