Summary and presentation of the lesson Euclidean algorithm for finding nodes. Presentation on the topic "Euclid's algorithm" Topic: Euclid's algorithm for finding GCD

To use the preview of presentations, create a Google account (account) and sign in: https://accounts.google.com

Slides captions:

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

EUCLID'S ALGORITHM 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".

Calculation GCD GCD = the greatest common divisor of two natural numbers is the largest number by which both original numbers are divisible without a remainder. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) Replace the larger of the two numbers with the difference between the larger and smaller until they are equal. This is NOD. 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 chisla"); readln(m,n); while mn do begin if m>n then m:=m-n else n:= n-m ; end; write("nod=",m); readln end.

0.Run the Evklid program on the computer. Test it with M=32, N=24; M=696, N=234. one . Check if two given numbers are coprime. Note. Two numbers are said to be coprime if their greatest common divisor is 1. 2 . Find the least common multiple (LCM) of numbers n and m if LCM(n, m) = n * m / gcd(n, m). 3 . Natural numbers m and n are given. 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) Tasks

Preview:

Topic: "Euclid's Algorithm"

Lesson Objectives:

1. Educational:

1. learn how to use the Euclid algorithm to find the gcd of two and three numbers
2. consolidate skills in using the algorithmic structures "Branching" and "Cycle"
3. gain experience in writing and debugging programs in the Pascal programming language

1. Educational:

1. formation of independence and responsibility in the study of new material

1. Developing:

1. development of attention and analytical thinking

Lesson plan:

1. Organizing time
2. Knowledge update
3. Explanation of the new topic
4. Practical part
5. Summing up the lesson
6. Homework.

Organizing time

Greetings. Who is absent. Number. Lesson topic. Questions on homework.

Knowledge update.

Questions:

What types of algorithmic structures do you know?

What is a linear structure? (Bl-sh)

What is a branching structure? (Bl-sh)

What is a cyclic structure? (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?

Explanation of a new topic (presentation)

About Euclid;

Idea of ​​Euclid's 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 a common divisor of M and N (M > N). This means that M \u003d mK, N \u003d nK, where m, n are natural numbers, and m > n. Then M - N \u003d K (m - n), which implies that K is a divisor of the number M - N. Hence, 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, Euclid's algorithm looks like this:

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

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

3) return to the implementation of paragraph 1.

Block diagram of the Euclid algorithm

Program in JS Pascal

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:

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

Summing up the lesson

Today in the lesson we got acquainted with the Euclid algorithm, which allows us to find the GCD of two non-negative integers, we wrote a program in the Pascal programming language that implements this algorithm. At home, you will receive a task in which you will apply this algorithm to find the GCD of three numbers and the LCM 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. Write a program for finding the least common multiple (LCM) of two numbers using the formula:

A  B \u003d GCD (A, B)  LCM (A, B)

slide 1

slide 2

slide 3

slide 4

slide 5

slide 6

Slide 7

slide 2

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

slide 3

GCD calculation

GCD = the greatest common divisor of two natural numbers is the largest number by which both original numbers are divisible without a remainder. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Replace the larger of the two numbers with the difference between the larger and smaller numbers until they are equal. This is NOD. 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); readln end.

slide 6

0.Run the Evklid program on the computer. Test it with M=32, N=24; M=696, N=234. 1. Check if two given numbers are coprime. Note. Two numbers are called coprime if their greatest common divisor is 1. 2.Find the least common multiple (LCM) of numbers n and m if LCM(n, m) = n * m / gcd(n, m). 3. Natural numbers m and n are given. Find natural numbers p and q without 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) Tasks

Slide 7

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

View all slides

Statement of the Problem Consider the following problem: it is required to write 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. 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="(!LANG: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="(!LANG: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), whence it follows that K is a divisor of M - N. Hence, all common divisors of M and N are divisors" title="(!LANG: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), whence it follows that K is a divisor of the number M - N. Hence, 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), whence it follows that K is a divisor of the number M - N. Hence, 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 \u003d K (m - n), whence it follows that K is a divisor of the number M - N. Hence, all common divisors of the numbers M and N are divisors "\u003e N). This means that M \u003d mK, N \u003d pK , where m, n are natural numbers, and m > n. Then M - N = K(m - n), whence it follows that K is a divisor of the number M - N. Hence, 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), whence it follows that K is a divisor of M - N. Hence, all common divisors of M and N are divisors" title="(!LANG: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), whence it follows that K is a divisor of the number M - N. Hence, 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 \u003d K (m - n), which implies that K is a divisor of the number M - N. Hence, all common divisors of the numbers M and N are divisors"> !}

Program in Pascal 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="(!LANG: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="(!LANG: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."> !}