Finding GCD using the Euclidean algorithm and using prime factorization. Euclid's algorithm

Euclid's algorithm

Greatest common divisor

Consider the following problem: you need to write a program to determine the greatest common divisor (GCD) of two natural numbers.

Let's remember mathematics. The greatest common divisor of two natural numbers is the largest natural number by which they are evenly divisible. For example, the numbers 12 and 18 have common factors: 2, 3, 6. The greatest common factor is the number 6. This is written like this:

GCD(12, 18) = 6.

Let us denote the initial data as M u N. The problem statement is as follows:
Given: M, N
Find: GCD(M, N).

IN in this case no additional mathematical formalization is required. The formulation of the problem itself is of a formal mathematical nature. There is no formula for calculating GCD(M, N) from the values ​​of M and N. But quite a long time ago, long before the advent of computers, an algorithmic method for solving this problem was known. It's called Euclidean algorithm .

The idea of ​​the Euclidean algorithm

The idea of ​​this algorithm is based on the property that if M>N, then

GCD(M, N) = GCD(M - N, N).

In other words, the gcd of two natural numbers is equal to the gcd of their positive difference (the modulus of their difference) and the smaller number.

It's easy to prove this property. Let K be the common divisor of M u N (M> N). This means that M = mK, N = nK, where m, n - integers, and m > n. Then M - N = K(m - n), which means that K is a divisor of the number M - N. This means that all common divisors of the numbers M and N are divisors of their difference M - N, including the greatest common divisor.

The second obvious property:

GCD(M, M) = M.

For "manual" counting, the Euclidean algorithm looks like this:

1) if the numbers are equal, then take any of them as the answer, otherwise continue executing the algorithm;

2) replace the larger number with the difference between the larger and smaller numbers;

3) return to step 1.

Let's consider this algorithm using the example of M=32, N=24:

The structure of the algorithm is a while-loop with nested branching. The cycle is repeated until the values ​​of M and N are equal to each other. In branching, the larger of the two values ​​is replaced by their difference.

Now look at the trace table of the algorithm for the initial values ​​M = 32, N = 24.

In the end, the result was correct.

Program in AY and Pascal

Let's write the algorithm in AY and the program in Pascal.

Questions and tasks

1. Run the Evklid program on your computer. Test it on the values ​​M = 32, N = 24; M = 696, N = 234.

2. Write a program to find the greatest common divisor of three numbers using the following formula:

GCD(A, B, C) = GCD(GCD(A, B), C).

3. Write a program to find the least common multiple (LCM) of two numbers using the formula:

A × B = GCD(A, B) × GCD(A, B).

Let's consider two main methods for finding GCD in two main ways: using the Euclidean algorithm and by decomposing into prime factors. Let's apply both methods for two, three and more numbers.

Euclidean algorithm for finding GCD

The Euclidean algorithm makes it easy to calculate the greatest common factor of two positive numbers. We presented the formulations and proof of the Euclid algorithm in the section “Greatest common divisor: determinant, examples.”

The essence of the algorithm is to sequentially carry out division with a remainder, during which a series of equalities of the form are obtained:

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

We can finish division when r k + 1 = 0, wherein r k = gcd (a , b).

Example 1

64 And 48 .

Solution

Let's introduce the following notations: a = 64, b = 48.

Based on the Euclidean algorithm, we will carry out division 64 on 48 .

We get 1 and the remainder 16. It turns out that q 1 = 1, r 1 = 16.

The second step is to divide 48 by 16, we get 3. That is q 2 = 3, A r 2 = 0 . Thus, the number 16 is the greatest common divisor for the numbers from the condition.

Answer: GCD (64, 48) = 16.

Example 2

What is the GCD of numbers? 111 And 432 ?

Solution

We divide 432 on 111 . According to the Euclidean algorithm, we obtain the chain of equalities 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Thus, the greatest common divisor of numbers is 111 And 432 – this is 3.

Answer: GCD (111, 432) = 3.

Example 3

Find the greatest common divisor of the numbers 661 and 113.

Solution

Let's sequentially divide the numbers and get GCD (661 , 113) = 1 . This means that 661 and 113 are relatively prime numbers. We could figure this out before starting the calculation if we consulted a table of prime numbers.

Answer: GCD (661, 113) = 1.

Finding GCD by factoring numbers into prime factors

In order to find the greatest common divisor of two numbers using the factorization method, it is necessary to multiply all the prime factors that are obtained by factoring these two numbers and are common to them.

Example 4

If we factor the numbers 220 and 600 into prime factors, we get two products: 220 = 2 2 5 11 And 600 = 2 2 2 3 5 5. The common factors in these two products are 2, 2 and 5. This means that GCD (220, 600) = 2 2 5 = 20.

Example 5

Find the greatest common divisor of numbers 72 And 96 .

Solution

Find all prime factors of numbers 72 And 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

The common prime factors for two numbers are 2, 2, 2 and 3. This means that GCD (72, 96) = 2 2 2 3 = 24.

Answer: GCD (72, 96) = 24.

The rule for finding the greatest common divisor of two numbers is based on the properties of the greatest common divisor, according to which gcd (m a 1, m b 1) = m gcd (a 1, b 1), where m is any positive integer.

Finding the gcd of three or more numbers

Regardless of the number of numbers for which we need to find the GCD, we will follow the same algorithm, which consists of sequentially finding the GCD of two numbers. This algorithm is based on the application of the following theorem: GCD of several numbers a 1 , a 2 , … , a k equal to the number dk, which is found by sequentially calculating the gcd (a 1 , a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .

Example 6

Find the greatest common divisor of four numbers 78, 294, 570 and 36 .

Solution

Let us introduce the notation: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Let's start by finding the gcd of numbers 78 and 294: d 2 = GCD (78 , 294) = 6 .

Now let's start finding d 3 = GCD (d 2 , a 3) = GCD (6, 570). According to the Euclid algorithm 570 = 6 95. It means that d 3 = GCD (6 , 570) = 6 .

Let's find d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 divisible by 6 without remainder. This allows us to get d 4 = GCD (6 , 36) = 6 .

d4 = 6, that is, GCD (78 , 294 , 570 , 36) = 6 .

Answer:

Now let's look at another way to calculate GCD for those and more numbers. We can find the gcd by multiplying all the common prime factors of numbers.

Example 7

Calculate the GCD of the numbers 78, 294, 570 and 36 .

Solution

Let's decompose these numbers into prime factors: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.

For all four numbers, the common prime factors will be the numbers 2 and 3.

It turns out that GCD (78, 294, 570, 36) = 2 3 = 6.

Answer: GCD (78, 294, 570, 36) = 6.

Finding GCD of Negative Numbers

If we have to deal with negative numbers, then we can use the moduli of these numbers to find the greatest common divisor. We can do this, knowing the property of numbers with opposite signs: numbers n And - n have the same divisors.

Example 8

Find the gcd of negative integers − 231 And − 140 .

Solution

To perform calculations, we take the modules of the numbers given in the condition. These will be the numbers 231 and 140. Let's write it down briefly: GCD (− 231 , − 140) = GCD (231, 140) . Now we apply the Euclidean algorithm to find prime factors of two numbers: 231 = 140 · 1 + 91 ; 140 = 91 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 1 + 7 and 42 = 7 6. We get that GCD (231, 140) = 7 .

And since GCD (− 231 , − 140) = GCD (231 , 140) , then gcd of numbers − 231 And − 140 equals 7 .

Answer: GCD (− 231, − 140) = 7.

Example 9

Determine the gcd of three numbers − 585, 81 and − 189 .

Solution

We will replace negative numbers in the given list into their absolute values, we obtain GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Then we factor all these numbers into prime factors: 585 = 3 3 5 13, 81 = 3 3 3 3 and 189 = 3 3 3 7. Common to the three numbers are the prime factors 3 and 3. It turns out that GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.

Answer: GCD (− 585, 81, − 189) = 9.

If you notice an error in the text, please highlight it and press Ctrl+Enter

Euclid's algorithm is an algorithm for finding the greatest common divisor (GCD) of a pair of integers.

Greatest Common Divisor (GCD) is a number that divides two numbers without a remainder and is itself divisible without a remainder by any other divisor of the given two numbers. Simply put, this is the most big number, by which two numbers for which the gcd is being sought can be divided without a remainder.

Algorithm for finding GCD by division

1. Divide the larger number by the smaller number.
2. If it is divided without a remainder, then the smaller number is GCD (you should exit the cycle).
3. If there is a remainder, then replace the larger number with the remainder of the division.
4. Let's move on to point 1.

Example:
Find gcd for 30 and 18.
30 / 18 = 1 (remainder 12)
18 / 12 = 1 (remainder 6)
12 / 6 = 2 (remainder 0)
End: GCD is a divisor of 6.
GCD(30, 18) = 6

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

In the loop, the remainder of the division is written to the variable a or b. The loop ends when at least one of the variables is zero. This means that the other one contains a gcd. However, we don’t know which one exactly. Therefore, for GCD we find the sum of these variables. Since one of the variables is zero, it has no effect on the result.

Algorithm for finding GCD by subtraction

1. Subtract the smaller number from the larger number.
2. If the result is 0, it means that the numbers are equal to each other and are GCD (you should exit the loop).
3. If the result of subtraction is not equal to 0, then replace the larger number with the result of the subtraction.
4. Let's move on to point 1.

Example:
Find gcd for 30 and 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
End: GCD is a minuend or subtrahend.
GCD(30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

The greatest common dividing line of two regional numbers $a$ and $b$ - $GCD(a, b)$ - is the largest number , on some number $a$ and $b$ are divided without remainder.

To find $GCD(a, b)$ you can proceed in the following natural way: decompose both numbers la by powers of prime numbers: $a = 2^(\alpha_1) \cdot 3^(\alpha_2) \cdot \ldots \cdot p^(\alpha_n)_n$ , $b = 2 ^(\beta_1) \cdot 3^(\beta_2) \cdot \ldots \cdot p^(\beta_n)_n$ , ($\alpha_k$ and $\beta_k$ can be equal to zero).

Then $$GCD(a, b) = 2^(\min(\alpha_1, \beta_1)) \cdot 3^(\min(\alpha_2, \beta_2)) \cdot \ldots \cdot p^(\ min(\alpha_n, \beta_n))_n.$$ For example, to find the most common value of $2625$ and $8100 $ we get: $2625 = 2^0 \cdot 3^1 \cdot 5^3 \cdot 7^1, 8100 = 2^2 \cdot 3^4 \cdot 5^2 \cdot 7^0$, means $GCD(2625, 8100) = 2^0 \cdot 3^1 \cdot 5^2 \cdot 7^0 = 75$.

The essential drawback of this method is that dividing a large number into simple multiplicities is not so simple. a hundred, or rather, not so fast.

Euclid in the 7th book “Beginning” describes the al-go-rhythm of the “common measure of two numbers”. Al-go-rhythm is described by geo-met-ri-che-ski, as the similarity of the common measure of two cuts. It boils down to the “follow-up from-the-nation” from the greater-from-the-smaller-from-the-cut. Now this al-go-rhythm from the walls is like the al-go-rhythm of Ev-kli-da for finding the most common de-li-those -for two on-tural numbers.

The basic idea on which the al-go-rhythm is based is that $GCD$ numbers $a$ and $b$ are equal $ GCD$ chi-sel $b$ and $a-b$. From here it follows that if you add $a$ to $b$ with the remainder, i.e. represented in the form $a = b \cdot q + r$, then $GCD(a, b) = GCD(b, r)$.

We will describe the beautiful geo-met-ri-che-skaya in-ter-pre-ta-tion of al-go-rit-ma, inter-active-tiv-naya re-a-li-za -tion of something in front of-the-same-higher.

In a straight-corner with long sides $a$ and $b$ for the largest possible square . In the remaining straight-coal, we again take the maximum possible square.

The Al-go-rhythm of the Ev-kli-da is a powerful tool, used in solving various personal problems. dacha For example, it is used to solve equations in whole numbers, presenting numbers in the form of constant -breaking (chain) fractions, it can be generalized to find the most common de-li-the two many- go-member-nov.

Literature

Euclid. Na-cha-la Ev-kli-da. Books VII, X. - M.-L.: GITTL, 1950.

R. Ku-rant, G. Robins. What is this ma-te-ma-ti-ka? - M.: MTsNMO, 2010.

Euclidean algorithm for finding GCD (greatest common divisor)

Given two non-negative integers and . It is required to find their greatest common divisor, i.e. the largest number that is a divisor of both , and . On English language"greatest common divisor" is written "greatest common divisor", and its common designation is:

(here the symbol "" denotes divisibility, i.e. "" denotes "divides")

When one of the numbers is equal to zero, and the other is different from zero, their greatest common divisor, according to definition, will be this second number. When both numbers are equal to zero, the result is undefined (any infinitely large number will do), we set the greatest common divisor to zero in this case. Therefore, we can talk about the following rule: if one of the numbers is equal to zero, then their greatest common divisor is equal to the second number.

Euclid's algorithm, discussed below, solves the problem of finding the greatest common divisor of two numbers and for .

This algorithm was first described in Euclid's Elements (circa 300 BC), although it is quite possible that this algorithm has earlier origins.

Algorithm

The algorithm itself is extremely simple and is described by the following formula:

Implementation

Using the C++ ternary conditional operator, the algorithm can be written even more briefly:

Finally, we present the non-recursive form of the algorithm:

Proof of correctness

First, note that with each iteration of the Euclidean algorithm, its second argument strictly decreases, therefore, since it is non-negative, then the Euclidean algorithm always completes.

For proof of correctness we need to show that for any >.

Let us show that the quantity on the left side of the equation is divided by the real one on the right, and the quantity on the right is divided by the one on the left. Obviously, this will mean that the left and right sides coincide, which will prove the correctness of the Euclidean algorithm.

Let's denote . Then, by definition, and .

But then it follows from here:

So, recalling the statement, we get the system:

Let us now use the following simple fact: if for some three numbers: and , then also holds: . In our situation we get:

Or, substituting its definition as , we get:

So, we have done half of the proof: we have shown that the left side divides the right. The second half of the proof is done in a similar way.

Working hours

The running time of the algorithm is estimated Lamé's theorem, which establishes a surprising connection between the Euclidean algorithm and the Fibonacci sequence:

If > and for some , then the Euclidean algorithm will perform no more recursive calls.