Euclidean algorithm, also known as division by turns, refers to the greatest common divisor used to calculate two non-negative integers A and B. gfa has two application fields: mathematics and computer. The calculation formula gcd(a, b) = gcd(b, a mod b).

Euclidean algorithm and extended Euclidean algorithm can be implemented in many programming languages.

Euclid algorithm is used to find the greatest common divisor of two positive integers. Euclid, an ancient Greek mathematician, first described this algorithm in his book Elements, so he named it Euclid algorithm.

The extended Euclidean algorithm can be used in RSA encryption and other fields. ?

If you need to ask for the greatest common divisor of two positive integers 1997 and 6 15, use Euclidean algorithm, as follows:

1997 ÷ 6 15 = 3 (remainder 152)

6 15 ÷ 152 = 4 (remainder 7)

152 ÷ 7 = 2 1 (remaining 5)

7 ÷ 5 = 1 (remainder 2)

5 ÷ 2 = 2 (remainder 1)

2 ÷ 1 = 2 (remainder is 0)

So far, the greatest common divisor is 1.

Repeatedly divide by divisor and remainder. When the remainder is 0, taking the divisor of the current formula as the greatest common divisor, the greatest common divisor of 1997 and 6 15 can be obtained.

Commutative division uses the following properties to determine the greatest common factor of two positive integers a and b:

1. If R is the remainder of A÷band R is not 0, then

gcd(a，b) = gcd(b，r)

The greatest common factor of a and its multiple is a.

Another way to write it is:

1. let r be a/b, and the remainder (0≤r

If r= 0, the algorithm ends; The answer is B.

Exchange: Set a←b, b←r, and return to the first step.