Editing Euclidean algorithm (section)

=== Worked example ===
[[File:Euclidean algorithm 1071 462.gif|upright|thumb|alt=Animation in which progressively smaller square tiles are added to cover a rectangle completely.|Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions {{math|1=''a'' = 1071}} and {{math|1=''b'' = 462}}. Squares of size {{math|462×462}} are placed within it leaving a {{math|462×147}} rectangle. This rectangle is tiled with {{math|147×147}} squares until a {{math|21×147}} rectangle is left, which in turn is tiled with {{math|21×21}} squares, leaving no uncovered area. The smallest square size, {{math|21}}, is the GCD of {{math|1071}} and {{math|462}}.]]

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of {{math|1=''a'' = 1071}} and {{math|1=''b'' = 462}}. To begin, multiples of {{math|462}} are subtracted from {{math|1071}} until the remainder is less than {{math|462}}. Two such multiples can be subtracted ({{math|1=''q''<sub>0</sub> = 2}}), leaving a remainder of {{math|147}}:
: {{math|1=1071 = 2 × 462 + 147}}.

Then multiples of {{math|147}} are subtracted from {{math|462}} until the remainder is less than {{math|147}}. Three multiples can be subtracted ({{math|1=''q''<sub>1</sub> = 3}}), leaving a remainder of {{math|21}}:
: {{math|1=462 = 3 × 147 + 21}}.

Then multiples of {{math|21}} are subtracted from {{math|147}} until the remainder is less than {{math|21}}. Seven multiples can be subtracted ({{math|1=''q''<sub>2</sub> = 7}}), leaving no remainder:
: {{math|1=147 = 7 × 21 + 0}}.

Since the last remainder is zero, the algorithm ends with {{math|21}} as the greatest common divisor of {{math|1071}} and {{math|462}}. This agrees with the {{math|gcd(1071, 462)}} found by prime factorization [[#Background: greatest common divisor|above]]. In tabular form, the steps are:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
|-
!Step ''k''!!Equation!!Quotient and remainder
|-
| 0 || {{math|1=1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub>}} || {{math|1=''q''<sub>0</sub> = 2}} and {{math|1=''r''<sub>0</sub> = 147}}
|-
| 1 || {{math|1=462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub>}} || {{math|1=''q''<sub>1</sub> = 3}} and {{math|1=''r''<sub>1</sub> = 21}}
|-
| 2 || {{math|1=147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub>}} || {{math|1=''q''<sub>2</sub> = 7}} and {{math|1=''r''<sub>2</sub> = 0}}; algorithm ends
|}