Euclidean algorithm (turning phase division)

Euclidean algorithm: GCD (a, b) = GCD (B, R), where r = a mod B

How to understand this algorithm is correct.

Set D₁For any common divisor of a and B, that is d₁|a，d₁|b ，Because r = a mod B, D can be obtained.₁|r

Therefore, any common divisor of a and B is also the common divisor of B and R, that is, the common divisor sets of them are the same.

So GCD (a, b) = GCD (B, a%b).