# Euklidészi algoritmus

### A Wikipédiából, a szabad lexikonból.

Tegyük fel, hogy x és y pozitív egész számok, és szeretnénk kiszámítani a legnagyobb közös osztójuk értékét. Ekkor vehetjük hasznát az euklidészi algoritmusnak.

Ha valamelyik szám osztja a másikat, mondjuk x | y, akkor (x,y) = x.

Ha nem osztják egymást, és mondjuk x a nagyobbik, osszuk el maradékosan y-nal: x = y * q + r, ahol 0 < r < y. Ekkor (x,y) = (y,r), így a problémát visszavezettük két kisebb szám legnagyobb közös osztójának meghatározására.

Ezt a lépést csak véges sokszor hajthatjuk végre, hiszen a számok mindvégig nem negatív egészek és folyamatosan csökkennek. Végül az utolsó, 0-tól különböző maradék a legnagyobb közös osztó.

## [szerkesztés] Az euklidészi algoritmus formális leírása

Tekintsük az számpárt. Osszuk maradékosan a-t b-vel, majd b-t a maradékkal, majd a maradékot az új maradékkal, és így tovább, mindig az osztót a maradékkal. Ekkor egy

... | ...

alakú sorozatot kapunk, ahol . Így az rn sorozat véges kell hogy legyen, és valamely -re . Tehát

Jelöljük n-nel az utolsó nem nulla maradék indexét (n = N − 1). Állítjuk, hogy ekkor rn = (a,b).

A legnagyobb közös osztó osztja a-t és b-t is, tehát r1 kreálásának módja miatt azt is. Mivel b-t és r1-et is osztja, hasonlóan r2-t is kell neki. Általánosan ha ri-t és ri + 1-et osztja, akkor így ri + 2-t is. Teljes indukcióval beláttuk tehát, hogy (a,b) | rn. Visszafelé haladva pedig tudjuk, hogy rn | rn − 1. Ekkor azonban rn | rn - 2, s általánosan ha rn | ri és rn | ri − 1, akkor rn | ri − 2. Így visszafelé elértük, hogy rn | a,b, azaz rn | (a,b). Ha ezt összevetjük azzal, hogy (a,b) | rn, akkor látható, hogy rn = (a,b). Az algoritmus tehát működik.

| Ez a matematikai tárgyú lap még csak csonk (azaz erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!

A lap eredeti címe "http://hu.wikipedia.org../../../e/u/k/Euklid%C3%A9szi_algoritmus.html"

Kategóriák: Számelmélet | Algoritmusok | Csonkok (matematika) | Csonkok 2004 novemberéből

##### Views

- Szócikk
- Vitalap
- Aktuális változat

##### Keresés

##### Más nyelveken

- English
- العربية
- Български
- Català
- Česky
- Deutsch
- Español
- Suomi
- Français
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Latviešu
- Nederlands
- Polski
- Português
- Русский
- Slovenščina
- Svenska
- Tiếng Việt
- 中文