Zatiketa euklidear

17 5-eko 3 taldetan banatzen da 2 zati bakarrik utziz. Hemen zatikizuna 17 da, zatitzailea 5, zatidura 3 eta hondarra 2.
17 = 5 × 3 + 2

Aritmetikan, Zatiketa Euklidearra (edo Euklidestarra), baita zatiketaren algoritmo gisa ezagutua, bi zenbaki osoren arteko zatiketaren eragiketari deritzo. Prozesu honetan, zatidura eta hondarra lortzen dira. Teoremak adierazten du hondar eta zatidura bat existitu eta bakarrak direla adierazten du, baldintza batzuk betez gero. Zatiketa Euklidearraz hitz egitean, ez da zatidura eta hondarra esplizituki kalkulatuko dituen metodo gisa ulertuko. Zatiketa honen kalkulua egiteko erabiltzen diren metodoak Zenbaki osoen zatiketaren algoritmo dute izena, non Zatiketa luzea den hedatuena, baina Osoen faktorizazioa eta Aritmetika modularra baita erabiliak dira.

Zatiketa Euklidearra, eta hau kalkulatzeko algoritmoak, zenbaki osoekin lan egiten den zenbait gaitan oso garrantzitsuak dira, esaterako, bi zenbaki osoren arteko zatitzaile komun handiena aurkitzeko Euklidesen algoritmoa. Hondarra kalkulatzen duen eragiketaren izena modulu eragiketa da.

Teoremaren adierazpena

$a$ eta $b$ zenbaki osoak emanda, $b$ ≠ $0$ izanda, bi zenbaki oso existituko dira $q$ eta $r$ non bat eta bakarrak diren eta

a=bq+r

eta

0\leq r<|b|

,

non $|b|$ $b$ -ren balio absolutua den.

Teorema honetan agertzen diren 4 zenbaki osoek izen bat dute: $a$ -ri zatikizun deitzen zaio, $b$ -ri zatitzaile deitzen zaio, $q$ -ri zatidura deitzen zaio eta $r$ -ri hondar deitzen zaio.

Adibidea

$320\,$		$21\,$
$110\,$		$15\,$
$5\,$

Horrek esan nahi du $320=(21\times 15)+5$ dela, $0\leq 5<|21|$ izanik.

Zatiduraren eta hondarraren kalkuluari, zatikizunetik eta zatitzailetik, zatiketa edo Zatiketa Euklidearra deritzo. Teorema honek askotan zatiketaren algoritmoari egiten dio aipamen, teorema izan arren eta ez algoritmoa, zeren eta bere frogapenak, ondoren esan bezala, zatiketaren algoritmo sinple bat ere ekartzen du $q$ eta $r$ kalkulatzeko.

Zatiketa ez dago definituta $b=0$ kasuan.

Historia

"Zatiketa Euklidearra" hitza 20. mendean erabiltzen hasi zen "Eremu Euklideararren zatiketaren" takigrafia moduan. Berehala hasi ziren matematikariak hitz hau erabiltzen zatiketa mota hau beste motako zenbakien zatiketez ezberdintzeko.

Adibide intuitiboa

Gaztak 9 zati dauzka, ondorioz, 4 lagunetako bakoitzari 2 gazta zati dagozkio, 1 soberan utziz.

Suposatu gazta bat 9 puskatan dagoela zatituta eta 4 lagunen artean banatu behar direla puska horiek. Zatiketa Euklidearra erabiliz, 9 4-rekin zatituta, zatidura 2 izango da eta hondarra 1. Hau da, lagun bakoitzak gaztaren 2 puska izango ditu, baina zati bat geldituko da soberakin.

Hau biderketa, zatiketaren kontrakoa, erabiliz froga daiteke: lagun bakoitzak 2 gazta puska hartuko balitu, orduan, 4 × 2 = 8 puska eskaini zaizkie 4 lagunei. Soberan geratzen den azken zatia batuz, emaitza 9 puska izango da. Laburbilduz: 9 = 4 × 2 + 1.

Orokortuz, pusken kopuruari a izena emanez eta lagun kopurua b izanik, hainbatetan zatitu daiteke gazta lagunen artean bakoitzak q puska izateko (zatidura) eta zenbait puska r < b soberan geldituko dira (hondarra). Ondorioz, a = bq + r ekuazioa betetzen da.

9 puskak 3 lagunen artean zatituak izan balira 4-ren artean izan ordez, bakoitzak 3 zati izango lituzke. Kasu honetan, hondarra zero da eta esaten da 3-ak hainbatetan zatitzen duela 9, edo 3-ak 9 zatitzen duela.

Zatiketa Euklidearra ere zenbaki negatiboekin erabili daiteke formula berdinarekin; adibidez: −9 = 4 × (−3) + 3, hots, −9 4-rekin zatituta −3 da hondarra 3 izanik.

Frogapena

Frogapena 2 zatitan datza — lehenik, q-ren eta r-ren existentziaren froga, eta bigarrenik, q eta r bat eta bakarrak direnaren froga.

Existentziaren froga

$b'=-b$ eta $q'=-q$ bezala emanik, $a=bq+r$ ekuazioa $a=b'q'+r$ moduan idatz liteke eta $0\leq r<|b|$ desberdintza hau honela idatz liteke: $0\leq r<|b'|$ . Hau eginez $b<0$ kasuaren existentzia $b>0$ kasura laburtzen da.

Berdintsu, $a<0$ eta $b>0$ bada, $a'=-a$ , $q'=-q-1$ eta $r'=b-r$ bezala emanik, $a=bq+r$ ekuazioa $a'=bq'+r'$ moduan berridatz liteke eta $0\leq r<b$ desberdintza honela idatz liteke $0\leq r'<b$ . Ondorioz, existentziaren froga $a\geq 0$ eta $b>0$ kasura laburtzen da eta frogaren hondarrean bakarrik hartuko ditugu aintzat.

Izan daitezela q₁ eta r₁ biak ez-negatiboak, orduan a = bq₁ + r₁, adibidez, q₁ = 0 eta r₁ = a. Baldin r₁ < b egia bada, bukatu dugu. Bestela, q₂ = q₁ + 1 eta r₂ = r₁ − b hauekin bat datoz a = bq₂ + r₂ eta 0 ≤ r₂ < r₁. Eragiketa hau errepikatuz lortzen dena da: q = q_k eta r = r_k, hori dela eta, a = bq + r eta 0 ≤ r < b da.

Honek existentzia frogatzen du eta zatiketaren algoritmo sinple bat ematen du zatidura eta hondarra kalkulatzeko. Hala ere, algoritmo honek q pauso behar ditu, ondorioz, ez da oso eraginkorra.

Bakartasunaren froga

Suposatu existitzen direla $q$ , $q'$ , $r$ , $r'$ non $0\leq r$ , $r'<|b|$ izanik, non $a=bq+r$ eta $a=bq'+r'$ . Bi desberdintzak batuz gero $0\leq r<|b|$ eta $-|b|<-r'\leq 0$ honako hau lortzen da $-|b|<r-r'<|b|$ , zein honela adierazi daitekeen $|r-r'|<|b|$ .

Aurreko bi ekuazioak berdinduz: $b(q'-q)=(r-r')$ . Ondorioz, $|b|$ -ek $|r-r'|$ zatitzen du. Baldin $|r-r'|\neq 0$ bada, esan nahi du $|b|\leq |r-r'|$ , aurreko desberdintzarekin kontraesanean egonik. Ondorioz, $r=r'$ eta $b(q'-q)=0$ . $b\neq 0$ denez, $q=q'$ da, bakartasuna frogatuz.

Eraginkortasuna

Orokorrean, existentziaren froga batek ez du existitzen den objektu bat kalkulatzeko algoritmo bat ekartzen, baina goiko frogapenak bat-batean ematen du algoritmo bat (ikusi Errepikapenezko kenketaren zatiketa). Hala ere, hau ez da oso metodo eraginkorra, zatiduraren kopuruaren hainbeste eragiketa behar baitu. Hau gertatzearen arrazoia bakarrik zenbaki osoen batuketaren, kenketaren eta konparazioaren erabilpenenean dago, biderketa baztertuz nahiz zenbaki oso partikularren erabilpena, adibidez, idazkera hamartarra.

Idazkera hamartarraren ikuspuntutik, zatiketa luzeak askoz ere eraginkorragoa den algoritmo bat ematen du. Idazkera bitarrerako orokortzeak konputagailuan erabiltzea ahalbidetzen du. Hala ere, sarrera handientzat, zatiketak biderketa bihurtzen dituzten algoritmoak, Newton–Raphsonen zatiketa bezalakoak, nahiago izaten dira, biderketen emaitza egiaztatzeko behar den denborarekiko proportzionala delako behar duten denbora, zein biderketa algoritmo erabiltzen ari den kontuan hartu gabe.

Bibliografia

(Ingelesez) Grimaldi, Ralph P., Discrete and Combinatorial Mathematics: An Applied Introduction

Ikus gainera

Kanpo estekak

Datuak: Q181054
Multimedia: Euclidean division / Q181054