Factorization

Finding the common divisor. It is widely used in Cryptography.

Euclidean Algorithm:  recursively modularing until remainder is zero.

Proof: A=x0*B+r0; B = x1*r0+r1; r0 = x2*r1+r2; r1=x3*r2+r3;

if r3 = 0, r1 is multiple of r2, r0 is multiple of r2, B is multiple of r2, A is multiple or r2, therefore r2 is the common divisor.