To find common Divisor for any 2 number

There is a method commonly known for finding the greatest common divisor between any 2 number. It work like this:

75=36*2+3,

36=3*12

So 3 is greatest common divisor of 75 and 36.

Why does this work?

We could see 75=(3*12)*2+3=3*(12*2+1)

Suppose for any two different number, X and Y.

X=Y*M1+R1

Then repeat the process:

Y=R1*M2+R2, or X=(R1*M2+R2)*M1+R1=R1*M1*M2+R2*MI+R1

If R1=0 then the process is completed, we have Y=R1*M1*M2+R1=R1*(M1*M2+1), R1 is the common divisor for X and Y; If not,

R1=R2*M3+R3 or
X=(R2*M3+R3)*M1*M2+R2*MI+(R2*M3+R3)=R2*M1*M2*M3+R3*M1*M2+R2*MI
=R2*(M1*M2*M3+M1)+R3*M1*M2

If R3=0 then the process is completed, we have Y=R2*(M1*M2*M3+M1), R2 is the common divisor for X and Y; If not, we can continue the process indefinitely. Notice that the last term in the right will disappear eventually.

In layperson’s language, we first found out the remainder of the greater number divided by smaller number, then use the remainder to test whether the smaller number is a multiple of the remainder. If it is the case, then the common divisor is the remainder itself. If not, then we test the remainder of the smaller number as divided by the remainder in the last operation. If it is the case, then the common divisor is the remainder in this operation. So the idea is to keep looking for the common divisor in the remainder term until we found it.