Greatest common divisor calculator

Greatest common divisor calculator Introduction

2, the definition of the greatest common divisor: for two integers a and b (not both 0), if there is an integer c such that both a and b are divisible by c, then c is the common divisor of a and b. Of all common divisor numbers, the largest one is called the greatest common divisor.

3. Properties of the greatest common divisor:

(1), the greatest common divisor of any two integers is unique.

(2) If a is a multiple of b, then the greatest common divisor of A and b is b.

(3), the greatest common divisor of two mutual prime numbers is 1.

(4), the greatest common divisor is not less than 1, and not greater than the smaller of the two numbers.

4, the greatest common divisor calculation method:

(1), prime factorization method: decompose each number into the product of prime factors, and then take the prime factors common to all numbers (each prime factor takes the least number of occurrences), and finally multiply these prime factors to get the greatest common divisor.

(2), Euclidean algorithm: This is a more efficient method based on the fact that the greatest common divisor of two positive integers a and b (a>b) is equal to the remainder of a divided by b, c and b. The result can be obtained quickly by recursion or loop calculation.