The division of phase and phase, also called Euclid algorithm, was put forward by the Greek mathematician Euclid in his book Elements of Geometry around 300 BC. In this way, the greatest common factor of two natural numbers, namely HCF or gcd, can be found quickly. The so-called greatest common factor refers to the greatest factor among several numbers. For example, the greatest common factor of 8 and 12 is 4, and gcd(8, 12)=4. Before introducing this method, let's explain some characteristics of divisibility. Note that the numbers in the following text are positive integers and will not be repeated in the future. We can give the definition of divisibility as follows: for two natural numbers A and B, if there is a positive integer Q, A = we call b | a, which is a factor of A, and A is a multiple of B, then if c | a and c | b, then C is the common factor of A and B, from which we can draw the following inference: Inference 1: If a | b, if K is. Because a | b knows that ha=b, so (hk). That is a | kb. Inference 2: If a | b and a | c, then a | (b c). Because from a | b and a | c, we can know that ha=b and KA = C. If we add them together, we can get (h+k)a=b+c, that is, a | (b+c). In the same way. Then a = B. Because we can know that HA = B and A = KB from a | b and b | a, A = K (HA) and HK = 1. Because both H and K are positive integers, h=k= 1, so A = B. Calculate the greatest common factor of two numbers by division. It is especially useful when the numerical value is very large, and it is also very simple to apply 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). So a | (m-nq) (derived from inference 1 and inference 2), that is, a | r and a | n, so a | b is also b | r and b | n, so b | (nq+r), that is, b | m and b | n, so b | a. Because a | b. r)。 For example, to calculate GCD (546,429), since 546 =1(429)+117,429 = 3 (117)+78,/kloc.