This HTML5 document contains 130 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
n14https://youproof.hu/kriptografia/
foafhttp://xmlns.com/foaf/0.1/
n9https://books.google.com/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n7http://hu.dbpedia.org/resource/Sablon:
owlhttp://www.w3.org/2002/07/owl#
n8https://archive.org/details/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Euklideszi_algoritmus
rdfs:label
Euklideszi algoritmus
owl:sameAs
freebase:m.02tbp
dct:subject
n11:Algoritmusok n11:Számelmélet
dbo:wikiPageID
9008
dbo:wikiPageRevisionID
23681903
dbo:wikiPageExternalLink
n8:introductiontonu00star_0 n8:numbertheoryitsh00ore n14:21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere n9:%3Fid=yMGeElJ8M0wC n14:17-euklideszi-algoritmus-maradekos-osztas-legnagyobb-kozos-oszto-euklideszi-gyuru n9:%3Fid=hXGr-9l1DXcC n9:%3Fid=WZIKAAAAYAAJ&printsec=frontcover%23v=onepage&q&f=false n9:%3Fid=7eLkq0wQytAC
prop-hu:wikiPageUsesTemplate
n7:Cite_book n7:Refhely n7:Kínai n7:Jegyzetek n7:Hely n7:Forrás n7:Fordítás n7:Portál n7:Kiemelt n7:ISBN n7:Math
prop-hu:authorlink
Donald Knuth
prop-hu:edition
3.0 2 4 1.0
prop-hu:first
K. H. O. W. J. C. R. P. G. J. J. D. E. J. H. M. R. A. D.
prop-hu:isbn
978 0
prop-hu:language
német
prop-hu:last
Rosen Crandall Knuth Stillwell Pomerance Stark Lejeune Dirichlet Schroeder LeVeque Ore Cox Little Tattersall Cohn O'Shea Mollin Cohen
prop-hu:location
New York Braunschweig Cambridge Reading, MA Boca Raton
prop-hu:oclc
490186017
prop-hu:origyear
1977
prop-hu:publisher
Addison–Wesley Vieweg MIT Press Chapman & Hall/CRC McGraw–Hill Dover dbpedia-hu:Cambridge_University_Press Springer-Verlag
prop-hu:ref
harv
prop-hu:title
Vorlesungen über Zahlentheorie Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra Fundamentals of Number Theory An Introduction to Number Theory Elementary Number Theory and its Applications Number Theory in Science and Communication Elementary Number Theory in Nine Chapters Advanced Number Theory Numbers and Geometry Prime Numbers: A Computational Perspective Fundamental Number Theory with Applications Elements of Number Theory A Course in Computational Algebraic Number Theory Number Theory and Its History The Art of Computer Programming, Volume 2: Seminumerical Algorithms
prop-hu:url
n9:%3Fid=7eLkq0wQytAC n8:introductiontonu00star_0 n9:%3Fid=yMGeElJ8M0wC n9:%3Fid=hXGr-9l1DXcC n9:%3Fid=WZIKAAAAYAAJ&printsec=frontcover%23v=onepage&q&f=false n8:numbertheoryitsh00ore
prop-hu:year
1993 1996 1997 2008 2003 2000 2001 2005 1962 1978 1948 1894
prop-hu:authorLink
Manfred R. Schroeder William J. LeVeque Henri Cohen Peter Gustav Lejeune Dirichlet Harold Stark Øystein Ore John Stillwell
prop-hu:editorFirst
Richard
prop-hu:editorLast
Dedekind
prop-hu:lccn
3005859
prop-hu:editorLink
Richard Dedekind
prop-hu:author2Link
Carl Pomerance
dbo:abstract
Az euklideszi algoritmus egy számelméleti algoritmus, amellyel két szám legnagyobb közös osztója határozható meg. Nevét az ókori görög matematikusról, Eukleidészről kapta, aki az Elemekben írta le (Kr. e. 300 körül). Az egyik legrégibb, gyakran használt algoritmus. Alapötlete az, hogy a legnagyobb közös osztó nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Például 252 és 105 legnagyobb közös osztója 21, amely legnagyobb közös osztója a 105 és a 147 = 252 − 105 számoknak is. Ez a helyettesítés csökkenti a nagyobb számot, így a cserék ismétlésével egyre kisebb számokat kapunk, egészen addig, amíg a két szám egyenlővé nem válik. Ez az eddigi számpárok, így az eredeti számpár legnagyobb közös osztója. Az algoritmus lépésein visszafelé menve találunk két egész (akár negatív) tényezőt, amelyek felhasználásával a legnagyobb közös osztó kifejezhető a két kiindulási szám lineáris kombinációjaként. Ha feltesszük, hogy a kivonások és a maradékos osztások ideje körülbelül megegyezik, akkor az algoritmusnak van egy gyorsabb változata is, amely a kivonások helyett maradékos osztással működik. Ennek lényege, hogy ha a nagyobb szám sokkal nagyobb, mint a kisebb, akkor sok kivonást kell elvégezni addig, amíg a két szám szerepe felcserélődik. A maradékképzés művelete ezt a sok kivonást egy lépésben végzi el. Az algoritmus akkor ér véget, amikor a maradék nulla lesz. Ekkor a legnagyobb közös osztó éppen a kisebb szám. Ezzel az algoritmus lépésszáma a kisebb szám logaritmusával arányossá válik (sohasem nagyobb, mint a tízes számrendszerbeli jegyek számának ötszöröse). A 20. század folyamán további optimalizációt végeztek. Az algoritmusnak számos alkalmazása van. A törtek egyszerűsítése mellett a moduláris aritmetika osztás műveletének megvalósításában is szerepel. Ehhez az ax ≡ c mod b kongruenciát kell megoldani, ezt a Lineáris diofantoszi egyenletek szakasz írja le részletesebben. Használható diofantoszi egyenletek megoldására, mint amilyen például a kínai maradéktételben szereplő szimultán kongruenciarendszer. Alkalmas lánctörtbe fejtéshez és irracionális számok közelítéséhez. Végül, de nem utolsósorban számelméleti tételek bizonyításának is hasznos segédeszköze; felhasználja a négynégyzetszám-tétel és a számelmélet alaptétele. Eredetileg egész számokra és szakaszokra használták, de a 19. században általánosították Gauss-egészekre és egyváltozós polinomokra.
prov:wasDerivedFrom
wikipedia-hu:Euklideszi_algoritmus?oldid=23681903&ns=0
dbo:wikiPageLength
94565
foaf:isPrimaryTopicOf
wikipedia-hu:Euklideszi_algoritmus
Subject Item
dbpedia-hu:Euklidészi_algoritmus
dbo:wikiPageRedirects
dbpedia-hu:Euklideszi_algoritmus
Subject Item
wikipedia-hu:Euklideszi_algoritmus
foaf:primaryTopic
dbpedia-hu:Euklideszi_algoritmus