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 19019 = 133 \cdot 143. Järelikult jagub üks teguritest 19-ga, nimelt 133 = 19 \cdot 7.

Vastunäide kordarvu korral. 4 \cdot 15 = 60 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 p, siis vähemalt üks teguritest jagub arvuga p.

Eukleidese lemmat kasutatakse tavaliselt järgmisel samaväärsel kujul:
:Kui p on algarv, mis jagab täisarvude korrutist ab, ent ei jaga arvu a, siis ta jagab arvu b..

Sellega ekvivalentne on järgmine üldistus: 
: Kui n \in \N jagab korrutist ab ja on ühega teguritest ühistegurita, siis ta jagab teist tegurit.
Tõepoolest, kui n on algarv, tuleb jälle välja ülaltoodud formuleering; kui n on kordarv, siis väide kehtib iga tema algteguri kohta ning seetõttu ka arvu n 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 \N. 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
:
rx+sy = 1.
 

Olgu a,b \in \Z suvalised täisarvud. Eeldusel, et algarv p jagab korrutist ab, ent mitte tegurit a, tuleb näidata, et p on teguri b jagaja.

Eeldusest järeldub muu hulgas, et a ja p on ühisteguriteta. Bézout' lemma järgi eksisteerivad siis kaks täisarvu s ja t nii, et s p + t a = 1. Kui seda võrdust korrutada arvuga b ja pisut teisendada, saame
: p(sb)+ (ab)t = b.
Eelduse kohaselt eksisteerib täisarv c \in \Z, mille korral ab = cp, seega saab p võrduse vasakus pooles sulgude ette viia:
: p (sb + ct)= b.
Järelikult on p korrutise b tegur. Seega jagab ta tegurit b, 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 
:
rn+sa = 1.

Korrutame mõlemad pooled arvuga :
:
rnb+sab = b.

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 n \mid ab ning *n* ja *a* on ühisteguriteta (st nende suurim ühistegur on ). Tuleb tõestada, et arv *n* jagab arvu *b*. Et n \mid ab, siis leidub täisarv *q* nii, et nq=ab. Ü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* n(q-b)=(a-n)b.
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*, siis 
:(n-a)q=a(b-q),
ja sama argument näitab, et *n* – *a* ja *a* on ühisteguriteta. Saame, et 0 b-q=r(n-a). Järelikult (n-a)q=ar(n-a),, järelikult q=ar. Nii et ab=nq=anr,, järelikult b=nr, 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.<br />Järelikult *c* mõõdab arvu *b*.<br /></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 algoritm]]i juures. Praktilistes arvutusülesannetes on lemmal endal ainult allutatud roll.

==Üldistused==
Eukleidese lemma ei kehti mitte ainult [[täisarvude ring]]is, vaid ka teistes [[faktoriaalne ring|faktoriaalsetes ringides]], kus algarvude osa etendavad [[taandumatu element|taandumatud elemendid]]. Sealhulgas kehtib ta [[Eukleidese ring]]ides, näiteks:
* [[Gaussi täisarvud]]e ring <math>\mathbb{Z}[i].</math>
* Ühe muutuja [[polünoom]]ide ring <math>K[x]</math> üle [[korpus (matemaatika)|korpus]]e <math>K.</math>

Gaussi lemma kehtib kõigis [[SÜT-ring]]ides, sealhulgas kõikides [[peaideaaliring]]ides, näiteks [[polünoomide aritmeetika|polünoomide ringides üle korpuse]].

===Üldistus peaideaaliringidele===

Lemma kehtib ka (kommutatiivsetes) [[peaideaaliring]]ides. Kui <math>H</math> on peaideaaliring, <math>a,b,p \in H</math> ja <math>p</math> on [[taandumatu element]] ringis <math>H</math>, siis <math>p \mid ab \Rightarrow p \mid a \lor p \mid b</math>.

Peale selle tõestatakse tugevamaks peetav väide, et taandumatu elemendi <math> p </math> genereeritud [[peaideaal]] <math> \langle p \rangle </math> on juba [[maksimaalne ideaal]]. Peaideaaliringis langevad järelikult [[lihtne ideaal|lihtsa ideaali]] ja [[maksimaalne ideaal|maksimaalse ideaali]] mõiste kokku.

Tõepoolest, kui <math>M \subseteq H</math> on ideaal ning <math> \langle p \rangle \subseteq M </math>, siis leidub <math>m \in H </math> nii, et <math> M = \langle m \rangle </math>. Sellest, et <math>p \in M = \langle m \rangle  </math> järeldub järelikult, et sobiva <math> c \in H</math> korral <math> p= m c </math>. Et <math>p </math> on taandumatu, siis <math>m </math> on ringis <math> H</math> [[pööratav element]] või <math>c </math> on seal pööratav element. Järelikult kas <math> M = \langle m \rangle = H </math> või <math>m </math> ja <math>p </math> on [[assotsieeritud elemendid]] ning genereerivad sama peaideaali. Kokkuvõttes saame, et <math> M = H </math> või <math> M = K1ok\langle p \rangle</math>, mis definitsiooni järgi tähendab, et <math> \langle p \rangle </math> on maksimaalne ideaal.

==Ajalugu==
See lemma esineb esimest korda [[Eukleides]]e "[[Elemendid (Eukleides)|Elementide]]" VII raamatu lausena 30. See tuuakse ära praktiliselt kõigis [[elementaarne arvuteooria|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