Pagtatanghal sa paksa ng Euclidean algorithm. Paksa: Euclidean algorithm para sa paghahanap ng GCD

Paksa: Euclidean algorithm para sa paghahanap ng GCD.

Mga layunin:ulitin ang mga naunang pinag-aralan na paksa Pinakamalaking common divisor at least common multiple, ipakilala ang Euclidean algorithm.

Ang mga layunin sa pag-aaral ay ulitin ang mga konsepto ng Greatest Common Divisor at Least Common Multiple, ang panuntunan para sa paghahanap sa kanila. Ipakilala ang Euclidean algorithm. Ayusin ang Euclidean algorithm sa pamamagitan ng paglutas ng mga kaukulang gawain.

Ang mga gawain sa pag-unlad ay ang pagbuo ng lohikal na pag-iisip, atensyon, memorya ng pagsasalita, ang kakayahang independiyenteng tumuklas ng bagong kaalaman, pag-usisa sa matematika, interes sa pag-iisip sa paksa.

Ang mga layunin ng edukasyon ay upang linangin ang isang kultura ng matematikal na pag-iisip, tulong sa isa't isa, magsagawa ng mga pagsubok sa sarili at pag-aralan ang mga pagkakamali ng isang tao.

Nagtatrabaho sa mga card

Hanapin ang GCD o LCM ng mga numero at tukuyin ang parirala:

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: NOC(12.40)

B: GCD(18.35)

A: GCD(17,34)

I: GCD(102.68)

E: GCD(18,12)

Isulat ang natitirang mga pares ng mga numero sa huling talahanayan

Mga sagot:

300

TUNGKOL SA

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: NOC(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

Hulaan ang 2 pang salita

Ano ang masasabi mo sa mga numero sa huling talahanayan? Ang mga ito ay medyo simple, i.e. Kung isasaalang-alang natin ang mga numerong ito sa mga pangunahing kadahilanan, hindi sila magkakaroon ng parehong mga kadahilanan. Paano mahahanap ang gcd ng mga naturang numero? Node ng naturang mga numero = 1. Paano mahahanap ang LCM? Upang mahanap ang LCM kailangan mong i-multiply ang mga numerong ito sa bawat isa.

Ang unang hanay ay naglalaman ng mga pares ng mga numero kung saan ang isa sa mga ito ay hindi nahahati ng isa. Yung. ang natitira ay hindi 0.

Paano mo nahanap ang GCD at LCM ng mga naturang numero? (Sa pamamagitan ng pag-factor ng mga numerong ito sa prime factor)

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

Tandaan natin ang panuntunan para sa paghahanap ng GCD at LCM, hanapin at suriin ang formula na 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

Pag-aaral ng bagong paksa:

GCD kung aling mga pares ng mga numero ang nagresulta sa 6?

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

Ano ang napansin mo? Paano ka nakakuha ng 30? 48-18

Paano ka nakakuha ng 12? 30-18

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

Yung. GCD(a,c) Kapag b>a = GCD(a,b-a)

Sino ang maaaring magpatuloy sa pagkakapantay-pantay na ito?

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

Ang Euclidean algorithm ay batay sa panuntunang ito.

Euclidean algorithm- mabisa para sa paghahanap ng dalawa. Ang algorithm ay ipinangalan sa taong unang inilarawan ito sa mga aklat VII at X.

Sa pinakasimpleng kaso nito, ang algorithm ng Euclidean ay inilapat sa isang pares ng mga positibong integer at bumubuo ng isang bagong pares na binubuo ng mas maliit na numero at sa pagitan ng mas malaki at mas maliit na numero. Ang proseso ay paulit-ulit hanggang ang mga numero ay pantay. Ang numerong natagpuan ay ang pinakamalaking karaniwang divisor ng orihinal na pares.

Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito na "mutual subtraction."

Ang kakanyahan ng pamamaraang ito ay ang mga sumusunod: ibawas ang mas maliit na numero mula sa mas malaking bilang hanggang sa magkapantay ang mga numero, palitan ang mas malaking numero ng pagkakaiba. Sa sandaling mangyari ito, makikita ang GCD. (Halimbawa sa pisara - mga numero 48 at 18)

Ang unang tanong ay: pantay ba ang mga numerong ito? Hindi, hindi sila pantay, kaya ibawas natin ang mas maliit sa mas malaking 48-18 = 30. Ang 30 ay hindi katumbas ng 18, na nangangahulugang 30-18 = 12, 18-12 = 6, 12-6 = 6. Ibig sabihin, ginagawa namin ang mga pagkilos na ito hanggang sa magkapantay ang mga numero. Samakatuwid gcd(48,18)=6

Alam ang gcd ng mga numero 48 at 18, hanapin ang gcd. NOC(48,18)=(48*18):6=48*3=144

Hanapin natin gamit ang Euclidean algorithm GCD(102;68).

Hahanapin natin GCD (357;273)

Dito namin ibinawas ang bilang 84 3 beses at ang bilang 21 ng tatlong beses.

Paano, nang hindi gumagawa ng mga pagbabawas, maaari mong malaman kung gaano karaming mga pagbabawas ang magkakaroon sa isang serye, at anong pagkakaiba ang magiging resulta? Anong mga kaso ang kailangang isaalang-alang? ( Tandaan: tandaan ang tungkol sa dibisyon.)

Ang pangkalahatang tuntunin ay maaaring buuin tulad ng sumusunod: kung ang numero a hindi mahahati ng b, pagkatapos ay papalitan ito ng natitira kapag hinati ng b(kailan a< b ang natitira ay pantay a); Kung a hinati ng b, pagkatapos ay palitan ito ng numero b. Eksaktong parehong panuntunan, na may muling pagsasaayos a At b, wasto din para sa b. Mas malaking numero hatiin sa pamamagitan ng mas maliit na isa, pagkatapos ay ang mas maliit sa pamamagitan ng unang natitira, pagkatapos ay ang unang natitira sa pangalawang natitira, atbp., hanggang sa makakuha ka ng 0. Pagkataposang huling natitirang hindi katumbas ng 0 ay gcd .

Hanapin ang 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

Ang kaginhawahan ng Euclidean algorithm ay nagiging lalong kapansin-pansin kung gagamitin natin ang form ng talahanayan:

Sa tablet na ito, isulat muna ang mga orihinal na numero, hatiin sa iyong ulo, isulat ang mga natitira sa kanan, at ang mga quotient sa ibaba, hanggang sa makumpleto ang proseso. Ang huling divisor ay ang gcd.

Kaya, ang pinakamalaking karaniwang divisor ng dalawang numero ay ang huling hindi-0 na natitira kapag hinahati ang mas malaking bilang sa mas maliit na bilang., yan aykung a = b *q + r, pagkatapos ay gcd(a; b) = gcd(b; r)

Ang pagkakasunud-sunod ng mga operasyon na ito ay tinatawag Euclidean algorithm.

1) Gamit ang Euclidean algorithm, hanapin ang gcd ng mga numero:

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

GCD(703,481)=37

GCD(2112,1680)=48

GCD(5075,1450)=

Suriin ang mga resulta sa iyong computer.

Italaga ang mga bata sa computer na maghanap ng GCD at LCM para sa tatlong numero gamit ang isang programa para sa paghahanap ng GCD at LCM.

GCD (150, ____) = ____

GCD(450,315,135)=____

GCD (135, ____) = ____

GCD(2160,1350,1080)=____

GCD(1080, ____) = ____

GCD(5300,3180,2120)=____

GCD(2120, ____) = ____

(Upang mahanap ang gcd ng tatlo o higit pang mga numero, hanapin muna ang gcd ng alinman sa dalawa sa mga ito, pagkatapos ay ang gcd ng natagpuang divisor at ang ikatlong ibinigay na numero.

at ang ikatlong ibinigay na numero.

7. Sinusuri ang mga resulta sa isang computer. Malayang paglutas ng problema.

1) Magkaparehong mga regalo ang inihanda para sa mga mag-aaral sa klase. Kasama sa lahat ng regalo ang 120 tsokolate, 280 matamis, at 320 mani. Ilang mag-aaral ang nasa unang baitang kung malalaman na higit sa 30 sila?

Sagot: ___________________________

2) May tatlong pampasaherong tren sa istasyon: ang una ay may 418 na upuan sa mga compartment na kotse, ang pangalawa ay may 494, at ang pangatlo ay may 456. Ilang mga compartment na kotse ang naroroon sa bawat tren, kung ang bawat kotse ay may parehong bilang ng mga upuan at ang kanilang kabuuang bilang ay higit sa 20? Sagot _______________________

3) Mula sa 156 na mga rosas ng tsaa, 234 na puti at 390 na pulang rosas ang ginawang mga bouquet, at sa lahat ng mga bouquet ay may pantay na bilang ng mga rosas ng bawat uri at ang bilang ng mga naturang bouquet ay higit sa 50. Ilang mga bouquet ang ginawa mula sa mga ito rosas at ilang rosas ng bawat uri ang nasa isang palumpon? Sagot________________

Buod ng aralin. Anong paraan ng paghahanap ng GCD at LCM ang nakilala natin sa aralin? Ang algorithm ni Euclid. Ano ang isa pang pangalan para sa pamamaraang ito? (paraan ng pagbabawas). Paano napabuti ang pamamaraang ito? Gamit ang dibisyon, ang isang mas malaking numero ay hinahati sa isang mas maliit na numero, pagkatapos ay isang mas maliit na numero sa unang natitira, pagkatapos ang unang natitira sa pangalawang nalalabi, atbp., hanggang sa makakuha sila ng 0. Ang huling hindi-zero na natitira ay ang gcd ng numero.

Upang gumamit ng mga preview ng presentasyon, gumawa ng Google account at mag-log in dito: https://accounts.google.com

Mga slide caption:

EUCLID'S ALGORITHM EUCLID, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Prinsipyo" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang paraan ng pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika. Euclid (365-300 BC)

EUCLID'S ALGORITHM Ang Euclid's algorithm ay isang algorithm para sa paghahanap ng greatest common divisor (GCD) ng dalawang non-negative integers. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek na mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

Ang pagkalkula ng GCD GCD = ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang na naghahati sa parehong orihinal na mga numero nang hindi nag-iiwan ng natitira. GCD(a, b)= GCD(a-b, b)= GCD(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba ng mas malaki at mas maliit hanggang sa magkapantay sila. GCD ito. GCD (18, 45) = GCD (18, 45-18) = GCD (18, 27) = GCD (18, 9) = =GCD(9,9)=9 Halimbawa:

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

programa Evklid ; var m, n: integer; simulan writeln("vved 2 numero"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:= n-m ; wakas; write("nod=",m); readlnend.

0.Patakbuhin ang Evklid program sa iyong computer. Subukan ito ng mga halaga M=32, N=24; M=696, N=234. 1 . Suriin kung ang dalawang ibinigay na numero ay medyo prime. Tandaan. Dalawang numero ang sinasabing relatibong prime kung ang kanilang pinakamalaking karaniwang divisor ay 1.2. Hanapin ang least common multiple (LCD) ng mga numero n at m kung LCM(n, m) = n * m / GCD(n, m). 3. Ibinigay ang mga natural na bilang m at n. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n. 4. Hanapin ang gcd ng tatlong numero. Tandaan. GCD(a , b , c)= GCD(GCD(a , b), c) Mga Problema

Preview:

Paksa: "Euclidean Algorithm"

Layunin ng aralin:

Pang-edukasyon:

matutong ilapat ang Euclidean algorithm upang mahanap ang gcd ng dalawa at tatlong numero
pagsamahin ang mga kasanayan sa paggamit ng mga istrukturang algorithm na "Branching" at "Cycle"
magkaroon ng karanasan sa pagsulat at pag-debug ng mga programa sa wikang programming ng Pascal

Pang-edukasyon:

pagbuo ng kalayaan at pananagutan kapag nag-aaral ng bagong materyal

Pag-unlad:

pag-unlad ng atensyon at analytical na pag-iisip

Plano ng aralin:

Oras ng pag-aayos
Pag-update ng kaalaman
Pagpapaliwanag ng bagong paksa
Praktikal na bahagi
Pagbubuod ng aralin
Takdang aralin.

Oras ng pag-aayos

Pagbati. Sino ang absent. Numero. Paksa ng aralin. Mga tanong sa takdang-aralin.

Pag-update ng kaalaman.

Mga Tanong:

Anong mga uri ng algorithmic na istruktura ang alam mo?

Anong istraktura ang tinatawag na linear? (Bl-sh)

Aling istraktura ang tinatawag na branching? (Bl-sh)

Anong istraktura ang tinatawag na cyclic? (Bl-sh)

Anong mga uri ng cycle ang alam mo?

Paano ipinapatupad ang isang loop na may kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Paano ipinapatupad ang isang loop na may hindi kilalang bilang ng mga pag-uulit sa wikang programming ng Pascal?

Pagpapaliwanag ng bagong paksa (pagtatanghal)

Tungkol kay Euclid;

Ang ideya ng Euclidean algorithm

Ang ideya ng algorithm na ito ay batay sa:

1. Ang property na kung M>N, pagkatapos ay GCD(M, N) = GCD(M - N, N).

Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba (ang modulus ng kanilang pagkakaiba) at ang mas maliit na bilang.

Patunay: hayaang K ang karaniwang divisor ng M at N (M>N). Nangangahulugan ito na ang M = mK, N = nK, kung saan ang m, n ay mga natural na numero, at m > n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M - N, kabilang ang pinakamalaking karaniwang divisor.

2. Pangalawang halatang pag-aari:

GCD(M, M) = M.

Para sa "manual" na pagbibilang, ganito ang hitsura ng Euclidean algorithm:

1) kung ang mga numero ay pantay, pagkatapos ay kunin ang alinman sa mga ito bilang sagot, kung hindi man ay ipagpatuloy ang pagpapatupad ng algorithm;

2) palitan ang mas malaking numero ng pagkakaiba sa pagitan ng mas malaki at mas maliit na mga numero;

3) bumalik sa hakbang 1.

Block diagram ng Euclidean algorithm

programa ng Pascal

programa Evklid;

var m, n: integer;

magsimula

writeln("vved 2 numero");

readln(m,n);

Habang ginagawa ko

Magsimula

Kung m>n

Tapos m:=m-n

Iba n:=n-m;

Wakas;

Write("nod=",m);

readln

wakas.

Praktikal na bahagi

Mga tanong at gawain:

Patakbuhin ang Evklid program sa iyong computer. Subukan ito sa mga halaga M = 32, N = 24; M = 696, N = 234.
Suriin kung ang dalawang ibinigay na numero ay medyo prime. Tandaan. Ang dalawang numero ay sinasabing relatibong prime kung ang kanilang pinakamalaking karaniwang divisor ay 1.

Pagbubuod ng aralin

Ngayon sa klase, natutunan namin ang tungkol sa Euclid algorithm, na nagbibigay-daan sa amin na mahanap ang gcd ng dalawang hindi negatibong integer, at nagsulat kami ng program sa Pascal programming language na nagpapatupad ng algorithm na ito. Makakatanggap ka ng takdang-aralin kung saan ilalapat mo ang algorithm na ito upang mahanap ang gcd ng tatlong numero at ang gcd ng dalawang numero.

Takdang aralin.

1. Sumulat ng isang programa upang mahanap ang pinakamalaking karaniwang divisor ng tatlong numero gamit ang sumusunod na formula:

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

2.Gumawa ng program para mahanap ang least common multiple (LCM) ng dalawang numero gamit ang formula:

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

Slide 1

Slide 2

Slide 3

Slide 4

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

Slide 5

programa Evklid; var m, n: integer; simulan writeln("vved 2 numero"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:=n-m; wakas; write("nod=",m); readlnend.

Slide 6

0.Patakbuhin ang Evklid program sa iyong computer. Subukan ito ng mga halaga M=32, N=24; M=696, N=234. 1. Suriin kung ang dalawang ibinigay na numero ay relatibong prime. Tandaan. Ang dalawang numero ay sinasabing relatibong prime kung ang kanilang pinakamalaking common divisor ay 1. 2. Hanapin ang least common multiple (LCD) ng mga numero n at m kung LCM(n, m) = n * m / GCD (n, m). 3. Ibinigay ang mga natural na bilang na m at n. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n. 4. Hanapin ang gcd ng tatlong numero. Tandaan. GCD(a, b, c)= GCD(GCD(a, b), c) Mga Problema

Slide 7

EUCLID, sinaunang Greek mathematician. Nagtrabaho sa Alexandria noong ika-3 siglo. BC e. Ang pangunahing gawain na "Mga Prinsipyo" (15 mga libro), na naglalaman ng mga pundasyon ng sinaunang matematika, elementarya na geometry, teorya ng numero, pangkalahatang teorya ng mga relasyon at ang paraan ng pagtukoy ng mga lugar at volume, na kasama ang mga elemento ng teorya ng mga limitasyon. Malaki ang impluwensya niya sa pag-unlad ng matematika. Gumagana sa astronomiya, optika, teorya ng musika.

Slide 2

Ang Euclidean algorithm ay isang algorithm para sa paghahanap ng greatest common divisor (GCD) ng dalawang non-negative integer. Euclid (365-300 BC) Tinawag ng mga sinaunang Greek na mathematician ang algorithm na ito na ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction".

Slide 3

Pagkalkula ng GCD

GCD = Ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking bilang na naghahati sa parehong orihinal na mga numero nang hindi nag-iiwan ng natitira. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) Palitan ang mas malaki sa dalawang numero ng pagkakaiba ng mas malaki at mas maliit hanggang sa magkapantay sila. GCD ito. GCD (18, 45)= GCD (18, 45-18)= GCD (18, 27)=GCD (18, 9)= =GCD(9,9)=9 Halimbawa:

Slide 4

Slide 5

programa Evklid; var m, n: integer; simulan writeln("vved 2 numero"); readln(m,n); habang mn magsisimula kung m>n pagkatapos m:=m-n iba n:=n-m; wakas; write("nod=",m); readlnend.

Slide 6

0.Patakbuhin ang Evklid program sa iyong computer. Subukan ito ng mga halaga M=32, N=24; M=696, N=234. 1. Suriin kung ang dalawang ibinigay na numero ay relatibong prime. Tandaan. Dalawang numero ang tinatawag na relatibong prime kung ang kanilang pinakamalaking karaniwang divisor ay 1. 2. Hanapin ang least common multiple (LCD) ng mga numero n at m kung LCM(n, m) = n * m / GCD (n, m). 3. Ibinigay ang mga natural na bilang na m at n. Maghanap ng mga natural na numerong p at q na walang karaniwang divisors na p / q = m / n. 4. Hanapin ang gcd ng tatlong numero. Tandaan. GCD(a, b, c)= GCD(GCD(a, b), c) Mga Problema

Slide 7

Tingnan ang lahat ng mga slide

Pahayag ng Problema Isaalang-alang ang sumusunod na problema: kailangan mong lumikha ng isang programa para sa pagtukoy ng pinakamalaking karaniwang divisor (GCD) ng dalawang natural na numero. Alalahanin natin ang matematika. Ang pinakamalaking karaniwang divisor ng dalawang natural na numero ay ang pinakamalaking natural na bilang kung saan sila ay pantay na nahahati. Halimbawa, ang mga numero 12 at 18 ay may mga karaniwang divisors: 2, 3, 6. Ang pinakamalaking karaniwang divisor ay ang numero 6. Ito ay nakasulat tulad ng sumusunod: GCD(12,18) = 6. Let us denote the initial data as M at N. Ang pahayag ng problema ay ang mga sumusunod : Ibinigay: M, N Hanapin: GCD(M,N).

N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang GCD ng dalawang natural na numero ay katumbas ng GCD ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay GCD(M,N) = GCD(M - N,N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na numero." class="link_thumb"> 4 !} Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang. N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang."> N, pagkatapos ay gcd(M,N) = gcd(M - N,N). Sa madaling salita, ang Ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at mas maliit na numero."> N, pagkatapos ay GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang GCD ng dalawang natural na numero ay katumbas ng GCD ng kanilang positibong pagkakaiba at ang mas maliit na bilang." title="Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa property na kung M>N, pagkatapos ay GCD(M,N) = GCD(M - N,N) Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang."> title="Ang ideya ng algorithm Ang ideya ng algorithm na ito ay batay sa pag-aari na kung M>N, pagkatapos GCD(M,N) = GCD(M - N,N). Sa madaling salita, ang gcd ng dalawang natural na numero ay katumbas ng gcd ng kanilang positibong pagkakaiba at ang mas maliit na bilang."> !}

N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors" title="Proof Let K ay isang karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n ), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors" class="link_thumb"> 5 !} Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors ng kanilang pagkakaiba M-N, kabilang ang pinakamalaking common divisor. . Kaya naman: GCD(M,N) = GCD(M - N,N). Ang pangalawang halatang property: GCD(M,M) = M. N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors "> N). Nangangahulugan ito na M = mK, N = pK , kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(t - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ay karaniwan ang mga divisor ng mga numerong M at N ay mga divisor ng kanilang pagkakaiba M-N, kabilang ang pinakamalaking karaniwang divisor. Kaya: GCD(M,N) = GCD(M - N,N). Ang pangalawang halatang property: GCD(M,M) = M."> N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors" title="Proof Let K ay isang karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n ), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors"> title="Patunay Hayaan ang K na maging karaniwang divisor ng M at. N (M>N). Nangangahulugan ito na ang M = mK, N = pK, kung saan ang m, n ay mga natural na numero, at m>n. Pagkatapos M - N = K(m - n), na nangangahulugan na ang K ay isang divisor ng numerong M - N. Nangangahulugan ito na ang lahat ng karaniwang divisors ng mga numerong M at N ay mga divisors"> !}

Pascal program Program Evklid; var M, N: integer; begin writeln("Ipasok ang M at N"); readln(M,N); habang ang MN ay nagsisimula kung M>N pagkatapos M:=M-N iba pa N:=N-M dulo; write("HOD=",M) dulo. N pagkatapos M:=M-N iba N:=N-M dulo; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M end; write("HOD=",M) end."> N tapos M:=M-N iba N:=N-M wakas; 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 pagkatapos M:=M-N iba N:=N-M dulo; 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."> !}