Eukleidese lemma
Eukleidese lemma ehk Eukleidese esimene teoreem on üks oluline lemma klassikalises aritmeetikas ja elementaarses arvuteoorias, mis ütleb:
Näide. 19 on algarv, ja see jagab arvu Järelikult jagub üks teguritest 19-ga, nimelt
Vastunäide kordarvu korral. jagub 20-ga, kuid kumbki tegur 20-ga ei jagu.
Eukleidese lemmat kasutatakse tavaliselt aritmeetika põhiteoreemi tõestuses, täpsemalt algteguriteks lahutuse ühesuse tõestamisel. Üldistustes piisab näitamiseks, et antud integriteetkond on faktoriaalne ring, Eukleidese lemma ning peaideaalide tõusvate ahelate tingimuse tõestamisest.
Seda omadust kasutatakse algarvu mõiste üldistamiseks kommutatiivse ringi lihtsateks elementideks ja lihtsateks ideaalideks. Eukleidese lemma näitab, et täisarvude ringis on taandumatud elemendid ka lihtsad elemendid. Tõestus kasutab matemaatilist induktsiooni ega ole seetõttu rakendatav kõikides integriteetkondades.
See väide esineb juba Eukleidese "Elementides" (raamat VII, lause 30).[1]
Teised formuleeringud
[muuda | muuda lähteteksti]Lemma võib formuleerida ka enama kui kahe täisarvu korrutise kohta:[2]
- Kui mitme täisarvulise teguri korrutis jagub algarvuga , siis vähemalt üks teguritest jagub arvuga .
Eukleidese lemmat kasutatakse tavaliselt järgmisel samaväärsel kujul:
- Kui on algarv, mis jagab täisarvude korrutist , ent ei jaga arvu siis ta jagab arvu .
Sellega ekvivalentne on järgmine üldistus:
- Kui jagab korrutist ja on ühega teguritest ühistegurita, siis ta jagab teist tegurit.[3]
Tõepoolest, kui on algarv, tuleb jälle välja ülaltoodud formuleering; kui on kordarv, siis väide kehtib iga tema algteguri kohta ning seetõttu ka arvu enda kohta.
See üldistus laieneb ka täisarvudele (Gaussi lemma):
- Kui täisarv n jagab kahe täisarvu korrutist ab, siis n jagab arvu b.
See on üldistus, sest algarv p ja täisarv a on ühisteguriteta siis ja ainult siis, kui p ei jaga arvu a.
Tõestus
[muuda | muuda lähteteksti]Kaks esimest tõestust tõestavad Eukleidese lemma üldistatud kujul, nimelt et kui täisarv n jagab täisarvude korrutist ab ning n ja a on ühisteguriteta, siis n jagab arvu b.
Algne Eukleidese lemma järeldub sellest, sest kui n on algarv, siis ta jagab arvu a või ei jaga arvu a ning viimasel juhtumil on n ja a ühisteguriteta, nii et üldistatud lemma järgi n jagab arvu b.
Tõestus Bézout' lemma kaudu
[muuda | muuda lähteteksti]Tänapäeval klassikaline otsetõestus kasutab Bézout' lemmat täisarvude kohta, nii et arutluskäik osalt väljub naturaalarvude raamest, aga väide kehtib ilmselt ka ahendatuna hulgale . Eukleidese aegadel Bézout' lemmat ei tuntud.[4] Bézout' lemma ütleb, et kui x ja y on ühisteguriteta täisarvud (st neil ei ole ühiseid jagajaid peale 1 ja −1), siis leiduvad täisarvud r ja s nii, et
Olgu suvalised täisarvud. Eeldusel, et algarv jagab korrutist , ent mitte tegurit , tuleb näidata, et on teguri jagaja.
Eeldusest järeldub muu hulgas, et ja on ühisteguriteta. Bézout' lemma järgi eksisteerivad siis kaks täisarvu ja nii, et . Kui seda võrdust korrutada arvuga ja pisut teisendada, saame
- .
Eelduse kohaselt eksisteerib täisarv , mille korral , seega saab võrduse vasakus pooles sulgude ette viia:
- .
Järelikult on korrutise tegur. Seega jagab ta tegurit , mida oligi tarvis tõestada.[5]
Eukleidese lemma teise kuju tõestamiseks oletame, et a ja n on ühisteguriteta ning coprime, and assume that n|ab. Bézout' lemma järgi leiduvad r ja s nii, et
Korrutame mõlemad pooled arvuga b:
Esimene liige vasakul jagub arvuga n ja teine liige jagub arvuga ab, mis eelduse kohaselt jagub arvuga n. Sellepärast ka b, mis on nende summa, jagub arvuga n.
Tõestus matemaatilise induktsiooni teel
[muuda | muuda lähteteksti]Järgnev tõestus on inspireeritud Eukleidese algoritmi Eukleidese versioonist, mis kasutab ainult lahutamist.
Oletame, et ning n ja a on ühisteguriteta (st nende suurim ühistegur on 1). Tuleb tõestada, et arv n jagab arvu b. Et siis leidub täisarv q nii, et Üldisust kaotamata võib eeldada, et n, q, a ja b on positiivsed, sest jaguvusseos on märkidest sõltumatu.
Et tõestada seda tugeva induktsiooni teel, oletame, et väide on tõestatud ab kõikide väiksemate positiivsete väärtuste korral.
On kolm juhtumit:
Kui n = a, siis kuna n ja aon ühisteguriteta, siis n = 1 ning see, et n jagab arvu b, järeldub triviaalselt.
Kui n < a, siis
Positiivsed täisarvud a – n ja n on ühisteguriteta: nende suurim ühistegur d peab jagama nende summat ning seetõttu jagab nii arvu n kui ka arvu a. Et eelduse järgi n ja a on ühisteguriteta, siis d = 1. Nüüd järeldub järeldus induktsioonihüpoteesist, sest 0 < (a – n) b < ab.
Samamoodi, kui n > a, siis
ja sama argument näitab, et n – a ja a on ühisteguriteta. Saame, et 0 < a (b − q) < ab}}, ja induktsioonihüpoteesist järeldub, et n − a jagab arvu b − q; st, leidub täisarv r, mille korral . Järelikult , järelikult Nii et , järelikult ning sellega on väide tõestatud.
Tõestus "Elementides"
[muuda | muuda lähteteksti]Eu1kleidese lemma on tõestatud Eukleidese "Elementide" VII raamatu lausena 30.
Lause 19
- Kui neli arvu on proportsionaalsed, siis esimesest ja neljandast saadud arv on võrdne teisest ja kolmandast saadud arvuga; ja kui esimesest ja neljandast saadud arv on võrdne teisest ja kolmandast saadud arvuga, siis need neli arvu on proportsionaalsed. [St, kui a : b=c : d, siis ad=bc; ja ümberpöördult.]
Lause 20
- Kõige väiksemad arvud nende seas, millel on sama proportsioon, mõõdavad neid, millel on nendega sama proportsioon sama arv kordi — mida suurem, seda suurem, ja mida väiksem, seda väiksem.
[St, kui a : b=c : d ning a, 'I'b on kõige väiksemad arvud nende seast, millel on nendega sama proportsioon, siis c=na, d=nb, kus n on täisarv.
Lause 21.
- Arvud, mis on ühisteguriteta, on kõige väiksemad nende seast, millel on nendega sama proportsioon.
[St, kui a : b=c : d ning a, b on ühisteguriteta, siis a, b on kõige väiksemad arvud nende seast, millel on sama proportsioon.
Lause 29
- Mis tahes algarv ja mis tahes arv, mida ta ei mõõda, on ühismõõduta. [St, kui a on algarv ja ta ei mõõda arvu b, sii9s a, b on ühismõõduta.
Lause 30
- Kui kaks arvu annavad korrutamisel sama arvu ja mingi algarv mõõdab korrutist, siis ta mõõdab ka üht algsetest arvudest. [St, algarv c mõõdab arvu ab, siis ta mõõdab kas arvu a või arvu b.
- Tõestus. Oletame, et c ei mõõda arvu a. Siis c, a on ühismõõduta (lause 29). Oletame, et ab=mc. Siis c : a = b : m (lause 19). Järelikult (lause 20, lause 21) b=nc, kus n on täisarv.
Järelikult c mõõdab arvu b.
Samamoodi, kui c ei mõõda arvu b, siis ta mõõdab arvu a. Seega c mõõdab üht arvudest a, b, mida oligi tarvis tõestada.
Rakendused
[muuda | muuda lähteteksti]Eukleidese lemmat kasutatakse kaudselt peaaegu igas argumentatsioonis jaguvuse kaudu, muu hulgas algteguriteks lahutuste ja Eukleidese algoritmi juures. Praktilistes arvutusülesannetes on lemmal endal ainult allutatud roll.
Üldistused
[muuda | muuda lähteteksti]Eukleidese lemma ei kehti mitte ainult täisarvude ringis, vaid ka teistes faktoriaalsetes ringides, kus algarvude osa etendavad taandumatud elemendd. Salhulgas kehtib ta Eukleidese ringides,[6], näiteks:
- Gaussi täisarvude ring
- Ühe muutuja polünoomide ring üle korpuse
Gaussi lemma kehtib kõigis SÜT-ringides, sealhulgas kõikides peaideaaliring, näiteks polünoomide ringides üle korpuse.
Üldistus peaideaaliringidele
[muuda | muuda lähteteksti]Lemma kehtib ka (kommutatiivsetes) peaideaaliringides. Kui on peaideaaliring, ja on taandumatu element ringis , siis .[7]
Peale selle tõestatakse tugevamaks peetav väide, et taandumatu elemendi genereeritud peaideaal on juba maksimaalne ideaal. Peaideaaliringis langevad järelikult lihtsa ideaali ja maksimaalse ideaali mõiste kokku.
Tõepoolest, kui on ideaal ning , siis leidub nii, et . Sellest, et järeldub järelikult, et sobiva korral . Et on taandumatu, siis on ringis pööratav element või on seal pööratav element. Järelikult kas või ja on assotsieeritud elemendid ning genereerivad sama peaideaali. Kokkuvõttes saame, et või , mis definitsiooni järgi tähendab, et on maksimaalne ideaal.
Ajalugu
[muuda | muuda lähteteksti]See lemma esineb esmakordselt Eukleidese "Elementide" VII raamatu lausena 30. See tuuakse ära praktiliselt kõigis elementaarse arvuteooria raamatutes.
Lemma üldistus täisarvudele ilmus Jean Prestet' õpikus "Nouveaux Elémens de Mathématiques" (1681).
Carl Friedrich Gaußi traktaadis "Disquisitiones arithmeticae" on lemma väide Eukleidese lause, mida ta kasutab täisarvu algteguriteks lahutuse ühesuse tõestamiseks (teoreem 16), pidades algteguriteks lahutuse olemasolu ilmseks. Sellest olemsolust ja ühesusest tuletab ta üldistuse täisarvudele. Selepärast nimetatakse seda üldistust ka Gaussi lemmaks.
Viited
[muuda | muuda lähteteksti]- ↑ Elemendid, raamat VII, lause 30 (ingliskeelne tõlge, originaaltõestusega)
- ↑ Виноградов И. М. Основы теории чисел. М.—Л.: ГИТТЛ, 1952., lk 20.
- ↑ Бухштаб А. А. Теория чисел, М.: Просвещение 1966*, lk 46, teoreem 41.
- ↑ G. H. Hardy, E. M. Wright, A. J. Wiles. An Introduction to the Theory of Numbers, 6. trükk, Oxford: Oxford University Press 2008, ISBN 978-0-19-921986-5.
- ↑ Калужнин Л. [http://plm.mccme.ru/ann/a47.htm Основная теорема арифметики, М., Наука, 1969, lk 32, teoreem 4.
- ↑ Ленг С. Алгебра*, М.: Мир 1968, lk 89—90.
- ↑ Jürgen Wolfart. Einführung in die Algebra und Zahlentheorie, Vieweg: Braunschweig/Wiesbaden 1996, ISBN=3-528-07286-5, lk 76}}