Presentation for the Euclidean algorithm class. Presentation on the topic "Euclidean algorithm". Block diagram of the Euclidean algorithm

Slide 2

The Euclidean algorithm is an algorithm for finding the greatest common divisor (GCD) of two non-negative integers. Euclid (365-300 BC) Ancient Greek mathematicians called this algorithm ἀνθυφαίρεσις or ἀνταναίρεσις - “mutual subtraction”.

Slide 3

GCD calculation

GCD = The greatest common divisor of two natural numbers is the largest number that divides both original numbers without leaving a remainder. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Replace the larger of the two numbers with the difference of the larger and smaller until they are equal. This is GCD. GCD (18, 45)= GCD (18, 45-18)= GCD (18, 27)=GCD (18, 9)= =GCD(9,9)=9 Example:

Slide 4

Slide 5

program Evklid; var m, n: integer; begin writeln("vved 2 numbers"); readln(m,n); while mn do begin if m>n then m:=m-n else n:=n-m; end; write("nod=",m); readlnend.

Slide 6

0.Run the Evklid program on your computer. Test it with values M=32, N=24; M=696, N=234. 1. Check whether two given numbers are relatively prime. Note. Two numbers are called relatively prime if their greatest common divisor is 1. 2. Find the least common multiple (LCD) of numbers n and m if LCM(n, m) = n * m / GCD (n, m). 3. Given natural numbers m and n. Find natural numbers p and q that have no common divisors such that p / q = m / n. 4. Find the gcd of three numbers. Note. GCD(a, b, c)= GCD(GCD(a, b), c) Problems

Slide 7

EUCLID, ancient Greek mathematician. Worked in Alexandria in the 3rd century. BC e. The main work "Principles" (15 books), containing the foundations of ancient mathematics, elementary geometry, number theory, the general theory of relations and the method of determining areas and volumes, which included elements of the theory of limits. He had a huge influence on the development of mathematics. Works on astronomy, optics, music theory.

View all slides

To use presentation previews, create a Google account and log in to it: https://accounts.google.com

Slide captions:

EUCLID'S ALGORITHM EUCLID, ancient Greek mathematician. Worked in Alexandria in the 3rd century. BC e. The main work "Principles" (15 books), containing the foundations of ancient mathematics, elementary geometry, number theory, the general theory of relations and the method of determining areas and volumes, which included elements of the theory of limits. He had a huge influence on the development of mathematics. Works on astronomy, optics, music theory. Euclid (365-300 BC)

EUCLID'S ALGORITHM The Euclid's algorithm is an algorithm for finding the greatest common divisor (GCD) of two non-negative integers. Euclid (365-300 BC) Ancient Greek mathematicians called this algorithm ἀνθυφαίρεσις or ἀνταναίρεσις - “mutual subtraction”.

Calculating GCD GCD = the greatest common divisor of two natural numbers is the largest number that divides both original numbers without leaving a remainder. GCD(a, b)= GCD(a-b, b)= GCD(a, b-a) Replace the larger of the two numbers with the difference of the larger and smaller until they are equal. This is GCD. GCD (18, 45) = GCD (18, 45-18) = GCD (18, 27) = GCD (18, 9) = =GCD(9,9)=9 Example:

STEP Operation M N Condition 1 Input M 48 2 Input N 18 3 M  N 48 18, yes 4 M>N 48>18, yes 5 M:=M-N 30 6 M  N 30  18, yes 7 M>N 30 >18, yes 8 M:=M-N 12 9 M  N 12 18, yes 10 M>N 12 >18, no 11 N:=N-M 6 12 M  N 12  6, yes 13 M>N 12 >6 , yes 14 M:=M-N 6 15 M  N 6  6, no 16 Output M

program Evklid ; var m, n: integer; begin writeln("vved 2 numbers"); readln(m,n); while mn do begin if m>n then m:=m-n else n:= n-m ; end; write("nod=",m); readlnend.

0.Run the Evklid program on your computer. Test it with values M=32, N=24; M=696, N=234. 1 . Check whether two given numbers are relatively prime. Note. Two numbers are said to be relatively prime if their greatest common divisor is 1.2. Find the least common multiple (LCD) of numbers n and m if LCM(n, m) = n * m / GCD(n, m). 3. Given natural numbers m and n. Find natural numbers p and q that have no common divisors such that p / q = m / n. 4. Find the gcd of three numbers. Note. GCD(a , b , c)= GCD(GCD(a , b), c) Problems

Preview:

Topic: "Euclidean Algorithm"

Lesson objectives:

Educational:

learn to apply the Euclidean algorithm to find the gcd of two and three numbers
consolidate skills in using algorithmic structures “Branching” and “Cycle”
gain experience in writing and debugging programs in the Pascal programming language

Educational:

formation of independence and responsibility when learning new material

Developmental:

development of attention and analytical thinking

Lesson plan:

Organizing time
Updating knowledge
Explanation of a new topic
Practical part
Summing up the lesson
Homework.

Organizing time

Greetings. Who is absent. Number. Lesson topic. Homework questions.

Updating knowledge.

Questions:

What types of algorithmic structures do you know?

What structure is called linear? (Bl-sh)

Which structure is called branching? (Bl-sh)

What structure is called cyclic? (Bl-sh)

What types of cycles do you know?

How is a loop with a known number of repetitions implemented in the Pascal programming language?

How is a loop with an unknown number of repetitions implemented in the Pascal programming language?

Explaining a new topic (presentation)

About Euclid;

The idea of the Euclid algorithm

The idea of this algorithm is based on:

1. 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.

Proof: let K be the common divisor of M and 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.

2.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.

Block diagram of the Euclidean algorithm

Pascal program

program Evklid;

var m, n: integer;

begin

writeln("vved 2 numbers");

readln(m,n);

While mn do

Begin

If m>n

Then m:=m-n

Else n:=n-m;

End;

Write("nod=",m);

readln

end.

Practical part

Questions and tasks:

Run the Evklid program on your computer. Test it on values M = 32, N = 24; M = 696, N = 234.
Check whether two given numbers are relatively prime. Note. Two numbers are said to be relatively prime if their greatest common divisor is 1.

Summing up the lesson

Today in class we learned about the Euclid algorithm, which allows us to find the gcd of two non-negative integers, and we wrote a program in the Pascal programming language that implements this algorithm. You will receive a homework assignment in which you will apply this algorithm to find the gcd of three numbers and the gcd of two numbers.

Homework.

1. 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)

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

A  B = GCD(A, B)  GCD(A, B)

Topic: Euclidean algorithm for finding GCD.

Goals:repeat the previously studied topics Greatest common divisor and least common multiple, introduce the Euclidean algorithm.

Learning objectives are to repeat the concepts of Greatest Common Divisor and Least Common Multiple, the rule for finding them. Introduce the Euclidean algorithm. Fix the Euclidean algorithm by solving the corresponding tasks.

Development tasks are the development of logical thinking, attention, speech memory, the ability to independently discover new knowledge, mathematical curiosity, cognitive interest in the subject.

The objectives of education are to cultivate a culture of mathematical thinking, mutual assistance, perform self-tests and analyze one’s mistakes.

Working on cards

Find the GCD or LCM of numbers and decipher the phrase:

300

D: GCD(33.88)

G: NOK(9.40)

A: NOC(14.42)

E: GCD(48,18)

R: NOK(17.5)

C: GCD(48,24)

K: GCD (72,12)

L: GCD(20,14)

E: GCD(30,18)

M: NOK(25.12)

T: NOK(4,8,16)

N: NOK(12.40)

B: GCD(18.35)

A: GCD(17,34)

I: GCD(102.68)

E: GCD(18,12)

Write down the remaining pairs of numbers in the last table

Answers:

300

ABOUT

AND

D: GCD(33.88)=11

G: NOC(9,40)=360

A: NOC(14,42)=42

E: GCD(48,18)=6

R: NOC(17.5)=85

C: GCD(48,24)=24

K: GCD (72,12)=12

L: GCD(20,14)=2

E: GCD(30,18)=6

M: LOC(25,12)=300

T: NOC(4,8,16)=16

N: NOC(12,40)=120

B: GCD(18,35)=1

A: GCD(17,34)=17

I: GCD(102.68)=34

E: GCD(18,12)=6

Guess 2 more words

What can you say about the numbers in the last table? They are relatively simple, i.e. If we factor these numbers into prime factors, they will not have the same factors. How to find the gcd of such numbers? Node of such numbers = 1. How to find the LCM? To find the LCM you need to multiply these numbers by each other.

The first column contains pairs of numbers in which one of them is not divisible by the other. Those. the remainder is not 0.

How did you find the GCD and LCM of such numbers? (By factoring these numbers into prime factors)

LCM(12,40)=2 3 *3*5=120

Let’s remember the rule for finding GCD and LCM, find and check the formula LCM(a,b)=(a*b):GCD(a,b)

3 *3*11=264

LCM(a,b)=(a*b):GCD(a,b)

264=(33*88):11=3*88=264

LCM(20,14)=2 2 *5*7=140

LCM(a,b)=(a*b):GCD(a,b)

140=(20*14):2=10*14=140

GCD(12,40)=2 2 =4

LCM(a,b)=(a*b):GCD(a,b)

120=(12*40):4=3*4=120

Learning a new topic:

GCD of which pairs of numbers resulted in 6?

6=GCD(48,18)=GCD(30,18)=GCD(12,18)

What did you notice? How did you get 30? 48-18

How did you get 12? 30-18

When a>b = gcd (a-b,c)

Those. GCD(a,c) When b>a = GCD(a,b-a)

Who can continue this equality?

6=GCD(48,18)=GCD(30,18)=GCD(12,18) = GCD(12,6)=GCD(6,6)=6

The Euclidean algorithm is based on this rule.

Euclidean algorithm- effective for finding two . The algorithm is named after the person who first described it in books VII and X.

In its simplest case, Euclidean's algorithm is applied to a pair of positive integers and forms a new pair that consists of the smaller number and between the larger and smaller number. The process is repeated until the numbers are equal. The number found is the greatest common divisor of the original pair.

Ancient Greek mathematicians called this algorithm “mutual subtraction.”

The essence of this method is as follows: subtract the smaller number from the larger number until the numbers are equal, replacing the larger number with the difference. As soon as this happens, the GCD is found. (Example on the board – numbers 48 and 18)

The first question is: are these numbers equal? No, they are not equal, therefore we subtract the smaller from the larger 48-18 = 30. 30 is not equal to 18, which means 30-18 = 12, 18-12 = 6, 12-6 = 6. That is, we perform these actions until the numbers are equal. Therefore gcd(48,18)=6

Knowing the gcd of numbers 48 and 18, find the gcd. NOC(48,18)=(48*18):6=48*3=144

Let's find using the Euclidean algorithm GCD(102;68).

We'll find GCD (357;273)

Here we subtracted the number 84 3 times and the number 21 three times.

How, without making subtractions, can you find out how many subtractions there will be in one series, and what difference will be the result? What cases need to be considered? ( Note: remember about division.)

The general rule can be formulated as follows: if the number a not divisible by b, then it is replaced by its remainder when divided by b(when a< b this remainder is equal a); If a divided by b, then replace it with the number b. Exactly the same rule, with rearrangement a And b, also valid for b. Larger number divide by the smaller one, then the smaller one by the first remainder, then the first remainder by the second remainder, etc., until you get 0. Thenthe last remainder not equal to 0 is gcd .

Find GCD (357;273).

357 273 273 84 84 21 GCD (357;273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

gcd(357.273)=gcd(273.84)=gcd(84.21)=21

The convenience of the Euclidean algorithm becomes especially noticeable if we use the table form:

In this tablet, first write down the original numbers, divide in your head, writing down the remainders on the right, and the quotients at the bottom, until the process is completed. The last divisor is the gcd.

Thus, the greatest common divisor of two numbers is the last non-0 remainder when dividing the larger number by the smaller number., that isif a = b *q + r, then gcd(a; b) = gcd(b; r)

This sequence of operations is called Euclidean algorithm.

1) Using the Euclidean algorithm, find the gcd of numbers:

A) 703, 481, B) 2112 and 1680; B) 5075 and 1450

GCD(703,481)=37

GCD(2112,1680)=48

GCD(5075,1450)=

Check the results on your computer.

Assign the children on the computer to find GCD and LCM for three numbers using a program for finding GCD and LCM.

GCD(150, ____) = ____

GCD(450,315,135)=____

GCD (135, ____) = ____

GCD(2160,1350,1080)=____

GCD(1080, ____) = ____

GCD(5300,3180,2120)=____

GCD(2120, ____) = ____

(To find the gcd of three or more numbers, first find the gcd of any two of them, then the gcd of the found divisor and the third given number.

and the third given number.

7. Checking the results on a computer. Independent problem solving.

1) Identical gifts were prepared for the students in the class. All gifts included 120 chocolates, 280 sweets, and 320 nuts. How many students are in first grade if it is known that there are more than 30 of them?

Answer:________________________

2) There are three passenger trains at the station: the first has 418 seats in compartment cars, the second has 494, and the third has 456. How many compartment cars are there in each train, if each car has the same number of seats and their total number is more than 20? Answer _________________________

3) From 156 tea roses, 234 white and 390 red roses were made into bouquets, and in all the bouquets there were equal numbers of roses of each type and the number of such bouquets was more than 50. How many bouquets were made from these roses and how many roses of each type were in one bouquet? Answer_________________

Lesson summary. What method of finding GCD and LCM did we get acquainted with in the lesson? Euclid's algorithm. What is another name for this method? (subtraction method). How has this method been improved? Using division, a larger number is divided by a smaller number, then a smaller number by the first remainder, then the first remainder by the second remainder, etc., until they get 0. The last non-zero remainder is the gcd of the numbers.

Slide 1

Slide 2

Slide 3

Slide 4

STEP Operation M N Condition 1 InputM 48 2 InputN 18 3 M N 48 18,yes 4 M>N 48>18,yes 5 M:=M-N 30 6 M N 30 18,yes 7 M>N 30>18,yes 8 M:= M-N 12 9 M N 12 18, yes 10 M>N 12>18, no 11 N:=N-M 6 12 M N 12 6, yes 13 M>N 12>6, yes 14 M:=M-N 6 15 M N 6 6, no 16 OutputM

Slide 5

program Evklid; var m, n: integer; begin writeln("vved 2 numbers"); readln(m,n); while mn do begin if m>n then m:=m-n else n:=n-m; end; write("nod=",m); readlnend.

Slide 6

0.Run the Evklid program on your computer. Test it with values M=32, N=24; M=696, N=234. 1. Check whether two given numbers are relatively prime. Note. Two numbers are said to be relatively prime if their greatest common divisor is 1. 2. Find the least common multiple (LCD) of numbers n and m if LCM(n, m) = n * m / GCD (n, m). 3. Given natural numbers m and n. Find natural numbers p and q that have no common divisors such that p / q = m / n. 4. Find the gcd of three numbers. Note. GCD(a, b, c)= GCD(GCD(a, b), c) Problems

Slide 7

Statement of the Problem Consider the following problem: you need to create a program for determining 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 divisors: 2, 3, 6. The greatest common divisor is the number 6. This is written as follows: GCD(12,18) = 6. Let us denote the initial data as M and N. The problem statement is as follows : Given: M, N Find: GCD(M,N).

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 and the smaller number." title="The idea of the 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 and the smaller number." class="link_thumb"> 4 !} The idea of the 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 and the smaller number. 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 and the smaller number."> 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 and smaller number."> 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 and the smaller number." title="The idea of the 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 and the smaller number."> title="The idea of the 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 and the smaller number."> !}

N). This means that M = mK, N = pK, 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" title="Proof Let K be a common divisor of M and. N (M>N). This means that M = mK, N = pK, 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" class="link_thumb"> 5 !} Proof Let K be a common divisor of M and. N (M>N). This means that M = mK, N = pK, 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. Hence: GCD(M,N) = GCD(M - N,N). The second obvious property: GCD(M,M) = M. N). This means that M = mK, N = pK, 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 "> N). This means that M = mK, N = pK , 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. Hence: GCD(M,N) = GCD(M - N,N). The second obvious property: GCD(M,M) = M."> N). This means that M = mK, N = pK, 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" title="Proof Let K be a common divisor of M and. N (M>N). This means that M = mK, N = pK, 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"> title="Proof Let K be a common divisor of M and. N (M>N). This means that M = mK, N = pK, 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"> !}

Pascal program Program Evklid; var M, N: integer; begin writeln("Enter M and N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end. N then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end."> N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="Pascal program Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N then M:=M-N else N:=N-M end; write("HOD=",M) end." title="Pascal program Program Evklid; var M, N: integer; begin writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}