Euklido teorema

Euklido teorema – pagrindinė skaičių teorijos teorema, teigianti, kad pirminių skaičių yra be galo daug. Pirmą kartą teoremą įrodė Euklidas savo veikale „Pradmenys“. Yra ne vienas šios teoremos įrodymų.

Euklido įrodymas 
Euklidas pasiūlė įrodymą, paskelbtą savo veikale „Pradmenys“, IX knygoje, 20-ajame teiginyje.

Tegul p1, p2, …, pn – baigtinis pirminių skaičių sąrašas, o P = p1p2…pn – šių pirminių skaičių sandauga. Tegu q = P + 1, tada q yra arba pirminis skaičius, arba sudėtinis skaičius.

 Jeigu q yra pirminis, tada duotas sąrašas yra nepilnas, nes pačio q nėra jame.
 Jeigu q yra sudėtinis, tai tada egzistuoja toks skaičius p, kuris dalina q. Jeigu p būtų sąraše, tai jis dalintų ir P, ir P + 1. Taigi turėtų dalyti ir jų skirtumą, t. y. (P+1) – P = 1. Kadangi joks pirminis skaičius nedalo 1, jis negali būti sąraše. Iš to seka, kad turi būti dar vienas pirminis skaičius, kurio nėra tame sąraše.

Nuorodos 
 

Skaičių teorija