preface

Euclid’s algorithm, also known as division, is used to calculate the greatest common divisor of two non-negative integers A and B

For the problem of calculating the greatest common divisor, one violent way to think about it is to iterate over every number from 1 to min(a,b), determine whether it is the common divisor of a and b in turn, and record a maximum value globally. Its time complexity is O(n).

background

Euclid’s algorithm can correctly calculate the greatest common divisor of A and B in a relatively short time, which first appeared in Euclid’s Original Geometry

The formula for

GCD (a,b) = GCD (b,a mod b),a >= b

GCD is short for Greatest Common Divisor

This algorithm iteratively computes B, A mod B as a new A, B continuously

All the way to the point where b is 0, where a is the greatest common divisor

The sample

Let’s give an example: find the greatest common divisor of 25,10

According to Euclid’s algorithm, the following steps are required:

  1. 25/10 = 2… 5 the GCD (25, 10) = GCD (10, 5)
  2. 10/5 = 2… The GCD (10, 5) = GCD (5, 0)
  3. In this case, b is 0, so the greatest common divisor between 25 and 10 is 5

5 is indeed the greatest common divisor of 25 and 10, no problem

And it can quickly converge to the case of b equals zero and end the calculation, with very low time complexity

According to the proof, it takes no more than five times the number of decimal places

The principle of

The algorithm seems simple, with only a one-line formula. The following article will introduce its principle and prove its correctness, because the learning algorithm not only needs to know the process of the algorithm, but also need to know why it is correct

The following proof process does not use complex mathematical formula, as easy as possible to understand

A lemma

There is a basic lemma in number theory:

If d is divisible into a, and d is divisible into b, then d is divisible into ax + by, where x and y are integer coefficients on a and b

If both a and b are integer multiples of D, then any combination of a and b is also an integer multiple of D

If a = md,b = nd, then (ax + by) = (am + bn)d, since a,m,b,n are all integers, so am + bn is also an integer, so this lemma holds

This lemma is so important that the correctness of the following proof depends on this lemma!

The same group of several

Let’s prove that all the common divisor of (a,b) and all the common divisor of (b,a mod b) are the same set of numbers


According to the lemma, d can be divisible into A-cb (coefficient 1,-c respectively).

Now let’s look at (b,a mod b) : a mod b can be viewed as a minus (a goes into b) times b, and a goes into b so let’s substitute c

So a mod b can be written as a minus cb, so b, a mod b can be written as b, a minus CB.

For any common divisor of (a, b) :

  • It must be divisible into b: by definition
  • It must also be divisible into a minus CB: from the lemma

So it must also be a common divisor of (b, a mod b)


Let’s go the other way. For any common divisor d of (b, a mod b), the properties of common divisor show that d is both a divisor of B and a minus cb. So d is divisible into B, and d is divisible into A minus CB

According to the lemma, d can be divisible into CB + a-cb (here take the coefficient of B as c and the coefficient of a – cb as 1) = a

For any common divisor of (b, a mod b) :

  • It must be divisible into b: by the common divisor definition
  • It must be divisible into a: from the lemma

So it must also be a common divisor of (a, b)


Based on the above two conclusions:

  1. For any common divisor of (a, b), it must also be a common divisor of (b, a mod b)
  2. For any common divisor of (b, a mod b), it must also be a common divisor of (a, b)

It follows that all the common divisor of (a,b) and all the common divisor of (b,a mod b) are the same set of numbers

Why is that? If it’s not the same set of numbers, then there must be some numbers that are unique to (a, b), or (b, a mod b), in either case, which would violate conclusion 1 or conclusion 2, and therefore be the same set of numbers

The greatest common divisor

Now that the common divisor is the same, the largest common divisor must be the same, so:

The greatest common divisor of (a,b) is the same as the greatest common divisor of (b,a mod b)

At the end of the iteration

This iteration will not go on forever and will soon encounter a situation where B is zero:

(b1, 0), b1 is an integer greater than 0

So the greatest common divisor of the original number, (a, b), is the same thing as the greatest common divisor of (b1, 0)

So what’s the greatest common divisor of b1, 0?

So this is equal to b1, because b1 goes into b1, and b1 goes into 0, so b1 is a common divisor of b1, 0. Is that the biggest?

And the answer is yes, because you can’t have anything larger than b1 as a common divisor, so b1 is the greatest common divisor of b1, 0, and a, b

Code sample

The code is very simple

private int gcd(int a,int b) {

    return b == 0 ? a : gcd(b,a % b);

}
Copy the code

conclusion

This paper introduces the realization of Euclidean algorithm, a classical algorithm for calculating the greatest common divisor of two numbers, and proves its correctness