Eukleidese lemma

Eukleidese lemma ehk Eukleidese esimene teoreem on üks oluline lemma klassikalises aritmeetikas ja elementaarses arvuteoorias, mis ütleb:
Kui algarv  jagab kahe täisarvu korrutist , siis  jagab vähemalt ühte neist täisarvudest.

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).Elemendid, raamat VII, lause 30 (ingliskeelne tõlge, originaaltõestusega)

 Teised formuleeringud 
Lemma võib formuleerida ka enama kui kahe täisarvu korrutise kohta:Виноградов И. М. Основы теории чисел.  М.—Л.: ГИТТЛ, 1952., lk 20.

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.Бухштаб А. А. Теория чисел, М.: Просвещение 1966*, lk 46, teoreem 41.
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 
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
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.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. Bézout' lemma ütleb, et kui  ja  on ühisteguriteta täisarvud (st neil ei ole ühiseid jagajaid peale 1 ja −1), siis leiduvad täisarvud  ja  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.Калужнин Л. Основная теорема арифметики, М., Наука, 1969, lk 32, teoreem 4.

Eukleidese lemma teise kuju tõestamiseks oletame, et  ja  on ühisteguriteta ning coprime, and assume that . Bézout' lemma järgi leiduvad  ja  nii, et 

Korrutame mõlemad pooled arvuga :

Esimene liige vasakul jagub arvuga  ja teine liige jagub arvuga , mis eelduse kohaselt jagub arvuga . Sellepärast ka , mis on nende summa, jagub arvuga .

Tõestus matemaatilise induktsiooni teel
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 ). 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 a on ü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 ; 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"
Eukleidese 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.</span>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 
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
Eukleidese lemma ei kehti mitte ainult täisarvude ringis, vaid ka teistes faktoriaalsetes ringides, kus algarvude osa etendavad taandumatud elemendid. Sealhulgas kehtib ta Eukleidese ringides,Ленг С. Алгебра*,  М.: Мир 1968, lk 89—90. näiteks:
 Gaussi täisarvude ring 
 Ühe muutuja polünoomide ring  üle korpuse 

Gaussi lemma kehtib kõigis SÜT-ringides, sealhulgas kõikides peaideaaliringides, näiteks polünoomide ringides üle korpuse.

Üldistus peaideaaliringidele

Lemma kehtib ka (kommutatiivsetes) peaideaaliringides. Kui  on peaideaaliring,  ja  on taandumatu element ringis , siis .Jürgen Wolfart. Einführung in die Algebra und Zahlentheorie,  Vieweg: Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, lk 76

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
See lemma esineb esimest korda 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 olemasolust ja ühesusest tuletab ta üldistuse täisarvudele. Seepärast nimetatakse seda üldistust ka Gaussi lemmaks.

 Viited 

Kategooria:Arvuteooria