The greatest common divisor
You have a floor 48 cm by 18 cm and want square tiles that fit exactly, with no cutting. The biggest tile that works is 6 cm, and that 6 is the greatest common divisor of 48 and 18: the largest number that divides both.
Trying every size from the smaller number downwards works, but for numbers near a trillion it is hopeless.
Greatest common divisor: is the biggest number that divides both.
gcd(48, 18)
48
018
112
26
30
4ab
a = 48, b = 18. 48 % 18 = 12.
Move 1 of 4
Swap in the remainder
Euclid's trick: lay 18 cm tiles along the 48 cm side. Two fit and 12 cm is left over. Anything that fits both 48 and 18 must also fit that leftover 12, so the question shrinks to 18 and 12. Then 12 and 6, then 6 and 0.
When the second number reaches 0, the first one is the answer.
Replace the pair: with the second number and the remainder, until the second is 0.
Update both at once: save the remainder before you overwrite the first number.
while b != 0:
a, b = b, a % b
return a