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 formula_1 Järelikult jagub üks teguritest 19-ga, nimelt formula_2
Vastunäide kordarvu korral. formula_3 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).
Teised formuleeringud.
Lemma võib formuleerida ka enama kui kahe täisarvu korrutise kohta:
Kui mitme täisarvulise teguri korrutis jagub algarvuga formula_4, siis vähemalt üks teguritest jagub arvuga formula_4.
Eukleidese lemmat kasutatakse tavaliselt järgmisel samaväärsel kujul:
Kui formula_4 on algarv, mis jagab täisarvude korrutist formula_7, ent ei jaga arvu formula_8 siis ta jagab arvu formula_9.
Sellega ekvivalentne on järgmine üldistus: 
 Kui formula_10 jagab korrutist formula_7 ja on ühega teguritest ühistegurita, siis ta jagab teist tegurit.
Tõepoolest, kui formula_12 on algarv, tuleb jälle välja ülaltoodud formuleering; kui formula_12 on kordarv, siis väide kehtib iga tema algteguri kohta ning seetõttu ka arvu formula_12 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 formula_15. Eukleidese aegadel Bézout' lemmat ei tuntud. 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
formula_16 
Olgu formula_17 suvalised täisarvud. Eeldusel, et algarv formula_4 jagab korrutist formula_7, ent mitte tegurit formula_20, tuleb näidata, et formula_4 on teguri formula_22 jagaja.
Eeldusest järeldub muu hulgas, et formula_20 ja formula_4 on ühisteguriteta. Bézout' lemma järgi eksisteerivad siis kaks täisarvu formula_25 ja formula_26 nii, et formula_27. Kui seda võrdust korrutada arvuga formula_22 ja pisut teisendada, saame
 formula_29.
Eelduse kohaselt eksisteerib täisarv formula_30, mille korral formula_31, seega saab formula_4 võrduse vasakus pooles sulgude ette viia:
 formula_33.
Järelikult on formula_4 korrutise formula_22 tegur. Seega jagab ta tegurit formula_22, mida oligi tarvis tõestada.
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 
formula_37
Korrutame mõlemad pooled arvuga :
formula_38
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 formula_39 ning "n" ja "a" on ühisteguriteta (st nende suurim ühistegur on ). Tuleb tõestada, et arv "n" jagab arvu "b". Et formula_40 siis leidub täisarv "q" nii, et formula_41 Ü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" &lt; "a", siis
formula_42
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 &lt; ("a" – "n") "b" &lt; "ab".
Samamoodi, kui "n" &gt; "a", siis 
formula_43
ja sama argument näitab, et "n" – "a" ja "a" on ühisteguriteta. Saame, et 0 &lt; "a" ("b" − "q") &lt; "ab"}}, ja induktsioonihüpoteesist järeldub, et "n" − "a" jagab arvu ; st, leidub täisarv "r", mille korral formula_44. Järelikult formula_45, järelikult formula_46 Nii et formula_47, järelikult formula_48 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".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, näiteks:
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 formula_52 on peaideaaliring, formula_53 ja formula_4 on taandumatu element ringis formula_52, siis formula_56.
Peale selle tõestatakse tugevamaks peetav väide, et taandumatu elemendi formula_57 genereeritud peaideaal formula_58 on juba maksimaalne ideaal. Peaideaaliringis langevad järelikult lihtsa ideaali ja maksimaalse ideaali mõiste kokku.
Tõepoolest, kui formula_59 on ideaal ning formula_60, siis leidub formula_61 nii, et formula_62. Sellest, et formula_63 järeldub järelikult, et sobiva formula_64 korral formula_65. Et formula_66 on taandumatu, siis formula_67 on ringis formula_68 pööratav element või formula_69 on seal pööratav element. Järelikult kas formula_70 või formula_67 ja formula_66 on assotsieeritud elemendid ning genereerivad sama peaideaali. Kokkuvõttes saame, et formula_73 või formula_74, mis definitsiooni järgi tähendab, et formula_58 on maksimaalne ideaal.
Ajalugu.
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. Seepärast nimetatakse seda üldistust ka Gaussi lemmaks.