Euklidovské lemma

Všechna čísla v tomto článku jsou považována za celá čísla , pokud není uvedeno jinak.

Euklidovo lemma je klasickým výsledkem elementární teorie čísel . Je formulován jako věta 30 v knize VII Euklidových prvků a je klíčem k důkazu základní věty aritmetiky . Moderní formulace [1] :

Pokud je součin několika faktorů dělitelný prvočíslem , pak alespoň jeden z faktorů je dělitelný číslem . $p$ $p$

Příklad. 19 je prvočíslo a dělí Proto je jeden z faktorů dělitelný 19, a to: $19019=133\cdot 143.$ $133=19\cdot 7.$

Pokud to není prvočíslo, pak může věta selhat. Příklad: dělitelné 20, ale žádný z faktorů není dělitelný 20. $p$ $4\cdot 15=60$

Důkaz

Nechť je dělitelný , ale ne dělitelný . Pak a jsou coprime , tedy existují celá čísla a taková, že $x\cdot y$ $p$ $X$ $p$ $X$ $p$ $u$ $proti$

x\cdot u+p\cdot v=1

Vynásobením obou stran dostaneme $y$

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

Oba členy na levé straně jsou dělitelné , což znamená, že pravá strana je také dělitelná , atd. [2] $p$ $p$

Pokud je součin dělitelný a coprime , pak [3] je dělitelný $před naším letopočtem$ $A$ $a,b$ $C$ $A.$

Euklidovo lemma platí nejen v kruhu celých čísel, ale i v dalších faktoriálových kruzích , kde roli prvočísel hrají ireducibilní prvky . Zejména to platí v euklidovských prstencích [4] , například:

↑ Vinogradov, 1952 , s. dvacet.
↑ Kalužnin L. A. Základní věta aritmetiky . - M. : Nauka, 1969. - S. 13 (Věta 4). — 32 s. - ( Populární přednášky o matematice ).
↑ Bukhshtab A. A. Teorie čísel. - M .: Vzdělávání, 1966. - S. 46 (Věta 41). — 384 s.
↑ Leng S. Algebra . - M .: Mir, 1968. - S. 89 -90. — 564 s.

Vinogradov I.M. Základy teorie čísel. - M. - L. : GITTL, 1952. - 180 s.
Žikov V.V. Základní teorém aritmetiky // Soros Educational Journal . - 2000. - T. 6 , č. 3 . - S. 112-117 .

`* Weisstein, Eric W. Euclid's Lemma (anglicky) na webových stránkách Wolfram MathWorld .