Lemat Euklidesa

Lemat Euklidesa – twierdzenie teorii liczb dotyczące relacji podzielności:

Jeśli liczba naturalna dzieli iloczyn dwóch innych i jest względnie pierwsza z jedną z nich, to dzieli tę drugą.

${\displaystyle \forall n,a,b\in \mathbb {N} :n|ab\land n\perp a\Rightarrow \ n|b.}$

Lematem Euklidesa nazywa się też konsekwencję (szczególny przypadek) tego faktu:

Jeśli liczba pierwsza dzieli iloczyn dwóch liczb naturalnych, to dzieli co najmniej jedną z nich.

${\displaystyle \forall p\in \mathbb {P} ,a,b\in \mathbb {N} :p|ab\Rightarrow p|a\lor p|b.}$

Nazwa upamiętnia Euklidesa, ponieważ drugie z tych twierdzeń pojawia się w jego Elementach, w księdze VII pod numerem 30. Powyższa własność charakteryzuje liczby pierwsze i stanowi motywację definicji ideału pierwszego.

Zastosowanie

Twierdzenie 30 i jego uogólnienie są wykorzystywane głównie w teorii liczb, zwłaszcza w dowodach podstawowego twierdzenia arytmetyki.

Linki zewnętrzne

• Matematyka dyskretna 1, Wykład 10: Teoria liczb, wazniak.mimuw.edu.pl [dostęp 2022-09-28].
• Eric W.E.W. Weisstein Eric W.E.W., Euclid’s Theorems, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2023-08-10].