Eukleidese lemma

Eukleidese lemma ehk Eukleidese esimene teoreem on üks oluline lemma klassikalises aritmeetikas ja elementaarses arvuteoorias, mis ütleb:

Kui algarv Mall:Math jagab kahe täisarvu korrutist Mall:Math, siis Mall:Math 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 \mathbb{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 $\mathbb{N}$. Eukleidese aegadel Bézout' lemmat ei tuntud. Bézout' lemma ütleb, et kui Mall:Math ja Mall:Math on ühisteguriteta täisarvud (st neil ei ole ühiseid jagajaid peale 1 ja −1), siis leiduvad täisarvud Mall:Math ja Mall:Math nii, et

$rx+sy=1.$

Olgu $a,b\in \mathbb{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 $sp+ta=1$. Kui seda võrdust korrutada arvuga $b$ ja pisut teisendada, saame

$p(sb)+(ab)t=b$.

Eelduse kohaselt eksisteerib täisarv $c\in \mathbb{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 Mall:Math ja Mall:Math on ühisteguriteta ning coprime, and assume that Mall:Math. Bézout' lemma järgi leiduvad Mall:Math ja Mall:Math nii, et

$rn+sa=1.$

Korrutame mõlemad pooled arvuga Mall:Math:

$rnb+sab=b.$

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

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 Mall:Math). 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 aon ühisteguriteta, siis n = 1 ning see, et n jagab arvu b, järeldub triviaalselt.

Kui n < a, siis

$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 – n) b < ab.

Samamoodi, kui n > a, siis

$(n-a)q=a(b-q),$

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 Mall:Math; st, leidub täisarv r, mille korral $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"

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

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 elemendd. Salhulgas kehtib ta Eukleidese ringides,, näiteks:

• Gaussi täisarvude ring $\mathbb{Z}[i].$
• Ühe muutuja polünoomide ring $K[x]$ üle korpuse $K.$

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

Üldistus peaideaaliringidele

Lemma kehtib ka (kommutatiivsetes) peaideaaliringides. Kui $H$ on peaideaaliring, $a,b,p\in H$ ja $p$ on taandumatu element ringis $H$, siis $p\mid ab\Rightarrow p\mid a\vee p\mid b$.

Peale selle tõestatakse tugevamaks peetav väide, et taandumatu elemendi $p$ genereeritud peaideaal $⟨p⟩$ on juba maksimaalne ideaal. Peaideaaliringis langevad järelikult lihtsa ideaali ja maksimaalse ideaali mõiste kokku.

Tõepoolest, kui $M\subseteq H$ on ideaal ning $⟨p⟩\subseteq M$, siis leidub $m\in H$ nii, et $M=⟨m⟩$. Sellest, et $p\in M=⟨m⟩$ järeldub järelikult, et sobiva $c\in H$ korral $p=mc$. Et $p$ on taandumatu, siis $m$ on ringis $H$ pööratav element või $c$ on seal pööratav element. Järelikult kas $M=⟨m⟩=H$ või $m$ ja $p$ on assotsieeritud elemendid ning genereerivad sama peaideaali. Kokkuvõttes saame, et $M=H$ või $M=K1ok⟨p⟩$, mis definitsiooni järgi tähendab, et $⟨p⟩$ 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. Selepärast nimetatakse seda üldistust ka Gaussi lemmaks.