Eukleideen Lemma

Kaikkien tämän artikkelin lukujen oletetaan olevan kokonaislukuja , ellei toisin mainita.

Eukleideen lemma on alkeislukuteorian klassinen tulos . Se on muotoiltu lauseeksi 30 kirjassa VII Euclid's Elements ja se on avain aritmeettisen peruslauseen todistukseen . Nykyaikainen muotoilu [1] :

Jos useiden tekijöiden tulo on jaollinen alkuluvulla , niin ainakin yksi tekijöistä on jaollinen luvulla . $s$ $s$

Esimerkki. 19 on alkuluku, ja se jakaa Siksi yksi tekijöistä on jaollinen 19:llä, nimittäin: $19019=133\cdot 143.$ $133=19\cdot 7.$

Jos se ei ole alkuluku, niin lause voi epäonnistua. Esimerkki: jaollinen 20:llä, mutta mikään tekijöistä ei ole jaollinen 20:llä. $s$ $4\cdot 15=60$

Todiste

Olkoon se jaollinen :lla , mutta ei :llä . Sitten ja ovat koprime , Siksi on kokonaislukuja ja sellainen, että $x\cdot y$ $s$ $x$ $s$ $x$ $s$ $u$ $v$

x\cdot u+p\cdot v=1

Kerrotaan molemmat puolet arvolla , saadaan $y$

(x\cdot y)\cdot u+p\cdot v\cdot y=y.

Molemmat vasemman puolen termit ovat jaollisia : llä , mikä tarkoittaa, että oikea puoli on jaollinen jne . [2] $s$ $s$

Jos tulo on jaollinen luvulla ja koprime , niin [3] on jaollinen $eKr$ $a$ $a,b$ $c$ $a.$

Euklidesin lemma ei päde vain kokonaislukujen renkaassa , vaan myös muissa tekijärenkaissa , joissa alkulukujen roolia ovat pelkistämättömät elementit . Erityisesti se pätee euklidisissa renkaissa [4] , esimerkiksi:

↑ Vinogradov, 1952 , s. kaksikymmentä.
↑ Kaluznin L. A. Aritmetiikan peruslause . - M .: Nauka, 1969. - P. 13 (Lause 4). – 32 s. - ( Suosittuja matematiikan luentoja ).
↑ Bukhshtab A. A. Numeroteoria . - M .: Education, 1966. - S. 46 (Lause 41). — 384 s.
↑ Pituus S. Algebra . - M .: Mir, 1968. - S. 89-90 . — 564 s.

Vinogradov I.M. Numeroteorian perusteet. - M. - L .: GITTL, 1952. - 180 s.
Zhikov V.V. Aritmetiikan peruslause // Soros Educational Journal . - 2000. - T. 6 , nro 3 . - S. 112-117 .

`* Weisstein, Eric W. Euclid's Lemma (englanniksi) Wolfram MathWorld -verkkosivustolla .