قضیه اقلیدس

قضیهٔ اقلیدس (به انگلیسی: Euclid's theorem) بیان می‌کند که تعداد اعداد اول، نامتناهی است. این قضیه به روش‌های مختلفی اثبات شده‌است. اقلیدس این قضیه را در کتاب اصول اقلیدس اثبات کرده‌است. اثباتی براساس برهان خلف به شرح زیر است:

به برهان خلف فرض کنید که تعداد اعداد اول، نامتناهی نباشد. یعنی متناهی و محدود باشد و تنها ${\displaystyle n}$

عدد اول به شکل ${\displaystyle p_1,\dots ,p_n}$

داشته باشیم. حاصل‌ضرب این ${\displaystyle n}$

عدد اول را ${\displaystyle P}$

می‌نامیم:

${\displaystyle P=p_1\cdot \dots \cdot p_n}$

سپس حاصل‌جمع آن‌ها با یک را ${\displaystyle Q}$

می‌نامیم: ${\displaystyle Q=P+1}$

. چون ${\displaystyle Q}$

از همۀ اعداد اول ${\displaystyle p_1}$

تا ${\displaystyle p_n}$

بزرگ‌تر است، پس طبق فرض خلف، ${\displaystyle Q}$

نمی‌تواند اول باشد. در نتیجه مرکب است. از آنجایی که هر عدد مرکب حداقل یک شمارندۀ اول دارد، پس ${\displaystyle Q}$

باید بر یکی از اعداد اول${\displaystyle p_1}$

تا ${\displaystyle p_n}$

بخش‌پذیر باشد. این عدد را ${\displaystyle p_i}$

در نظر بگیرید. پس هم ${\displaystyle P}$

و هم ${\displaystyle Q}$

بر ${\displaystyle p_i}$

بخش‌پذیر هستند. در نتیجه تفاضل آن‌ها یعنی ${\displaystyle Q-P}$

نیز بر ${\displaystyle p_i}$

بخش‌پذیر است. اما این ممکن نیست؛ زیرا ${\displaystyle Q-P}$

برابر با یک است و عدد یک بر هیچ عدد اولی بخش‌پذیر نیست. پس فرض خلف باطل شد و در نتیجه تعداد اعداد اول، نامتناهی است. ${\displaystyle ◼}$