Lemat Euklidesa

Lemat Euklidesa to uogólnienie twierdzenia 30 z VII księgi Elementów Euklidesa. Treść lematu jest następująca:

Jeżeli liczba naturalna dzieli iloczyn dwóch innych liczb naturalnych i jest względnie pierwsza z jedną z nich, to jest dzielnikiem drugiej.

Można to zapisać w następującej postaci:

$n|ab \and \gcd (n,a)=1\Rightarrow n|b$

Nazwy lemat Euklidesa często używa się w odniesieniu do 30 twierdzenia, a nie jego uogólnienia. Twierdzenie to mówi, że jeżeli liczba pierwsza dzieli iloczyn dwóch liczb naturalnych, to dzieli co najmniej jedną z nich:

$p|ab \Rightarrow p|a \or p|b$

Powyższa własność charakteryzuje liczby pierwsze i stanowi motywację definicji ideału pierwszego. Twierdzenie 30 i jego uogólnienie są wykorzystywane głownie w teorii liczb, zwłaszcza w dowodach zasadniczego twierdzenia arytmetyki.

Zobacz też

• Algorytm Euklidesa
• Zasadnicze twierdzenie arytmetyki