قضیه اقلیدس

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

به برهان خلف فرض کنید که تعداد اعداد اول، نامتناهی نباشد. یعنی متناهی و محدود باشد و تنها $n$ عدد اول به شکل $p_{1},\ldots ,p_{n}$ داشته باشیم. حاصل‌ضرب این $n$ عدد اول را $P$ می‌نامیم:

$P=p_{1}\cdot \ldots \cdot p_{n}$

سپس حاصل‌جمع آن‌ها با یک را $Q$ می‌نامیم: $Q=P+1$. چون $Q$ از همۀ اعداد اول $p_{1}$ تا $p_{n}$ بزرگ‌تر است، پس طبق فرض خلف، $Q$ نمی‌تواند اول باشد. در نتیجه مرکب است. از آنجایی که هر عدد مرکب حداقل یک شمارندۀ اول دارد، پس $Q$ باید بر یکی از اعداد اول$p_{1}$ تا $p_{n}$ بخش‌پذیر باشد. این عدد را $p_{i}$ در نظر بگیرید. پس هم $P$ و هم $Q$ بر $p_{i}$ بخش‌پذیر هستند. در نتیجه تفاضل آن‌ها یعنی $Q-P$ نیز بر $p_{i}$ بخش‌پذیر است. اما این ممکن نیست؛ زیرا $Q-P$ برابر با یک است و عدد یک بر هیچ عدد اولی بخش‌پذیر نیست. پس فرض خلف باطل شد و در نتیجه تعداد اعداد اول، نامتناهی است. $\blacksquare$

جستارهای وابسته

• لم اقلیدس

منابع

• Rosen, K.H. (2012). Discrete Mathematics and Its Applications (به انگلیسی). McGraw-Hill. Retrieved 2015-02-28.