Euclid's algorithm - finding the greatest common divisor. Math I like Euclid's algorithm for calculating the greatest common divisor

07.07.2020

In the preface to his first edition, In the Realm of Ingenuity (1908), E. I. Ignatiev writes: The results are reliable only when the introduction to the field of mathematical knowledge is made in an easy and pleasant way, on objects and examples of everyday and everyday situations, selected with proper wit and amusement.

In the preface to the 1911 edition of “The Role of Memory in Mathematics”, E.I. Ignatiev writes "... in mathematics, one should remember not formulas, but the process of thinking."

To extract the square root, there are tables of squares for two-digit numbers, you can decompose the number into prime factors and extract the square root from the product. The table of squares is not enough, extracting the root by factoring is a time-consuming task, which also does not always lead to the desired result. Try to extract the square root of the number 209764? Decomposition into prime factors gives the product 2 * 2 * 52441. By trial and error, selection - this, of course, can be done if you are sure that this is an integer. The way I want to suggest allows you to take the square root in any case.

Once at the institute (Perm State Pedagogical Institute) we were introduced to this method, which I now want to talk about. I never thought about whether this method has a proof, so now I had to deduce some evidence myself.

The basis of this method is the composition of the number =.

=&, i.e. &2=596334.

1. Split the number (5963364) into pairs from right to left (5`96`33`64)

2. We extract the square root of the first group on the left ( - number 2). So we get the first digit of the number &.

3. Find the square of the first digit (2 2 \u003d 4).

4. Find the difference between the first group and the square of the first digit (5-4=1).

5. We demolish the next two digits (we got the number 196).

6. We double the first figure we found, write it down to the left behind the line (2*2=4).

7. Now you need to find the second digit of the number &: the doubled first digit that we found becomes the digit of the tens of the number, when multiplied by the number of units, you need to get a number less than 196 (this is the number 4, 44 * 4 \u003d 176). 4 is the second digit of &.

8. Find the difference (196-176=20).

9. We demolish the next group (we get the number 2033).

10. Double the number 24, we get 48.

11.48 tens in a number, when multiplied by the number of units, we should get a number less than 2033 (484 * 4 \u003d 1936). The digit of units found by us (4) is the third digit of the number &.

The proof is given by me for the cases:

1. Extracting the square root of a three-digit number;

2. Extracting the square root of a four-digit number.

Approximate methods for extracting the square root (without using a calculator).

1. The ancient Babylonians used the following method to find the approximate value of the square root of their x number. They represented the number x as a sum a 2 + b, where a 2 is the closest to x the exact square of the natural number a (a 2 ? x), and used the formula . (1)

Using formula (1), we extract the square root, for example, from the number 28:

The result of extracting the root of 28 using MK 5.2915026.

As you can see, the Babylonian method gives a good approximation to the exact value of the root.

2. Isaac Newton developed a square root method that dates back to Heron of Alexandria (c. 100 AD). This method (known as Newton's method) is as follows.

Let a 1- the first approximation of a number (as a 1, you can take the values of the square root of a natural number - an exact square that does not exceed X) .

The next, more accurate approximation a 2 numbers found by the formula .

Size: px

Start impression from page:

transcript

1 LECTURE 2 CALCULATION OF THE GREAT COMMON DIVISION Euclid's algorithm When working with large composite numbers, their decomposition into prime factors is usually unknown. But for many applied problems of number theory, the search for factoring a number is an important, often encountered practical problem. In number theory, there is a relatively fast way to calculate the gcd of two numbers, which is called the Euclid algorithm. Algorithm 1. Euclid's algorithm. Entrance. Integers a, b; 0< b < а. Выход. d = НОД (a,b). 1. Положить r 0 a, r 1 b, i Найти остаток r i+1 от деления r i 1 на r i. 3. Если r i+1 = 0, то положить d r i. В противном случае положить i i + 1 и вернуться на шаг Результат: d. Теорема. Для любых а, b >0, the Euclid algorithm stops and the number d it produces is the greatest common divisor of the numbers a and b. Proof . By the division theorem with a remainder, for any i 1 we have r i 1 = q i r i + r i+1, where 0 r i+1< r i. Получаем монотонно убывающую последовательность неотрицательных целых чисел r 1 >r 2 > r 3 >... 0 bounded from below. Such a sequence cannot be infinite, hence Euclid's algorithm stops. Euclid's Binary Algorithm The Euclid's Binary GCD algorithm turns out to be faster when implementing this

2 algorithms on the computer, because it uses the binary representation of the numbers a and b. The binary Euclid algorithm is based on the following properties of the greatest common divisor (we assume that 0< b а): 1) если оба числа а и b четные, то НОД(a,b) = 2 НОД(a/2, b/2) 2) если число а нечетное, число b четное, то НОД(a, b) = НОД(а, b/2); 3) если оба числа а и b нечетные, а >b, then gcd(a, b) = gcd(a b, b); 4) if a = b, then gcd(a, b) = a. Algorithm 2. Binary Euclid's algorithm. Entrance. Integers a, b; 0< b а. Выход. d = HOД(a,b). 1. Положить g Пока оба числа а и b четные, выполнять а a/2, b b/2, g 2g до получения хотя бы одного нечетного значения а или b. 3. Положить u a, v b. 4. Пока u 0, выполнять следующие действия Пока u четное, полагать u u/ Пока v четное, полагать v v/ При u v положить u u v. В противном случае положить v v u. 5. Положить d gv. 6. Результат: d. Расширенный алгоритм Евклида Расширенный алгоритм Евклида находит наибольший общий делитель d чисел а и b и его линейное представление, т. е. целые числа x и у, для которых ах + by = d, и не требует «возврата», как в рассмотренном примере. Пусть d НОД для a и b, т. е. d = (a, b), где a >b. Then there are integers x and y such that d = ax + by. In other words, the gcd of two numbers can be represented in

3 as a linear combination of these numbers with integer coefficients. Algorithm 3. Scheme of the extended Euclid algorithm. 1. Determine = 1, = 0, = 0, = 1, α = a, β = b. 2. Let the number q be the quotient of the number a divided by the number b, and the number r be the remainder of the division of these numbers (i.e., a = qb + r). a = b; b = r; t = ; //t = x i-1 ; = tq; // = x i for the right side = x i+1 for the right side; //t = y i-1 ; = tq; 5. Go back to step Determine x = x 0, y = y 0, d = αx + βy. A variant of the extended Euclid algorithm Log. Integers a, b; 0< b а. Выход: d = НОД(а, b); такие целые числа х, у, что ах + by = d. 1. Положить r 0 а, r 1 b, х 0 1, x 1 0, у 0 0, y 1 1, i 1 2. Разделить с остатком r i 1 на r i,: r i 1 = q i r i +r i Если r i+1 = 0, то положить d r i, х x i у y i. В противном случае положить x i+1 x i 1 x i, y i+1 y i 1 y i, i i + 1 и вернуться на шаг Результат: d, х, у. Корректность определения чисел х и у,

4 calculated by the algorithm, the following theorem shows. Theorem 4. At each iteration of Algorithm 3, the equality ax i + by i = r i is satisfied, for i 0. Proof. Let's use the method of mathematical induction. For i = 0 and i = 1, the required equality holds due to Step 1 of Algorithm 3. Let us assume that it is true for i 1 and for i. Then at step 3 we get x i+1 = x i 1 x i and y i+1 = y i 1 y i. Therefore, ax i+1 + by i+1 = a(x i 1 x i) + b(y i 1 y i,) = ax i 1 + by i 1 (ax i + by i) = r i 1 r i = r i+1 . Example. Given a = 1769, b = 551. Using the extended Euclidean algorithm, find integers x and y such that d = ax + by, where d gcd of numbers a and b. I stage of the sequence of calculations. 1. Determine = 1, = 0, = 0, = 1, α = 1769, β = Quotient q = a / b = 1769/551 = 3, and the remainder of the division r = 116. a = 551; b = 116; t = =0: = t q = 1 0 = 1 = 0; = t q = 3; the following intermediate values

5 parameters: a= 551, b = 116, = 0, = 1, = 1, = Since the remainder of the division is r 0, we return to step 2. Stage II of the calculation sequence. 1. Parameter value: a = 551, b = 116, = 0, = 1, = 1, = Quotient q = a/b = 551/116 = 4, and remainder r = 87. a = 116; b = 87; t == 0; =1: = t q = = 4 = 3; = t q = 1 (3) 4 = 13; the following intermediate values of the parameters: a= 116, b = 87, = 1, = 4, = 3, = Since the remainder of the division is r 0, we return to step 2. Stage III of the calculation sequence. 1. Value of parameters: a= 116, b = 87, = 1, = 4, = 3, = Quotient q = a/b = 116/87 = 1, and remainder r = 29.

6 a = 87; b = 29; t = = 4: = t q = 1 (4) 1 = 5; = 3; = 13; = t q = 3 (13) 1 = 16; the following intermediate values of the parameters: a= 87, b = 29, = 4, = 5, = 13, = Since the remainder of the division is r 0, we return to step 2. Stage IV of the calculation sequence. 1. Parameter value: a= 87, b = 29, = 4, = 5, = 13, = Quotient q = a/b = 87/29 = 3, and remainder r = 0. a = 87; b = 29; t == 4; = 5; = 19; = 13; = 16; = t q = 13 (16) 3 = 61; the following intermediate parameter values: a= 87, b = 29, = 5, = 19, = 16, = Since the remainder of the division is r = 0, we perform step 6.

7 6. Calculate the GCD using the formula d = αx + βy, where x = x 0 = 5, y = y 0 = 16, α= 1769, β = 551. Substituting the value of the parameters, we obtain d = αx + βy = = = 29 The extended Euclid algorithm can also be implemented in binary form. Algorithm 4. Extended Binary Euclid Algorithm. Entrance. Integers a, b; 0< b а. Выход. d = НОД(a, b); такие целые числа х, у, что ах + by = d. 1. Положить g Пока оба числа а и b четные, выполнять а a/2, b b/2, g 2g до получения хотя бы одного нечетного значения а или b. 3. Положить u a, v b, А 1, В 0, С 0, D Пока u 0, выполнять следующие действия Пока u четное, положить u u/ Если оба числа А и B четные, то положить A A/2, B B/2. В противном случае положить A (A+b)/2, B (B a)/ Пока v четное: Положить v v/ Если оба числа С и D четные, то положить С C/2, D D/2. В противном случае положить C (C + b)/2, D (D a)/ При u v положить u u v, А А С, В В D. В противном случае положить v v u, C C A, D D B. 5. Положить d gv, x С, у D. 6. Результат: d, х, у.

Solution of equations in integers Linear equations. Direct enumeration method Example. Rabbits and pheasants are sitting in a cage. They have 8 legs in total. Find out how many of those and others are in the cell. List all solutions. Solution.

Lesson 7 A number d is called the greatest common divisor (GCD) of numbers a and b if (1) d a and d b, and also (2) for all x from x a and x b follows x d. In this case, we write d = (a, b). Lemma 1. For any numbers

Topic. Fundamentals of elementary number theory and applications - Theoretical material. Set of modulo residues, properties of congruences. Let be a natural number greater than . We denote by Z the set of all classes

Ugra Physics and Mathematics Lyceum VP Chuvakov BASICS OF NUMBER THEORY Lecture notes (0)(mod) (0)(mod) Natural numbers N, - the set of natural numbers used for counting or enumeration

Chapter 2 Integer, rational and real numbers 2.. Integer numbers Numbers, 2, 3,... are called natural. The set of all natural numbers is denoted by N, i.e. N = (,2,3,...). Numbers..., 3, 2,0,2,3,...

Continued fractions Finite continued fractions Definition An expression of the form a 0 + a + a + + a m where a 0 Z a a m N a m N/() is called a continued fraction and m is the length of the continued fraction a 0 a a m will be called the coefficients of the continued fraction

LECTURE 1 SOME ELEMENTS OF NUMBER THEORY

Gorbachev NOT Polynomials in one variable Solving equations of degree The concept of a polynomial Arithmetic operations on polynomials Dep A polynomial (polynomial) of the th degree with respect to a variable

Divisibility of integers The number a is divisible by the number b (or b divides a) if there is such a number c that a = bc In this case, the number c is called the quotient of dividing a by b Notation: a - a is divisible by b or ba b divides

LECTURE 12 COMPARISONS OF THE SECOND DEGREE ON A SIMPLE MODULAR AND QUADRATIC RESIDUES The general form of comparison of the second degree modulo p has the form (1) c 0 x 2 + c 1 x + c 2 0 mod p. Finding a Comparison Solution (1)

Instructions, solutions, answers EQUATIONS IN INTEGER. Equation with one unknown. Solution. Let's put it into the equation. We get the equality (4a b 4) (a b 8) 0. The equality A B 0, where A and B are integers, is satisfied,

Algebraic polynomials. 1 Algebraic polynomials of degree n over a field K Definition 1.1 A polynomial of degree n, n N (0), in a variable z over a number field K is an expression of the form: fz = a n z n

Lecture Quadratic residues and non-residues Lecturer: Nyu Zolotykh Recorded by: E Zamaraeva?? September 00 Contents Quadratic residues and non-residues Legendre symbol Properties of the Legendre symbol Quadratic law of reciprocity

State Educational Institution Boarding School "Intellectual" natural numbers as a linear combination with integer coefficients"

Mathematical analysis Section: Indefinite integral Topic: Integration of rational fractions Lecturer Pakhomova E.G. 0 5. Integration of rational fractions DEFINITION. The rational fraction is called

4 Number theory 4 Integers 7 Definition Let, b Z Then divides b if there is an integer such that b (denoted by b) 73 Theorem (division with remainder) If, b Z and b, then there are such integers

Mathematical analysis Section: Indefinite integral Topic: Integration of rational fractions Lecturer Rozhkova S.V. 0 5. Integration of rational fractions DEFINITION. The rational fraction is called

009-00 account year. 6, 9 cells. Maths. Elements of number theory. 4. Calculation of the greatest common divisor and least common multiple Let's keep the notation from the paragraph. For a natural number n, the notation n

APPLIED ALGEBRA. Part I: Finite fields (Galois fields). I 1 / 67 Part I Finite fields (Galois fields). I APPLIED ALGEBRA. Part I: Finite fields (Galois fields). I 2 / 67 Residue fields modulo prime

5 Solving equations in integers In solving even such simple equations as a linear equation with one unknown, there are some peculiarities if the coefficients of the equation are integers, and it is required

Laboratory work 8 Calculation of the greatest common divisor for two numbers using the Euclidean algorithm

Section 1. Mathematical foundations of cryptography 1 Field definition A finite field GF q (or a Galois field) is a finite arbitrary set of elements with addition and multiplication operations specified between them

XIX Interregional Olympiad for Schoolchildren in Mathematics and Cryptography Tasks for Grade 11 Solution of Problem 1 First, we note that if N = pq, where p and q are prime numbers, then the number of natural numbers less than

Polynomials and their roots 2018 Gushchina Elena Nikolaevna Definition: A polynomial of degree n n N is any expression of the form: P & z = a & z & + a &+, z &+, + + a, z + a., where a & , a &+, a, a. R, a&

Lecture 4. STANDARD AES. RIJNDAEL ALGORITHM. AES (Advnced Encrypton Stndrd) is a new single-key encryption standard that has replaced the DES standard. Rjndel algorithm (rhine-dal)

Polynomials and their roots Definition: A polynomial of degree n (n N) is any expression of the form: P n (z) = a n z n + a n 1 z n 1 + + a 1 z + a 0, where a n, a n 1, a 1, a 0 R, a n leading coefficient, a

1 Euclid's algorithm and its complexity Definition 1. A common divisor of numbers a and b is a number c such that c a and c b. Definition 2. The greatest common divisor of numbers a and b is their common divisor,

LECTURE 14 Calculation of square roots modulo composite It follows from the above theory that if =, where and are prime numbers, the group Z is isomorphic to the space Z Z. Since the isomorphism preserves the properties

LECTURE 3 CALCULATION OF SQUARE ROOTS MODULAR Case of a simple module Consider the comparison x a mod p, () where the number p is prime and the integer a is not divisible by p Calculation of the solution x of this equation is

Discrete Mathematics Colloquium Program (main stream) At the beginning of the colloquium, you will receive a ticket containing three questions: a definitions question, a task, and a proofs question.

Shor's algorithm Yu. Lifshits. December 1, 005 Lecture outline 1. Preparation (a) Factoring numbers (b) Quantum computing (c) Emulation of classical computing. Simon's algorithm (a) Quantum parallelism

From the history of mathematics The first fairly voluminous book in which arithmetic was presented independently of geometry was Nicomachus' Introduction to Arithmetic (okne).

A Brief Introduction to the Beginnings of Elementary Number Theory Denis Kirienko Computer Summer School, January 1, 2009 Integer division Let two integers a and b, b 0 be given.

Topic 1-9: Polynomials. Construction of a ring of polynomials. Divisibility Theory. Derivative A. Ya. Ovsyannikov Ural Federal University Institute of Mathematics and Computer Science Department of Algebra and Discrete

Algebraic equations where Definition. Algebraic is an equation of the form 0, P () 0, some real numbers. 0 0 In this case, the variable is called unknown, and the numbers 0 are called

Lecture 6 Elements of number theory 1 Problem. Continue number sequence 1, 3, 5, 7, 1, 3, 5, 7, 11 1, 11, 101, 1001, 1, 11, 101, 1001, 1011, 2 Integer Arithmetic Uses integers: Z = (, -2, -1, 0,

Polynomials A polynomial with one variable x of degree n is an expression of the form, where are any numbers, called the coefficients of the polynomial, and the leading coefficient of the polynomial is called If instead of the variable

1 2 Contents. 1. Introduction. 4-6 1.1. Abstract...4 1.2. Problem 4 1.3. Purpose of work 5 1.4. Hypothesis..5 1.5. Subject of research... 5 1.6. Object of study. 5 1.7. Novelty... 5-6 1.8. Research methods...6

8.3, 8.4.2 class, Mathematics (textbook Makarychev) 2018-2019 academic year Theme of the module “Integers. Divisibility of numbers. Degree with an integer indicator ”The theoretical and practical parts are checked in the test. TOPIC Know

Lecture INTEGRATION OF RATIONAL FRACTIONS Rational fractions Integration of simple rational fractions Decomposition of a rational fraction into simple fractions Integration of rational fractions Rational

Www.cryptolymp.ru XIX Interregional Olympiad for Schoolchildren in Mathematics and Cryptography (Grade 11) Solution of Problem 1 First, we note that if N pq, where p and q are prime numbers, then the number of natural numbers,

Chapter Integers Divisibility theory Integers are called numbers, -3, -, -, 0, 3, those natural numbers, 3, 4, as well as zero and negative numbers -, -, -3, -4, The set of all integers is denoted by

Ministry of Education and Science of the Russian Federation Ural State University of Economics Yu. 4th, rev. and additional e-mail: [email protected],

(trigonometric series trigonometric system examples - expansion on the interval [ -l; l ] for functions of arbitrary period - incomplete series expansion in sines and cosines even and odd continuations)

Theoretical computer science II Lecture 5. Integer algorithms: extended Euclid's algorithm, inverse element modulo, exponentiation modulo. Public key cryptography, RSA protocol. Probabilistic

5. Bose-Chaudhury-Hokvingham codes The corrective properties of cyclic codes can be determined on the basis of two theorems. Theorem 1. For any m and t, there exists a cyclic code of length n = 2 m 1, with multiplicity

MODULAR ARITHMETIC In some applications, it is convenient to perform arithmetic operations on integers given in the so-called modular representation. This representation assumes that the integer

MATHEMATICS USE 00 Koryanov A.G. Assignments From Bryansk Send comments and suggestions to: [email protected] EQUATIONS AND INEQUALITIES IN INTEGER NUMBERS (from educational problems to olympiad problems) Linear

2.22. Take out the common factor (n is a natural number) out of brackets: 1) x n + 3 + x n ; 3) z 3n - z n ; 2) y n + 2 - y n - 2, n > 2; 4) 5n + 4 + 2 5n + 2-3 5n + 1. 2.23. Each number was assigned

LECTURE 15 PRIME NUMBERS A natural number p greater than one is called prime if it is only divisible by 1 and itself. Theorem (Euclid). The set of prime numbers is infinite. Denote by π(x)

Topic 3. Elements of algebraic and analytic number theory Theoretical material 1. Continued fractions. The final continued fraction is the expression a +, (1) where a is an integer, a, i > 0, natural numbers,

Http://vk.ucoz.et/ Operations on polynomials k a k A polynomial (polynomial) of degree k is a function of the form a, where variable, a are numerical coefficients (=,.k), and. Any non-zero number can be considered

Penza State Pedagogical University named after V. G. Belinsky M. V. Glebov V. F. Timerbulatova

Divisibility of integers with remainder Let m be an integer and n a natural number

Avdoshin S.M., Savelyeva A.A. An algorithm for solving systems of linear equations in residue rings An effective algorithm for solving systems of linear equations in residue rings is developed, which is equivalent in complexity to

APPLIED ALGEBRA. Part I: Finite fields (Galois fields) I 1 / 88 Part I Finite fields (Galois fields) I APPLIED ALGEBRA. Part I: Finite fields (Galois fields) I 2 / 88 Residue fields modulo a prime number

5 Algebraic structures 6 Definition A binary operation on a set S is a mapping of S S into S

/E Elements of number theory and. Rochev August 28, 2018 ..... 1 1.2 Greatest common divisor ..................................

Chapter Integer, rational and real numbers. Division with remainder. Divide each of the numbers ±23, ±4 with the remainder by each of the numbers ±5. 2. Find all positive divisors of 42. 3. It's 3 o'clock now.

Differential equations lecture 4 Equations in total differentials. Integrating factor Lecturer Anna Igorevna Sherstneva 9. Equations in total differentials The equation d + d = 14 is called the equation

Topic. Fundamentals of elementary number theory and applications. Primitive roots, indices. Theoretical material Let a, m be natural coprime numbers, and m, then, according to Euler's theorem, a m)

Department of Mathematics and Informatics Elements of Higher Mathematics Educational and methodological complex for students of secondary vocational education studying using distance technologies Module Theory of Limits Compiled by: Associate Professor

Section 2. Numerical methods in cryptography Assignment for independent work To study algorithms that are widely used in cryptography. Elements of number theory: extended Euclid's algorithm;

The thematic plan is based on the program material of the 206-207 academic year according to the textbook "Algebra 8", ed. A.G. Mordkovich, taking into account the recommended mandatory minimum content of education Topic

Lecture 2. Properties of binomial coefficients. Summation and the method of generating functions (final case). Polynomial coefficients. Estimates for binomial and polynomial coefficients. Amount estimates

Let's consider this algorithm with an example. Let's find

1st step. We divide the number under the root into two digits (from right to left):

2nd step. We extract the square root from the first face, that is, from the number 65, we get the number 8. Under the first face, we write the square of the number 8 and subtract. We attribute the second face (59) to the remainder:

(the number 159 is the first remainder).

3rd step. We double the found root and write the result on the left:

4th step. We separate in the remainder (159) one digit on the right, on the left we get the number of tens (it is equal to 15). Then we divide 15 by the doubled first digit of the root, that is, by 16, since 15 is not divisible by 16, then in the quotient we get zero, which we write as the second digit of the root. So, in the quotient we got the number 80, which we double again, and demolish the next face

(the number 15901 is the second remainder).

5th step. We separate one digit from the right in the second remainder and divide the resulting number 1590 by 160. The result (number 9) is written as the third digit of the root and assigned to the number 160. The resulting number 1609 is multiplied by 9 and we find the following remainder (1420):

Further actions are performed in the sequence indicated in the algorithm (the root can be extracted with the required degree of accuracy).

Comment. If the root expression is a decimal fraction, then its integer part is divided into two digits from right to left, the fractional part is divided into two digits from left to right, and the root is extracted according to the specified algorithm.

DIDACTIC MATERIAL

1. Take the square root of the number: a) 32; b) 32.45; c) 249.5; d) 0.9511.

Greetings readers and visitors to our site!. In this section, we will analyze various algorithms, as well as their implementation in Pascal.

To master the material of today's lesson, you will need knowledge and.

Today we will consider three algorithms (out of five) for finding the greatest common divisor of two integers, two of which are directly associated with the name of Euclid. We will look at two more in the next section.
The greatest common divisor (gcd) of two numbers a and b is the largest integer that divides them both.
Example: gcd(25, 5) = 5; gcd(12, 18) = 6.

Search algorithm

Let's start with d- the smallest of two numbers. This is the first obvious candidate for their greatest common divisor. And then, until d divides both numbers, we decrease it by one. As soon as such a division is ensured, we stop the decrease in d.

Var a, b, d: integer; begin write("Enter two numbers: "); readln(a, b); if a< b then d:= a + 1 else d:= b + 1; {так как мы используем цикл с постусловием, необходимо минимальное значение увеличить на один, иначе цикл repeat, в силу своих конструктивных особенностей, не учтет это минимальное число и не сделает его кандидатом в НОД. Например, 5 и 25.} repeat d:= d - 1 until (a mod d = 0) and (b mod d = 0); write("NOD = ", d) end.

Let's turn to this program, for example, with the numbers 30 and 18. Then on the way to the answer (the number 6) it will have to go through the numbers: 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7 .6.

Euclid's algorithm "with subtraction"

Let a and b be integers, then the following statements are true:

All common divisors of the pair a and b are also common divisors of the pair a - b, b;
Conversely, all common divisors of the pair a - b and b are also common divisors of the pair a and b;
gcd(A, B) = gcd(A - B, B) if A > B;
gcd(A, 0) = A.

Proof:

If t is an arbitrary common divisor of a and b, then it also divides the difference a - b. Indeed, from a = t * u and b = t * v it follows that a - b = t * u - t * v = t * (u - v). That is, t is also a common divisor of a - b and b.
Conversely, if t is an arbitrary divisor, the common divisor of a - b and b, then it also divides their sum a - b + b = a. This can be proved analogously to the previous one. Therefore t is also a common divisor of a and b.
We conclude that the set of common divisors a and b coincides with the set of divisors a - b and b. In particular, the greatest common divisors of these pairs also coincide.
The largest integer that divides the number a is the number a itself. The number 0 is divisible by any number. Hence the greatest common divisor of a and 0 is a.

The proven formula (3) allows us to reduce the calculation of the greatest divisor of one pair to the calculation of the greatest common divisor of another pair, in which the numbers are already smaller. The obvious formula (4) lets us know when to stop.

Briefly, Euclid's "with subtraction" algorithm would be as follows. We subtract the smaller number from the larger number and replace the larger one with the difference until one of the numbers becomes zero. Then the remaining non-zero number is the greatest common divisor.

Example. Let a = 82 and b = 60. GCD(82, 60) = GCD(22, 60) = GCD(22, 38) = GCD(22, 16) = GCD(6, 16) = GCD(6, 10) = gcd(6, 4) = gcd(2, 4) = gcd(2, 2) = gcd(2, 0) = 2.

At the penultimate step of the algorithm, before the appearance of 0, both numbers are equal, otherwise 0 could not have arisen. Therefore, we will extract the GCD at this very moment.

Block diagram of the Euclid "with subtraction" algorithm

Program

var a, b: integer; begin write("a = "); readln(a); write("b = "); readln(b); while a<>b do if a > b then a:= a - b else b:= b - a; writeln("NOD = ", a); end.

Euclid's algorithm with "division"

Let a and b be integers, and r be the remainder of dividing a by b. Then gcd(a, b) = gcd(b, r).

This formula also allows you to reduce the calculation of the greatest common divisor of one pair of numbers to the calculation of the greatest common divisor of another pair of numbers.

Example. gcd(82, 60) = gcd(22, 60) = gcd(22, 16) = gcd(6, 16) = gcd(6, 4) = gcd(2, 4) = gcd(0, 2) = 2 .

Var a, b: integer; begin write("a = "); readln(a); write("b = "); readln(b); while (a<>0) and (b<>0) do if a >= b then a:= a mod b else b:= b mod a; write(a + b) end.

That's all for today! You will learn a few more modifications of the Euclid algorithm and ways to find GCD in the next lessons.