Two unequal numbers being set out, and the less being continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, the original numbers will be prime to one another.
Proof
Suppose for contradiction some number d>1 measures both inputs.
At each subtraction step the divisor and remainder differ from the
previous pair by a common multiple of d; so d persists through
the algorithm and ultimately measures the unit, which is impossible.