The greatest common divisor (gcd) of two positive integers is the largest integer that divides both without remainder.

Euclid's algorithm is based on the following property: if p>q then the gcd of p and q is the same as the gcd of p%q and q.

p%q is the remainder of p which cannot be divided by q, e.g. 33 % 5 is 3.

This is based on the fact that the gcd of p and q also must divided (p-q) or (p-2q) or (p-3q). Therefore you can subtract the maximum of a multitude q from p which is p%q.