Euclidean division, also called Euclidean algorithm, is an algorithm to find the greatest common factor of two positive integers. It is the oldest known algorithm and can be traced back to 3000 years ago. With a simple idea, let two numbers be A and b (b < a), and the steps to find their greatest common divisors (A and B) are as follows: A is divided by B to get a = bq...r 1 (0 ≤ r). If r 1=0, then (a, b) = b; If r 1≠0, then divide by r 1 to get b = r 1q...r2 (0 ≤ R2). If R2 = 0, then (a, b) = r 1, if r2≠0. Its last nonzero remainder is (a, b). Principle and its detailed proof Before introducing this method, let's explain some characteristics of divisibility (all the numbers below are positive integers, so I won't repeat them). We can give the definition of divisibility as follows: for two natural numbers A and B, if there is a positive integer Q that makes a=bq, A can be divisible by B, B is a factor of A, A is a multiple of B, if A can be divisible by C, then C is a common factor of A and B ... From this, we can draw the following inference: inference 1, if A can be divisible by B, Ka can also be divisible by B (ka=kqb). Inference 2: If A can be divisible by C (a=hc) and B can also be divisible by C (b=tc), then (A B) can also be divisible by C because: add two expressions: a+b=hc+tc=(h+t)c and subtract two. Then a=b because: a=qb b=ta a=qta qt= 1 because q and t are positive integers, t=q= 1. So: a=b is used to calculate the greatest common factor of two numbers, which is especially useful when the value is very large, and it is also very simple to apply it to computer programs. The theory is as follows: if q and r are the quotient and remainder of m divided by n, that is, m=nq+r, then gcd(m, n)=gcd(n, r). The proof is as follows: Let a=gcd(m, n) and b=gcd(n, r) prove that ∵a is the greatest common divisor of m, n, ∴m can be divisible by A, and ∴ m-qn can also be divisible by A from the inference 1. Similarly, ∫b is the greatest common divisor of n and r, ∴n can be divisible by b, and r can also be divisible by b, ∴ that is, b is the greatest common divisor of m and n (note: it is not the greatest common divisor yet) ∫a is the greatest common divisor of m and n, and b is the greatest common divisor of m and n ∴ b ≤ For example, calculate gcd (546,429 429) GCD (546 546,429) 546 =1* 429+117 = gcd (429,117) 426. 78) 117 =1* 78+39 = gcd (78,39) 78 = 2 * 39 = 39 [Edit this paragraph] The natural language description of computer algorithm is to determine the greatest common factor of two positive integers A and B by using the following properties:/kloc-. Another way to write it is: 1. A present b, where r is the remainder (0 ≤ r < b); If r = 0, the algorithm ends; The answer is B. 2. Exchange: Set a←b, b←r, and return to the first step. Flowchart Flowchart Pseudocode This algorithm can be written recursively: function GCD (a, b) {IF B