This article is about finding the greatest common divisor (GCD) two or more numbers. First, let's look at the Euclid algorithm; it allows you to find the gcd of two numbers. After this, we will focus on a method that allows us to calculate the gcd of numbers as the product of their common prime factors. Next, we will look at finding the greatest common divisor of three or more numbers, and also give examples of calculating the gcd of negative numbers.

Page navigation.

Euclidean algorithm for finding GCD

Note that if we had turned to the table of prime numbers from the very beginning, we would have found out that the numbers 661 and 113 are prime numbers, from which we could immediately say that their greatest common divisor is 1.

Answer:

GCD(661, 113)=1 .

Finding GCD by factoring numbers into prime factors

Let's consider another way to find GCD. The greatest common divisor can be found by factoring numbers into prime factors. Let's formulate a rule: The gcd of two positive integers a and b is equal to the product of all common prime factors found in the prime factorizations of the numbers a and b.

Let's give an example to explain the rule for finding GCD. Let us know the decompositions of the numbers 220 and 600 into prime factors, they have the form 220=2·2·5·11 and 600=2·2·2·3·5·5. The common prime factors involved in factoring the numbers 220 and 600 are 2, 2 and 5. Therefore, GCD(220, 600)=2·2·5=20.

Thus, if we factor the numbers a and b into prime factors and find the product of all their common factors, then this will find the greatest common divisor of the numbers a and b.

Let's consider an example of finding GCD according to the stated rule.

Example.

Find the greatest common divisor of the numbers 72 and 96.

Solution.

Let's factor the numbers 72 and 96 into prime factors:

That is, 72=2·2·2·3·3 and 96=2·2·2·2·2·3. Common prime factors are 2, 2, 2 and 3. Thus, GCD(72, 96)=2·2·2·3=24.

Answer:

GCD(72, 96)=24 .

In conclusion of this paragraph, we note that the validity of the above rule for finding GCD follows from the property of the greatest common divisor, which states that 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

Finding the greatest common divisor of three or more numbers can be reduced to sequentially finding the gcd of two numbers. We mentioned this when studying the properties of GCD. There we formulated and proved the theorem: the greatest common divisor of several numbers a 1, a 2, ..., a k is equal to the number d k, which is found by sequentially calculating 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.

Let's see what the process of finding the gcd of several numbers looks like by looking at the solution to the example.

Example.

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

Solution.

In this example, a 1 =78, a 2 =294, a 3 =570, a 4 =36.

First, using the Euclidean algorithm, we determine the greatest common divisor d 2 of the first two numbers 78 and 294. When dividing, we obtain the equalities 294 = 78 3 + 60 ; 78=60·1+18 ; 60=18·3+6 and 18=6·3. Thus, d 2 =GCD(78, 294)=6.

Now let's calculate d 3 =GCD(d 2, a 3)=GCD(6, 570). Let's apply the Euclidean algorithm again: 570=6·95, therefore, d 3 = GCD(6, 570)=6.

It remains to calculate d 4 =GCD(d 3, a 4)=GCD(6, 36). Since 36 is divisible by 6, then d 4 = GCD(6, 36) = 6.

Thus, the greatest common divisor of the four given numbers is d 4 =6, that is, gcd(78, 294, 570, 36)=6.

Answer:

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

Factoring numbers into prime factors also allows you to calculate the gcd of three or more numbers. In this case, the greatest common divisor is found as the product of all common prime factors of the given numbers.

Example.

Calculate the gcd of the numbers from the previous example using their prime factorizations.

Solution.

Let's factor the numbers 78, 294, 570 and 36 into prime factors, we get 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2·3· 3. The common prime factors of all these four numbers are numbers 2 and 3. Hence, GCD(78, 294, 570, 36)=2·3=6.

The circle showed how you can extract square roots in a column. You can calculate the root with arbitrary precision, find any number of digits in its decimal notation, even if it turns out to be irrational. The algorithm was remembered, but questions remained. It was not clear where the method came from and why it gave the correct result. It wasn’t in the books, or maybe I was just looking in the wrong books. In the end, like much of what I know and can do today, I came up with it myself. I share my knowledge here. By the way, I still don’t know where the rationale for the algorithm is given)))

So, first I tell you “how the system works” with an example, and then I explain why it actually works.

Let’s take a number (the number was taken “out of thin air”, it just came to mind).

1. We divide its numbers into pairs: those to the left of the decimal point are grouped two from right to left, and those to the right are grouped two from left to right. We get.

2. We extract the square root from the first group of numbers on the left - in our case this is (it is clear that the exact root may not be extracted, we take a number whose square is as close as possible to our number formed by the first group of numbers, but does not exceed it). In our case this will be a number. We write down the answer - this is the most significant digit of the root.

3. We square the number that is already in the answer - this - and subtract it from the first group of numbers on the left - from the number. In our case it remains .

4. We assign the following group of two numbers to the right: . We multiply the number that is already in the answer by , and we get .

5. Now watch carefully. We need to assign one digit to the number on the right, and multiply the number by, that is, by the same assigned digit. The result should be as close as possible to, but again no more than this number. In our case, this will be the number, we write it in the answer next to, on the right. This is the next digit in the decimal notation of our square root.

6. From subtract the product , we get .

7. Next, we repeat the familiar operations: we assign the following group of digits to the right, multiply by , to the resulting number > we assign one digit to the right, such that when multiplied by it we get a number smaller than , but closest to it - this is the next digit in decimal root notation.

The calculations will be written as follows:

And now the promised explanation. The algorithm is based on the formula

Comments: 51

1. 2 Anton:

   Too chaotic and confusing. Arrange everything point by point and number them. Plus: explain where we substitute the required values ​​in each action. I’ve never calculated a root root before; I had a hard time figuring it out.

2. 5 Julia:

3. 6 :

   Yulia, 23 is currently written on the right; these are the first two (on the left) digits of the root already received in the answer. Multiply by 2 according to the algorithm. We repeat the steps described in point 4.

4. 7 zzz:

   error in “6. From 167 we subtract the product 43 * 3 = 123 (129 nada), we get 38.”
   I don’t understand how it turned out to be 08 after the decimal point...

5. 9 Fedotov Alexander:

   And even in the pre-calculator era, we were taught at school not only the square root, but also the cube root in a column, but this was more tedious and painstaking work. It was easier to use Bradis tables or a slide rule, which we already studied in high school.

6. 10 :

   Alexander, you are right, you can extract roots of large powers into a column. I'm going to write just about how to find the cube root.

7. 12 Sergei Valentinovich:

   Dear Elizaveta Alexandrovna! In the late 70s, I developed a scheme for automatic (i.e., not by selection) calculation of quadra. root on the Felix adding machine. If you are interested, I can send you a description.

8. 14 Vlad aus Engelsstadt:

   (((Extracting the square root of the column)))
   The algorithm is simplified if you use the 2nd number system, which is studied in computer science, but is also useful in mathematics. A.N. Kolmogorov presented this algorithm in popular lectures for schoolchildren. His article can be found in the “Chebyshev Collection” (Mathematical Journal, look for a link to it on the Internet)
   By the way, say:
   G. Leibniz at one time toyed with the idea of ​​​​transitioning from the 10th number system to the binary one because of its simplicity and accessibility for beginners (primary schoolchildren). But breaking established traditions is like breaking a fortress gate with your forehead: it’s possible, but it’s useless. So it turns out, as according to the most quoted bearded philosopher in the old days: the traditions of all dead generations suppress the consciousness of the living.

   Until next time.

9. 15 Vlad aus Engelsstadt:

   ))Sergey Valentinovich, yes, I’m interested...((

   I bet that this is a variation on the “Felix” of the Babylonian method of extracting the square knight using the method of successive approximations. This algorithm was covered by Newton's method (tangent method)

   I wonder if I was wrong in my forecast?

10. 18 :

    2Vlad aus Engelsstadt

    Yes, the algorithm in binary should be simpler, that's pretty obvious.

    About Newton's method. Maybe that's true, but it's still interesting

11. 20 Kirill:

    Thanks a lot. But there is still no algorithm, no one knows where it came from, but the result is correct. THANKS A LOT! I've been looking for this for a long time)

12. 21 Alexander:

    How will you extract the root from a number where the second group from left to right is very small? for example, everyone's favorite number is 4,398,046,511,104. After the first subtraction, it is not possible to continue everything according to the algorithm. Can you explain please.

13. 22 Alexey:

    Yes, I know this method. I remember reading it in the book “Algebra” of some old edition. Then, by analogy, he himself deduced how to extract the cube root in a column. But there it’s already more complicated: each digit is determined not by one (as for a square), but by two subtractions, and even there you have to multiply long numbers every time.

14. 23 Artem:

    There are typos in the example of extracting the square root of 56789.321. The group of numbers 32 is assigned twice to the numbers 145 and 243, in the number 2388025 the second 8 must be replaced by 3. Then the last subtraction should be written as follows: 2431000 – 2383025 = 47975.
    Additionally, when dividing the remainder by the doubled value of the answer (without taking into account the comma), we obtain an additional number of significant digits (47975/(2*238305) = 0.100658819...), which should be added to the answer (√56789.321 = 238.305... = 238.305100659).

15. 24 Sergey:

    Apparently the algorithm came from Isaac Newton’s book “General Arithmetic or a book on arithmetic synthesis and analysis.” Here is an excerpt from it:

    ABOUT EXTRACTING ROOTS

    To extract the square root of a number, you must first place a dot above its digits, starting from the ones. Then you should write in the quotient or radical the number whose square is equal to or closest in disadvantage to the numbers or number preceding the first point. After subtracting this square, the remaining digits of the root will be sequentially found by dividing the remainder by twice the value of the already extracted part of the root and subtracting each time from the remainder of the square the last found digit and its tenfold product by the named divisor.

16. 25 Sergey:

    Please also correct the title of the book “General Arithmetic or a book about arithmetic synthesis and analysis”

17. 26 Alexander:

    Thanks for the interesting material. But this method seems to me somewhat more complicated than what is needed, for example, for a schoolchild. I use a simpler method based on expanding a quadratic function using the first two derivatives. Its formula is:
    sqrt(x)= A1+A2-A3, where
    A1 is the integer whose square is closest to x;
    A2 is a fraction, the numerator is x-A1, the denominator is 2*A1.
    For most numbers encountered in a school course, this is enough to get the result accurate to the hundredth.
    If you need a more accurate result, take
    A3 is a fraction, the numerator is A2 squared, the denominator is 2*A1+1.
    Of course, to use it you need a table of squares of integers, but this is not a problem at school. Remembering this formula is quite simple.
    However, it confuses me that I obtained A3 empirically as a result of experiments with a spreadsheet and I do not quite understand why this member has this appearance. Maybe you can give me some advice?

18. 27 Alexander:

    Yes, I've considered these considerations too, but the devil is in the details. You write:
    “since a2 and b differ quite little.” The question is exactly how little.
    This formula works well on numbers in the second ten and much worse (not up to hundredths, only up to tenths) on numbers in the first ten. Why this happens is difficult to understand without the use of derivatives.

19. 28 Alexander:

    I will clarify what I see as the advantage of the formula I propose. It does not require the not entirely natural division of numbers into pairs of digits, which, as experience shows, is often performed with errors. Its meaning is obvious, but for a person familiar with analysis, it is trivial. Works well on numbers from 100 to 1000, which are the most common numbers encountered in school.

20. 29 Alexander:

    By the way, I did some digging and found the exact expression for A3 in my formula:
    A3= A22 /2(A1+A2)

21. 30 vasil stryzhak:

    In our time, with the widespread use of computer technology, the question of extracting the square knight from a number is not worth it from a practical point of view. But for mathematics lovers, various options for solving this problem will undoubtedly be of interest. In the school curriculum, the method of this calculation without the use of additional funds should take place on a par with multiplication and long division. The calculation algorithm must not only be memorized, but also understandable. The classical method, presented in this material for discussion with disclosure of the essence, fully complies with the above criteria.
    A significant drawback of the method proposed by Alexander is the use of a table of squares of integers. The author is silent about the majority of numbers encountered in the school course. As for the formula, in general I like it due to the relatively high accuracy of the calculation.

22. 31 Alexander:

    for 30 vasil stryzhak
    I didn't keep anything quiet. The table of squares is supposed to be up to 1000. In my time at school they simply learned it by heart and it was in all mathematics textbooks. I explicitly named this interval.
    As for computer technology, it is not used mainly in mathematics lessons, unless the topic of using a calculator is specifically discussed. Calculators are now built into devices that are prohibited for use on the Unified State Exam.

23. 32 vasil stryzhak:

    Alexander, thank you for the clarification! I thought that for the proposed method it is theoretically necessary to remember or use a table of squares of all two-digit numbers. Then for radical numbers not included in the interval from 100 to 10000, you can use the technique of increasing or decreasing them by the required number of orders of magnitude by moving the decimal point.

24. 33 vasil stryzhak:

25. 39 ALEXANDER:

    MY FIRST PROGRAM IN IAMB LANGUAGE ON THE SOVIET MACHINE “ISKRA 555″ WAS WRITTEN TO EXTRACT THE SQUARE ROOT OF A NUMBER USING THE COLUMN EXTRACTION ALGORITHM! and now I forgot how to extract it manually!

Since ancient times, work with numbers has been divided into two different areas: one directly concerned the properties of numbers, the other was associated with counting techniques. By "arithmetic" in many countries this latter field is usually meant, which is undoubtedly the oldest branch of mathematics.

Apparently, the greatest difficulty for ancient calculators was working with fractions. This can be seen from the Ahmes Papyrus (also called the Rhind Papyrus), an ancient Egyptian work on mathematics dating back to around 1650 BC. All fractions mentioned in the papyrus, with the exception of 2/3, have numerators equal to 1. The difficulty of handling fractions is also noticeable when studying ancient Babylonian cuneiform tablets. Both the ancient Egyptians and Babylonians apparently performed calculations using some form of abacus. The science of numbers received significant development among the ancient Greeks starting with Pythagoras, around 530 BC. As for the technology of calculation itself, much less was done in this area by the Greeks.

The later Romans, on the contrary, made virtually no contribution to the science of numbers, but based on the needs of rapidly developing production and trade, they improved the abacus as a counting device. Very little is known about the origins of Indian arithmetic. Only a few later works on the theory and practice of number operations have come down to us, written after the Indian positional system was improved by including zero in it. Exactly when this happened we do not know for sure, but it was then that the foundations for our most common arithmetic algorithms were laid.

The Indian number system and the first arithmetic algorithms were borrowed by the Arabs. The earliest extant Arabic arithmetic textbook was written by al-Khwarizmi around 825. It makes extensive use and explanation of Indian numerals. This textbook was later translated into Latin and had a significant influence on Western Europe. A distorted version of the name al-Khwarizmi has come down to us in the word “algorism”, which, when further mixed with the Greek word arrhythmos became the term "algorithm".

Indo-Arabic arithmetic became known in Western Europe mainly thanks to the work of L. Fibonacci Book of abacus (Liber abaci, 1202). The Abacist method offered simplifications similar to the use of our positional system, at least for addition and multiplication. The Abacists were replaced by algorithms that used zero and the Arabic method of division and square root extraction. One of the first arithmetic textbooks, the author of which is unknown to us, was published in Treviso (Italy) in 1478. It dealt with calculations when making trade transactions. This textbook became the predecessor of many arithmetic textbooks that appeared subsequently. Until the beginning of the 17th century. More than three hundred such textbooks were published in Europe. Arithmetic algorithms have been significantly improved during this time. In the 16th–17th centuries. Symbols for arithmetic operations appeared, such as =, +, -, ґ, ё and .

Mechanization of arithmetic calculations.

As society developed, so did the need for faster and more accurate calculations. This need gave rise to four remarkable inventions: Indo-Arabic numerals, decimals, logarithms and modern computing machines.

In fact, the simplest calculating devices existed before the advent of modern arithmetic, because in ancient times elementary arithmetic operations were performed on the abacus (in Russia, abacuses were used for this purpose). The simplest modern computing device can be considered a slide rule, which consists of two logarithmic scales sliding one along the other, which allows multiplication and division by summing and subtracting segments of the scales. B. Pascal (1642) is considered to be the inventor of the first mechanical adding machine. Later in the same century, G. Leibniz (1671) in Germany and S. Moreland (1673) in England invented machines for performing multiplication. These machines became the predecessors of desktop computing devices (arithmometers) of the 20th century, which made it possible to quickly and accurately perform addition, subtraction, multiplication and division operations.

In 1812, the English mathematician C. Babbage began to create a design for a machine for calculating mathematical tables. Although work on the project continued for many years, it remained unfinished. Nevertheless, Babbage’s project served as an incentive for the creation of modern electronic computers, the first examples of which appeared around 1944. The speed of these machines was amazing: with their help, in minutes or hours it was possible to solve problems that previously required many years of continuous calculations, even with the use of adding machines.

Positive integers.

Let A And B are two finite sets that have no common elements, and let A contains n elements, and B contains m elements. Then many S, consisting of all elements of the sets A And B, taken together, is a finite set containing, say, s elements. For example, if A consists of elements ( a, b, c), a bunch of IN– from elements ( x, y), then the set S=A+B and consists of elements ( a, b, c, x, y). Number s called amount numbers n And m, and we write it like this: s = n + m. In this entry the numbers n And m are called terms, the operation of finding the sum – addition. The operation symbol "+" is read as "plus". A bunch of P, consisting of all ordered pairs in which the first element is chosen from the set A, and the second one is from the set B, is a finite set containing, say, p elements. For example, if, as before, A = {a, b, c}, B = {x, y), That P=AґB = {(a,x), (a,y), (b,x), (b,y), (c,x), (c,y)). Number p called work numbers a And b, and we write it like this: p = aґb or p = a×b. Numbers a And b in the work they are called multipliers, the operation of finding the product – multiplication. The operation symbol ґ is read as “multiplied by.”

It can be shown that from these definitions the following fundamental laws of addition and multiplication of integers follow:

– the law of commutative addition: a + b = b + a;

– law of associative addition: a + (b + c) = (a + b) + c;

– the law of commutative multiplication: aґb = bґa;

– law of associativity of multiplication: aґ(bґc) = (aґb)ґc;

– law of distributivity: aґ(b + c)= (aґb) + (aґc).

If a And b– two positive integers and if there is a positive integer c, such that a = b + c, then we say that a more b(this is written like this: a>b), or what b less a(this is written like this: b). For any two numbers a And b one of three relationships holds: either a = b, or a>b, or a.

The first two fundamental laws say that the sum of two or more terms does not depend on how they are grouped or in what order they are arranged. Similarly, from the third and fourth laws it follows that the product of two or more factors does not depend on how the factors are grouped or what their order is. These facts are known as the "generalized laws of commutativity and associativity" of addition and multiplication. It follows from them that when writing the sum of several terms or the product of several factors, the order of the terms and factors is unimportant and the parentheses can be omitted.

In particular, the repeated sum a + a + ... + a from n terms is equal to nґa. Repeated work aґaґ ... ґa from n We agreed to denote the factors a n; number a called basis, and the number n – repeat product indicator, the repeated work itself – nth power numbers a. These definitions allow us to establish the following fundamental laws for exponents:

Another important consequence of the definitions: aґ1 = a for any integer a, and 1 is the only integer that has this property. The number 1 is called unit.

Divisors of integers.

If a, b, c– integers and aґb = c, That a And b are divisors of a number c. Because aґ1 = a for any integer a, we conclude that 1 is a divisor of any integer and that any integer is a divisor of itself. Any integer divisor a, different from 1 or a, got the name proper divisor numbers a.

Any integer other than 1 and not having its own divisors is called prime number. (An example of a prime number is the number 7.) A whole number that has its own divisors is called composite number. (For example, the number 6 is composite, since 2 divides 6.) From the above it follows that the set of all integers is divided into three classes: one, prime numbers and composite numbers.

There is a very important theorem in number theory that states that “any integer can be represented as a product of prime numbers, and up to the order of the factors, such a representation is unique.” This theorem is known as the "fundamental theorem of arithmetic". It shows that prime numbers serve as the “building blocks” from which all integers other than one can be constructed using multiplication.

If a certain set of integers is given, then the largest integer that is a divisor of each number included in this set is called greatest common divisor given set of numbers; the smallest integer whose divisor is each number from a given set is called least common multiple given set of numbers. Thus, the greatest common divisor of the numbers 12, 18 and 30 is 6. The least common multiple of the same numbers is 180. If the greatest common divisor of two integers a And b is equal to 1, then the numbers a And b are called mutually prime. For example, the numbers 8 and 9 are relatively prime, although neither of them is prime.

Positive rational numbers.

As we have seen, integers are abstractions that arise from the process of counting finite sets of objects. However, for the needs of everyday life, integers are not enough. For example, when measuring the length of a table top, the adopted unit of measurement may be too large and not fit a whole number of times into the measured length. To cope with such a difficulty, with the help of the so-called. fractional(i.e., literally, “broken”) numbers, a smaller unit of length is introduced. If d– some integer, then the fractional unit 1/ d determined by the property dґ1/d= 1, and if n is an integer, then nґ1/d we simply write it as n/d. These new numbers are called “ordinary” or “simple” fractions. Integer n called numerator fractions and numbers d – denominator. The denominator shows how many equal shares the unit was divided into, and the numerator shows how many such shares were taken. If n d, the fraction is called proper; if n = d or n>d, then it is incorrect. Integers are treated as fractions with a denominator of 1; for example, 2 = 2/1.

Since the fraction n/d can be interpreted as the result of division n units per d equal parts and taking one of those parts, a fraction can be thought of as the "quotient" or "ratio" of two whole numbers n And d, and understand the fraction line as a division sign. Therefore, fractions (including integers as a special case of fractions) are usually called rational numbers (from the Latin ratio - ratio).

Two fractions n/d And ( kґn)/(kґd), Where k– an integer, can be considered as equal; for example, 4/6 = 2/3. (Here n = 2, d= 3 and k= 2.) This is known as the “fundamental property of a fraction”: the value of any fraction will not change if the numerator and denominator of the fraction are multiplied (or divided) by the same number. It follows that any fraction can be written as the ratio of two relatively prime numbers.

From the interpretation of the fraction proposed above it also follows that as the sum of two fractions n/d And m/d having the same denominator, you should take the fraction ( n + m)/d. When adding fractions with different denominators, you must first convert them, using the basic property of a fraction, into equivalent fractions with the same (common) denominator. For example, n 1 /d 1 = (n 1 H d 2)/(d 1 H d 2) and n 2 /d 2 = (n 2 H d 1)/(d 1 H d 2), from where

One could do it differently and first find the least common multiple, say m, denominators d 1 and d 2. Then there are integers k 1 and k 2 , such that m = k 1 H d 1 = k 2 H d 2 and we get:

With this method the number m usually called lowest common denominator two fractions. These two results are equivalent by the definition of equality of fractions.

Product of two fractions n 1 /d 1 and n 2 /d 2 is taken equal to the fraction ( n 1 H n 2)/(d 1 H d 2).

The eight fundamental laws given above for integers are also valid if, under a, b, c understand arbitrary positive rational numbers. Also, if given two positive rational numbers n 1 /d 1 and n 2 /d 2, then we say that n 1 /d 1 > n 2 /d 2 if and only if n 1 H d 2 > n 2 H d 1 .

Positive real numbers.

The use of numbers to measure the lengths of line segments suggests that for any two given line segments AB And CD there must be some segment UV, perhaps very small, which could be postponed an integer number of times in each of the segments AB And CD. If such a common unit of length UV exists, then the segments AB And CD are called commensurate. Already in ancient times, the Pythagoreans knew about the existence of incommensurable straight segments. A classic example is the side of a square and its diagonal. If we take the side of a square as a unit of length, then there is no rational number that could be a measure of the diagonal of this square. You can verify this by arguing by contradiction. Indeed, suppose that the rational number n/d is the measure of the diagonal. But then segment 1/ d could be postponed n once diagonally and d times on the side of the square, despite the fact that the diagonal and the side of the square are incommensurable. Consequently, regardless of the choice of unit of length, not all line segments have lengths that can be expressed in rational numbers. In order for all line segments to be measured by some unit of length, the number system must be expanded to include numbers representing the results of measuring the lengths of line segments that are incommensurate with the chosen unit of length. These new numbers are called positive irrational numbers. The latter, together with positive rational numbers, form a wider set of numbers, the elements of which are called positive valid numbers.

If OR– horizontal half-line emanating from a point O, U– point on OR, different from the origin O, And OU is chosen as a unit segment, then each point P on a half-line OR can be associated with a single positive real number p, expressing the length of the segment OP. In this way we establish a one-to-one correspondence between positive real numbers and points other than O, on a half-line OR. If p And q– two positive real numbers corresponding to points P And Q on OR, then we write p>q,p = q or p depending on the location of the point P to the right of the point Q on OR, coincides with Q or located to the left of Q.

The introduction of positive irrational numbers significantly expanded the scope of applicability of arithmetic. For example, if a– any positive real number and n is any integer, then there is only one positive real number b, such that bn=a. This number b called a root n th degree of a and is written as, where the symbol in its outline resembles a Latin letter r, with which the Latin word begins radix(root) and is called radical. It can be shown that

These relationships are known as the basic properties of radicals.

From a practical point of view, it is very important that any positive irrational number can be approximated as accurately as desired by a positive rational number. This means that if r is a positive irrational number and e is an arbitrarily small positive rational number, then we can find positive rational numbers a And b, such that a and b. For example, a number is irrational. If you select e= 0.01, then ; if you choose e= 0.001, then .

Indo-Arabic number system.

Algorithms, or calculation schemes, of arithmetic depend on the number system used. It is quite obvious, for example, that the calculation methods invented for the Roman number system may differ from the algorithms invented for the current Indo-Arabic system. Moreover, some number systems may be completely unsuitable for constructing arithmetic algorithms. Historical data shows that before the adoption of the Indo-Arabic number notation system, there were no algorithms at all that made it easy enough to add, subtract, multiply and divide numbers using “pencil and paper.” Over the long years of the existence of the Indo-Arabic system, numerous algorithmic procedures specially adapted to it were developed, so that our modern algorithms are the product of an entire era of development and improvement.

In the Hindu-Arabic number system, each entry representing a number is a set of ten basic symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, called numerals. For example, the Hindu-Arabic notation for the number four hundred and twenty-three takes the form of the sequence of digits 423. The meaning of a digit in the Hindu-Arabic notation of a number is determined by its place, or position, in the sequence of digits that form this notation. In the example we gave, the number 4 means four hundreds, the number 2 means two tens and the number 3 means three units. The number 0 (zero), used to fill empty positions, plays a very important role; for example, the entry 403 means the number four hundred and three, i.e. tens are missing. If a, b, c, d, e mean individual numbers, then in the Indo-Arabic system abcde means an abbreviation for an integer

Since every integer admits a unique representation in the form

Where n is an integer, and a 0 , a 1 ,..., a n- numbers, we conclude that in a given number system, each integer can be represented in a unique way.

The Hindu-Arabic number system allows you to concisely write not only integers, but also any positive real numbers. Let us introduce the notation 10 - n for 1/10 n, Where n– an arbitrary positive integer. Then, as can be shown, any positive real number can be represented, and uniquely, in the form

This record can be compressed by writing it as a sequence of numbers

where is the sign, called the decimal point, between a 0 and b The 1 indicates where the negative powers of 10 begin (in some countries a dot is used for this purpose). This method of writing a positive real number is called decimal expansion, and a fraction presented in the form of its decimal expansion is decimal.

It can be shown that for a positive rational number, the decimal expansion after the decimal point either breaks off (for example, 7/4 = 1.75) or repeats (for example, 6577/1980 = 3.32171717...). If a number is irrational, then its decimal expansion does not break off and does not repeat. If the decimal expansion of an irrational number is interrupted at some decimal place, we obtain its rational approximation. The farther to the right of the decimal point the sign at which we terminate the decimal expansion is located, the better the rational approximation (the smaller the error).

In the Hindu-Arabic system, a number is written using ten basic digits, the meaning of which depends on their place, or position, in the notation of the number (the value of a digit is equal to the product of the digit and some power of 10). Therefore, such a system is called the decimal positional system. Positional number systems are very convenient for constructing arithmetic algorithms, and this is why the Indo-Arabic number system is so widespread in the modern world, although different symbols may be used to denote individual numbers in different countries.

Names of numbers.

The names of numbers in the Indo-Arabic system follow certain rules. The most common way of naming numbers is that the number is first divided into groups of three digits from right to left. These groups are called "periods". The first period is called the period of "units", the second - the period of "thousands", the third - the period of "millions", etc., as shown in the following example:

Each period is read as if it were a three-digit number. For example, the period 962 is read as "nine hundred sixty two". To read a number consisting of several periods, the group of digits in each period is read, starting with the leftmost one and then proceeding in order from left to right; Each group is followed by the name of the period. For example, the number above reads "seventy-three trillion eight hundred forty-two billion nine hundred sixty-two million five hundred thirty-two thousand seven hundred ninety-eight." Note that when reading and writing integers, the conjunction “and” is not usually used. The name of the unit category is omitted. Trillions are followed by quadrillions, quintillions, sextillions, septillions, octillions, nonallions, and decillions. Each period has a value 1000 times greater than the previous one.

In the Hindu-Arabic system, it is customary to follow the following procedure for reading the numbers to the right of the decimal point. Here the positions are called (in order from left to right): “tenths”, “hundredths”, “thousandths”, “ten-thousandths”, etc. A proper decimal is read as if the digits after the decimal point form a whole number, followed by the name of the position of the last digit to the right. For example, 0.752 is read as "seven hundred fifty-two thousandths." A mixed decimal is read by combining the rule for naming whole numbers with the rule for naming proper decimals. For example, 632.752 reads "six hundred thirty-two point seven hundred and fifty-two thousandths." Notice the word "integers" before the decimal point. In recent years, decimal numbers have increasingly been read more simply, for example 3.782 as "three point seven hundred and eighty two".

Addition.

Now we are ready to analyze the arithmetic algorithms that are taught in elementary school. These algorithms deal with operations on positive real numbers written as decimal expansions. We assume that elementary addition and multiplication tables have been learned by heart.

Consider the addition problem: calculate 279.8 + 5.632 + 27.54:

First, we sum up the same powers of the number 10. The number 19Х10 –1 is divided according to the distributive law into 9Х10 –1 and 10Х10 –1 = 1. We move the unit to the left and add it to 21, which gives 22. In turn, we split the number 22 into 2 and 20 = 2H10. We move the number 2H10 to the left and add it to 9H10, which gives 11H10. Finally, we divide 11H10 into 1H10 and 10H10 = 1H10 2, move 1H10 2 to the left and add it to 2H10 2, which gives 3H10 2. The final total turns out to be 312.972.

It is clear that the calculations performed can be presented in a more concise form, at the same time using it as an example of the addition algorithm that is taught in school. To do this, we write all three numbers one below the other so that the decimal points are on the same vertical:

Starting from the right, we find that the sum of the coefficients at 10 –3 is equal to 2, which we write in the corresponding column under the line. The sum of the coefficients at 10 –2 is equal to 7, which is also written in the corresponding column under the line. The sum of the coefficients for 10 –1 is 19. We write the number 9 under the line, and move 1 to the previous column, where there are ones. Taking into account this unit, the sum of the coefficient in this column turns out to be equal to 22. We write one two under the line, and move the other to the previous column, where the tens are. Taking into account the transferred two, the sum of the coefficients in this column is equal to 11. We write one unit under the line, and transfer the other to the previous column, where there are hundreds. The sum of the coefficients in this column turns out to be equal to 3, which we write below the line. The required amount is 312.972.

Subtraction.

Subtraction is the inverse of addition. If three positive real numbers a, b, c interconnected so that a+b=c, then we write a = c – b, where the symbol “-” is read as “minus”. Finding a number a according to known numbers b And c called "subtraction". Number c called minuend, number b– “subtractable”, and the number a- "difference". Since we are dealing with positive real numbers, the condition must be satisfied c > b.

Let's look at an example of subtraction: calculate 453.87 – 82.94.

First of all, borrowing a unit from the left if necessary, we transform the expansion of the minuend so that its coefficient for any power of 10 is greater than the coefficient of the subtrahend for the same power. From 4H10 2 we borrow 1H10 2 = 10H10, adding the last number to the next term in the expansion, which gives 15H10; similarly, we borrow 1Х10 0, or 10Ч10 –1, and add this number to the penultimate term of the expansion. After this, we get the opportunity to subtract the coefficients for the same powers of the number 10 and easily find the difference of 370.93.

The recording of subtraction operations can be presented in a more compressed form and you can get an example of a subtraction algorithm studied in school. We write the subtrahend under the minuend so that their decimal points are on the same vertical. Starting from the right, we find that the difference in coefficients at 10 –2 is equal to 3, and we write this number in the same column under the line. Since in the next column on the left we cannot subtract 9 from 8, we change the three in the units position of the minuend to two and treat the number 8 in the tenths position as 18. After subtracting 9 from 18 we get 9, etc., i.e. .

Multiplication.

Let's first consider the so-called “short” multiplication is multiplication of a positive real number by one of the single-digit numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, for example, 32.67ґ4. Using the law of distributivity, as well as the laws of associativity and commutativity of multiplication, we get the opportunity to break factors into parts and arrange them in a more convenient way. For example,

These calculations can be written more compactly as follows:

The compression process can be continued. We write the factor 4 under the multiplicand 32.67, as indicated:

Since 4ґ7 = 28, we write the number 8 under the line, and place 2 above the number 6 of the multiplicand. Next, 4ґ6 = 24, which, taking into account what is transferred from the column on the right, gives 26. We write the number 6 below the line, and write 2 above the number 2 of the multiplicand. Then we get 4ґ2 = 8, which in combination with the transferred two gives 10. We sign the number 0 under the line, and the one above the number 3 of the multiplicand. Finally, 4ґ3 = 12, which, taking into account the transferred unit, gives 13; The number 13 is written below the line. Putting a decimal point, we get the answer: the product is equal to 130.68.

A "long" multiplication is simply a "short" multiplication repeated over and over again. Consider, for example, multiplying the number 32.67 by the number 72.4. Let's place the multiplier under the multiplicand, as indicated:

Doing short multiplication from right to left, we get the first quotient of 13.068, the second of 65.34, and the third of 2286.9. According to the law of distributivity, the product that needs to be found is the sum of these partial products, or 2365.308. In written notation, the decimal point in partial products is omitted, but they must be correctly arranged in “steps” in order to then be summed up to obtain the complete product. The number of decimal places in the product is equal to the sum of the number of decimal places in the multiplicand and the multiplier.

Division.

Division is the inverse operation of multiplication; just as multiplication replaces repeated addition, division replaces repeated subtraction. Consider, for example, the following question: how many times is 3 contained in 14? Repeating the operation of subtracting 3 from 14, we find that 3 “enters” 14 four times, and the number 2 “remains”, i.e.

The number 14 is called divisible, number 3 – divider, number 4 – private and number 2 – the remainder. The resulting relationship can be expressed in words as follows:

dividend = (divisor ґ quotient) + remainder,

0 Ј remainder

Finding the quotient and remainder of 1400 divided by 3 by repeatedly subtracting 3 would require a lot of time and effort. The procedure could be significantly speeded up if we first subtract 300 from 1400, then 30 from the remainder, and finally 3. After subtracting 300 four times, we would get a remainder of 200; after subtracting 30 from 200 six times, the remainder would be 20; finally, after subtracting 3 from 20 six times, we get the remainder 2. Therefore,

The quotient and remainder to be found are 466 and 2, respectively. The calculations can be organized and then sequentially compressed as follows:

The above reasoning applies if the dividend and divisor are any positive real numbers expressed in the decimal system. Let's illustrate this with the example of 817.65е23.7.

First, the divisor must be converted to an integer using a decimal point shift. In this case, the decimal point of the dividend is shifted by the same number of decimal places. The divisor and dividend are arranged as shown below:

Let's determine how many times the divisor is contained in the three-digit number 817, the first part of the dividend that we divide by the divisor. Since it is estimated to be contained three times, we multiply 237 by 3 and subtract the product of 711 from 817. The difference of 106 is less than the divisor. This means that the number 237 appears in the trial dividend no more than three times. The number 3, written under the number 2 divisor below the horizontal line, is the first digit of the quotient that needs to be found. After we move down the next digit of the dividend, we get the next trial dividend 1066, and we need to determine how many times the divisor 237 fits into the number 1066; Let's say 4 times. We multiply the divisor by 4 and get the product 948, which we subtract from 1066; the difference turns out to be 118, which means that the next digit of the quotient is 4. We then subtract the next digit of the dividend and repeat the entire procedure described above. This time it turns out that the trial dividend 1185 is exactly (without a remainder) divisible by 237 (the remainder of the division finally turns out to be 0). By separating with a decimal point in the quotient the same number of digits as they are separated in the dividend (remember that we previously moved the decimal point), we get the answer: the quotient is equal to 34.5.

Fractions.

Calculations with fractions include addition, subtraction, multiplication and division, as well as simplifying complex fractions.

Adding fractions with the same denominator is done by adding the numerators, for example,

1/16 + 5/16 + 7/16 = (1 + 5 + 7)/16 = 13/16.

If fractions have different denominators, then they must first be reduced to a common denominator, i.e. convert to fractions with the same denominators. To do this, we find the least common denominator (the smallest multiple of each of the given denominators). For example, when adding 2/3, 1/6 and 3/5, the lowest common denominator is 30:

Summing up, we get

20/30 + 5/30 + 18/30 = 43/30.

Subtracting fractions is done in the same way as adding them. If the denominators are the same, then the subtraction comes down to subtracting the numerators: 10/13 – 2/13 = 8/13; If fractions have different denominators, then you must first bring them to a common denominator:

7/8 – 3/4 = 7/8 – 6/8 = (7 – 6)/8 = 1/8.

When multiplying fractions, their numerators and denominators are multiplied separately. For example,

5/6ґ4/9 = 20/54 = 10/27.

To divide one fraction by another, you need to multiply the first fraction (dividend) by the reciprocal fraction of the second (divisor) (to get the reciprocal fraction, you need to swap the numerator and denominator of the original fraction), i.e. ( n 1 /d 1)е( n 2 /d 2) = (n 1 H d 2)/(d 1 H n 2). For example,

3/4е7/8 = 3/4ґ8/7 = 24/28 = 6/7.

A mixed number is the sum (or difference) of a whole number and a fraction, such as 4 + 2/3 or 10 – 1/8. Since a whole number can be thought of as a fraction with a denominator of 1, a mixed number is nothing more than the sum (or difference) of two fractions. For example,

4 + 2/3 = 4/1 + 2/3 = 12/3 + 2/3 = 14/3.

A complex fraction is one that has a fraction in either the numerator, the denominator, or the numerator and denominator. This fraction can be converted into a simple one:

Square root.

If n r, such that r 2 = n. Number r called square root from n and is designated . At school they teach you to extract square roots in two ways.

The first method is more popular because it is simpler and easier to apply; calculations using this method are easily implemented on a desktop calculator and generalize to the case of cube roots and higher roots. The method is based on the fact that if r 1 – approaching the root, then r 2 = (1/2)(r 1 + n/r 1) – more accurate approximation of the root.

Let's illustrate the procedure by calculating the square root of some number between 1 and 100, say the number 40. Since 6 2 = 36 and 7 2 = 49, we conclude that 6 is the best approximation to in whole numbers. A more accurate approximation to is obtained from 6 as follows. Dividing 40 by 6 gives 6.6 (rounded to the first decimal place) even numbers of tenths). To get a second approximation to , we average the two numbers 6 and 6.6 and get 6.3. Repeating the procedure, we obtain an even better approximation. Dividing 40 by 6.3, we find the number 6.350, and the third approximation turns out to be (1/2)(6.3 + 6.350) = 6.325. Another repetition gives 40е6.325 = 6.3241106, and the fourth approximation turns out to be (1/2)(6.325 + 6.3241106) = 6.3245553. The process can continue as long as desired. In general, each subsequent approximation can contain twice as many digits as the previous one. So, in our example, since the first approximation, the integer 6, contains only one digit, we can keep two digits in the second approximation, four in the third, and eight in the fourth.

If the number n does not lie between 1 and 100, then you must first divide (or multiply) n to some power of 100, say, to k-th so that the product is in the range from 1 to 100. Then the square root of the product will be in the range from 1 to 10, and after it is extracted, we multiply (or divide) the resulting number by 10 k, find the required square root. For example, if n= 400000, then we first divide 400000 by 100 2 and we get the number 40, which lies in the range from 1 to 100. As shown above, it is approximately equal to 6.3245553. Multiplying this number by 10 2, we get 632.45553 as an approximate value for, and the number 0.63245553 serves as an approximate value for.

The second of the procedures mentioned above is based on the algebraic identity ( a + b) 2 = a 2 + (2a + b)b. At each step, the already obtained part of the square root is taken as a, and the part that still needs to be determined is for b.

Cube root.

To extract the cube root of a positive real number, there are algorithms similar to those for extracting the square root. For example, to find the cube root of a number n, first we approximate the root by some number r 1 . Then we build a more accurate approximation r 2 = (1/3)(2r 1 + n/r 1 2), which in turn gives way to an even more accurate approximation r 3 = (1/3)(2r 2 + n/r 2 2), etc. The procedure for constructing increasingly accurate approximations of the root can continue indefinitely.

Consider, for example, calculating the cube root of a number between 1 and 1000, say the number 200. Since 5 3 = 125 and 6 3 = 216, we conclude that 6 is the closest integer to the cube root of 200. Therefore, we choose r 1 = 6 and sequentially calculate r 2 = 5,9, r 3 = 5,85, r 4 = 5.8480. In each approximation, starting from the third, it is allowed to maintain a number of characters that is one less than twice the number of characters in the previous approximation. If the number from which you want to extract the cube root is not between 1 and 1000, then you must first divide (or multiply) it by some, say, k th, power of the number 1000 and thereby bring it into the desired range of numbers. The cube root of the newly obtained number lies in the range from 1 to 10. After it is calculated, it must be multiplied (or divided) by 10 k to get the cube root of the original number.

The second, more complex, algorithm for finding the cube root of a positive real number is based on the use of the algebraic identity ( a + b) 3 = a 3 + (3a 2 + 3ab + b 2)b. Currently, algorithms for extracting cube roots, as well as roots of higher powers, are not taught in high school, since they are easier to find using logarithms or algebraic methods.

Euclid's algorithm.

This algorithm was presented in Beginnings Euclid (c. 300 BC). It is used to calculate the greatest common divisor of two integers. For the case of positive numbers, it is formulated as a procedural rule: “Divide the larger of the two given numbers by the smaller. Then divide the divisor by the remainder and continue in this manner until the last divisor is evenly divided by the last remainder. The last of the divisors will be the greatest common divisor of the two given numbers.”

As a numerical example, consider two integers 3132 and 7200. The algorithm in this case comes down to the following steps:

The greatest common divisor is the same as the last divisor - the number 36. The explanation is simple. In our example, we see from the last line that the number 36 divides the number 288. From the penultimate line it follows that the number 36 divides 324. So, moving up from line to line, we are convinced that the number 36 divides 936, 3132 and 7200 We now claim that the number 36 is a common divisor of the numbers 3132 and 7200. Let g is the greatest common divisor of the numbers 3132 and 7200. Since g divides 3132 and 7200, from the first line it follows that g divides 936. From the second line we conclude that g divides 324. So, going down from line to line, we are convinced that g divides 288 and 36. And since 36 is a common divisor of the numbers 3132 and 7200 and is divided by their greatest common divisor, we conclude that 36 is this greatest common divisor.

Examination.

Arithmetic calculations require constant attention and are therefore prone to errors. Therefore, it is very important to check the calculation results.

1. The addition of a column of numbers can be checked by adding the numbers in the column first from top to bottom and then from bottom to top. The justification for this method of verification is the generalized law of commutativity and associativity of addition.

2. Subtraction is checked by adding the difference with the subtrahend - the minuend should be obtained. The rationale for this verification method is the definition of the subtraction operation.

3. Multiplication can be checked by rearranging the multiplicand and the multiplier. The justification for this method of verification is the law of commutative multiplication. You can check multiplication by breaking the factor (or multiplicand) into two terms, performing two separate multiplication operations and adding the resulting products - you should get the original product.

4. To check division, you need to multiply the quotient by the divisor and add the remainder to the product. You should get the dividend. The rationale for this verification method is the definition of the division operation.

5. Checking the correctness of extracting a square (or cubic) root consists of raising the resulting number by squaring (or cube) - the original number should be obtained.

A particularly simple and very reliable way to check the addition or multiplication of integers is a technique that represents a transition to the so-called. "comparisons modulo 9". Let us call “excess” the remainder of the sum of the digits used to write the number when divided by 9. Then, regarding “excesses,” two theorems can be formulated: “the excess of the sum of integers is equal to the excess of the sum of the excesses of terms,” and “the excess of the product of two integers is equal to the excess of the product of their excesses.” Below are examples of checks based on this theorem:

The method of moving to comparisons modulo 9 can also be used when testing other arithmetic algorithms. Of course, such a check is not infallible, since working with “excesses” is also subject to errors, but such a situation is unlikely.

Interest.

A percentage is a fraction whose denominator is 100; Percents can be written in three ways: as a fraction, as a decimal, or using the special percentage notation %. For example, 7 percent can be written as 7/100, as 0.07, or as 7%.

An example of the most common type of percentage problem is the following: “Find 17% of 82.” To solve this problem, you need to calculate the product 0.17ґ82 = 13.94. In products of this kind, 0.17 is called the rate, 82 is the base, and 13.94 is the share, expressed as a percentage. The three mentioned quantities are related to each other by the relation

Rate ґ base = percentage share.

If any two quantities are known, the third can be determined from this relationship. Accordingly, we get three types of problems “using percentages”.

Example 1. The number of students enrolled in this school increased from 351 to 396. By what percentage did this number increase?

The increase was 396 – 351 = 45 people. Writing the fraction 45/351 as a percentage, we get 45/351 = 0.128 = 12.8%.

Example 2. An ad in the store during a sale says “25% off all items.” What is the sale price for an item that normally sells for $3.60?

A 25% decrease in price of $3.60 means a decrease of 0.25-3.60 = $0.90; therefore, the price of the item during the sale will be $3.60 – $0.90 = $2.70.

Example 3. Money deposited in the bank at 5% per annum brought a profit of $40 per year. What amount was deposited into the bank?

Since 5% of the amount is $40, i.e. 5/100 ґ amount = $40, or 1/100 ґ amount = 8 dollars, the total amount is 800 dollars.

Arithmetic of approximate numbers.

Many numbers used in calculations arise either from measurements or estimates and can therefore only be considered approximations. It is obvious that the result of calculations performed with approximate numbers can only be an approximate number. For example, suppose that measurements of the counter surface yielded the following results (rounded to the nearest tenth of a meter): width 1.2 m, length 3.1 m; one could say that the area of ​​the counter is 1.2ґ3.1 = 3.72 m2. However, in reality the information is far from being so certain. Since the value 1.2 m only indicates that the width measurement is between 1.15 and 1.25 m, and 3.1 indicates that the length measurement is between 3.05 and 3.15 m, about the counter area we can only say that it should be greater than 1.15ґ3.05 = 3.5075, but less than 1.25ґ3.15 = 3.9375. Therefore, the only reasonable answer to the question about the area of ​​the counter is to say that it is approximately 3.7 m 2 .

Let us next consider the problem of adding the results of approximate measurements of 3.73 m, 52.1 m and 0.282 m. The simple sum is 56.112 m. But, as in the previous problem, all that can be said with certainty is that the true sum must be greater than 3.725 + 52.05 + 0.2815 = 56.0565 m and less than 3.735 + 52.15 + 0.2825 = 56.1765 m. Thus, the only reasonable answer to the question is to say that the sum is approximately equal to 56.1 m.

The two examples above illustrate some rules that are useful when working with approximate numbers. There are different ways to round numbers. One of them is to discard the lower digits of the number. Moreover, if the first digit to be discarded is more than five, then the last remaining digit must be increased by one; if it is less, then the last digit of the remaining part remains unchanged.

If the first digit to be discarded is exactly five, then the last digit to be retained is increased by one if it is odd and remains unchanged if it is even. For example, when rounding to the nearest hundredth the number 3.14159;17.7682; 28,999; 0.00234; 7.235 and 7.325 become 3.14; 17.77; 29.00; 0.00; 7.24 and 7.32.

Another method of rounding is associated with the concept of significant figures and is used when writing a number by machine. The significant digits of an approximate number are the digits in its decimal notation in order from left to right, starting with the first non-zero digit and ending with the digit that stands in place of the decimal place corresponding to the error. For example, the significant digits of the approximate number 12.1 are the numbers 1, 2, 1; approximate number 0.072 – numbers 7, 2; the approximate number 82000, written to the nearest hundred, is 8, 2, 0.

Now we will formulate the two rules for operating with approximate numbers mentioned above.

When adding and subtracting approximate numbers, each number should be rounded to the digit following the last digit of the least accurate number, and the resulting sum and difference should be rounded to the same number of digits as the least accurate number. When multiplying and dividing approximate numbers, each number should be rounded to the sign following the last significant digit of the least significant number, and the product and quotient should be rounded with the same accuracy as the least accurate number is known.

Returning to the previously considered problems, we get:

1.2ґ3.1 = 3.72 m 2 » 3.7 m 2

3.73 + 52.1 + 0.28 = 56.11 m 2 "56.1 m,

where the sign " means "approximately equal".

Some arithmetic textbooks provide algorithms for working with approximate numbers, allowing you to avoid unnecessary signs when calculating. In addition, they use the so-called. recording approximate numbers, i.e. any number is represented in the form (a number in the range from 1 to 10) ґ (power of 10), where the first factor contains only the significant digits of the number. For example, 82000 km, rounded to the nearest hundred km, would be written as 8.20ґ10 4 km, and 0.00702 cm would be written as 7.02ґ10 –3 cm.

Numbers in mathematical tables, trigonometric or logarithmic tables are approximate, written with a certain number of signs. When working with such tables, you should follow the rules for calculations with approximate numbers.

Logarithms.

By the beginning of the 17th century. The complexity of applied computing problems has increased so much that it was not possible to cope with them “manually” due to too much labor and time. Fortunately, invented in time by J. Napier at the beginning of the 17th century. logarithms made it possible to cope with the problem that arose. Since the theory and applications of logarithms are described in detail in a special article LOGARITHM, we will limit ourselves to only the most necessary information.

It can be shown that if n is a positive real number, then there is a unique positive real number x, such that 10 x = n. Number x called (regular or decimal) logarithm numbers n; conventionally it is written like this: x=log n. Thus, the logarithm is an exponent, and from the laws of operations with exponents it follows that

It is these properties of logarithms that explain their widespread use in arithmetic. The first and second properties allow us to reduce any multiplication and division problem to a simpler addition and subtraction problem. The third and fourth properties make it possible to reduce exponentiation and root extraction to much simpler operations: multiplication and division.

For ease of use of logarithms, their tables have been compiled. To compile a table of decimal logarithms, it is enough to include only logarithms of numbers from 1 to 10. For example, since 247.6 = 10 2 ґ2.476, we have: log247.6 = log10 2 + log2.476 = 2 + log2.476, and since 0.02476 = 10 –2 ґ2.476, then log0.02476 = log10 –2 + log2.476 = –2 + log2.476. Note that the decimal logarithm of a number between 1 and 10 lies between 0 and 1 and can be written as a decimal. It follows that the decimal logarithm of any number is the sum of an integer, called the characteristic of the logarithm, and a decimal fraction, called the mantissa of the logarithm. The characteristic of the logarithm of any number can be found “in the mind”; The mantissa should be found using tables of logarithms. For example, from the tables we find that log2.476 = 0.39375, hence log247.63 = 2.39375. If the characteristic of the logarithm is negative (when the number is less than one), then it is convenient to represent it as the difference of two positive integers, for example, log0.02476 = –2 + 0.39375 = 8.39375 – 10. The following examples explain this technique.

Literature:

History of mathematics from ancient times to the beginning of the 19th century., vol. 1–3. M., 1970–1972.
Serre J.-P. Arithmetic course. M., 1972
Nechaev V.I. Numerical systems. M., 1975
Daan-Dalmedico A., Peiffer J . Paths and labyrinths. Essays on the history of mathematics. M., 1986
Engler E. Elementary Mathematics. M., 1987

Size: px

Start showing from the page:

Transcript

1 LECTURE 2 CALCULATION OF THE GREATEST COMMON DIVISOR Euclid's algorithm When working with large composite numbers, their decomposition into prime factors is usually unknown. But for many applied problems in number theory, finding the factorization of a number is an important, frequently encountered practical problem. In number theory, there is a relatively fast way to calculate the gcd of two numbers, which is called the Euclidean algorithm. Algorithm 1. Euclidean 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 Euclidean algorithm stops and the number d it produces is the greatest common divisor of the numbers a and b. Proof . By the theorem on division with 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 below. Such a sequence cannot be infinite, therefore, the Euclidean algorithm stops. Binary Euclidean algorithm Binary Euclidean algorithm for calculating GCD turns out to be faster when implementing this

2 algorithms on a computer because it uses the binary representation of numbers a and b. Euclidean's binary 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 Euclidean 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 exist 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 Euclidean algorithm. 1. Define = 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 ; = t q; // = x i for the right side = x i+1 for the right; //t = y i-1 ; = t q; 5. Return to step Determine x = x 0, y = y 0, d = αx + βy. Variant of the extended Euclidean algorithm Input. Integers a, b;< 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 occurs 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, аx 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 is the gcd of numbers a and b. Stage I of the calculation sequence. 1. Determine = 1, = 0, = 0, = 1, α = 1769, β = Quotient q = a/b = 1769/551 = 3, and remainder 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 r is 0, we return to step 2. Stage II of the calculation sequence. 1. Parameter values: 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 r is 0, we return to step 2. Stage III of the calculation sequence. 1. Parameter values: 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 parameter values: a = 87, b = 29, = 4, = 5, = 13, = Since the remainder of the division r is 0, we return to step 2. Stage IV of the calculation sequence. 1. Parameter values: 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. We calculate the GCD using the formula d = αx + βy, where x = x 0 = 5, y = y 0 = 16, α = 1769, β = 551. Substituting the values ​​of the parameters, we get d = αx + βy = = = 29 The extended Euclidean algorithm can also be implemented in binary form. Algorithm 4. Extended binary Euclidean algorithm. Entrance. Integers a, b;< 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, х, у.

Solving equations in integers Linear equations. Brute-force method Example. Rabbits and pheasants are sitting in a cage. They have a total of 8 legs. Find out how many of both are in the cage. List all solutions. Solution.

Lesson 7 The 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

Subject. Fundamentals of elementary number theory and applications - Theoretical material. A set of modulo residues, properties of comparisons. Let the natural number be greater. Let Z denote the set of all classes

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

Chapter 2 Integers, rational and real numbers 2.. Integers The numbers, 2, 3,... are called natural numbers. 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 The manual does not outline the theory of numbers, but provides the minimum tools from this theory that will be required in the future to study the cryptographic systems used

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

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

LECTURE 12 COMPARISONS OF THE SECOND DEGREE MODULE AND QUADRATIC RESULTS 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)

Directions, solutions, answers INTEGER EQUATIONS. Equation with one unknown.. Solution. Let's plug it into the equation. We obtain 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 the 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: NU Zolotykh Recorded by: E Zamaraeva?? September 00 Contents Quadratic residues and non-residues Legendre symbol Properties of the Legendre symbol Quadratic reciprocity law

GOU boarding school ""Intellectual"" Research work in mathematics on the topic: "On representability natural numbers in the form of a linear combination with integer coefficients"

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

4 Number Theory 4 Integers 7 Definition Let, b Z Then divide 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 integers

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

009-00 school year. 6, 9 grades Mathematics. Elements of number theory. 4. Calculation of the greatest common divisor and least common multiple Let's keep the notation from the section. For a natural number n, write 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 Fields of residues modulo prime

5 Solving equations in integers Solving even such simple equations as a linear equation with one unknown has its own 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. The purpose of the work is to create a program using the Euclidean algorithm that determines the greatest for numbers a and b

Section 1. Mathematical foundations of cryptography 1 Definition of a field A finite field GF q (or 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 Problems for grade 11 Solution to problem 1 First, 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. AES STANDARD. RIJNDAEL ALGORITHM. The AES (Advnced Encrypton Stndrd) standard is a new single-key encryption standard that replaces the DES standard. Rjndel algorithm (Rhein 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 senior coefficient, a

1 Euclid's algorithm and its complexity Definition 1. The 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 the numbers a and b is their common divisor,

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

LECTURE 3 CALCULATING SQUARE ROOTS MODULE The case of a simple modulus Consider the comparison x a mod p, () where the number p is prime and the integer a is not divisible by p Calculating the solution x of this equation is

Colloquium program in discrete mathematics (main stream) At the beginning of the colloquium you will receive a ticket containing three questions: a question on knowledge of definitions, a problem, a question on knowledge of proofs.

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 sufficiently voluminous book in which arithmetic was presented independently of geometry was Introduction to Arithmetic by Nicomacheus (Oc. AD). In the history of arithmetic, its role is comparable to the role

A brief introduction to the beginnings of elementary number theory Denis Kiriyenko Summer computer school, January 1, 2009 Integer division Let two integers a and b be given, b 0. The integer quotient of division

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. An equation of the form 0, P () 0, some real numbers is called algebraic. 0 0 In this case, the variable quantity is called unknown, and the numbers 0, coefficients

Lecture 6 Elements of number theory 1 Problem. Continue the number series 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 coefficients of the polynomial, and are called the leading coefficient of the polynomial 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 grade, Mathematics (textbook Makarychev) 2018-2019 academic year The topic of the module is “Integers. Divisibility of numbers. Degree with an integer indicator” The test tests the theoretical and practical parts. TOPIC Know

Lecture INTEGRATION OF RATIONAL FRACTIONS Rational fractions Integration of simple rational fractions Decomposition of rational fractions 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, note that if N pq, where p and q are prime numbers, then the number of natural numbers,

Chapter Integers Theory of Divisibility Integers are the 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 Economic University Yu. B. Melnikov Polynomials Section of the electronic textbook to accompany the lecture Ed. 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 Euclidean algorithm, modulo inverse, modulo exponentiation. Public key cryptography, RSA protocol. Probabilistic

5. Bose-Chaudhuri-Hocquenghem codes Correction properties of cyclic codes can be determined on the basis of two theorems. Theorem 1. For any m and t there is a cyclic code of length n = 2 m 1, with multiplicity

MODULAR ARITHMETICS In some applications it is convenient to perform arithmetic operations on integers specified in what is called modular notation. This representation assumes that the integer

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

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

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

Topic 3. Elements of algebraic and analytical number theory Theoretical material 1. Continued fractions. A 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 the variable, a are the numerical coefficients (=,.k), and. Any non-zero number can be considered

Penza State Pedagogical University named after V. G. Belinsky M. V. Glebova V. F. Timerbulatova PRACTICAL LESSONS IN ALGEBRA OF POLYNOMIALS Educational and methodological manual Penza Published by

DIVISION OF INTEGER NUMBERS WITH A REMAINDER Let m be an integer and n a natural number. If m > n and m is not divisible by n, then it is possible to divide m by n with a remainder. Definition 3 For any integer m and any

Avdoshin S.M., Savelyeva A.A. Algorithm for solving systems of linear equations in residue rings An effective algorithm for solving systems of linear equations in residue rings has been developed, equivalent in complexity

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 from S S to S That is, it is a rule that assigns to each ordered pair of elements from S a certain

/E Elements of number theory and. rochev August 28, 2018 Table of contents Table of contents i 1 Integers 1 1.1 Introductory problems................................... ..... 1 1.2 Greatest common divisor....................................

Chapter Integers, 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 factors of the number 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

Subject. 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 Computer Science Elements of Higher Mathematics Educational and methodological complex for secondary vocational education students studying using distance technologies Module Theory of Limits Compiled by: Associate Professor

Section 2. Numerical-theoretic methods in cryptography Independent work assignment Study algorithms that are widely used in cryptography. Elements of number theory: extended Euclidean algorithm;

The thematic plan was compiled on the basis of 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. Calculation of sums and the method of generating functions (final case). Polynomial coefficients. Estimates of binomial and polynomial coefficients. Amount estimates

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 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 are natural numbers, 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).