הוכחת אֵוּקלידס לקיום אינסוף מספרים ראשוניים

בפוסט כאן למדנו על הדרך בה הוכיח אוקלידס כי קיימים אינסוף מספרים ראשוניים. הניסוח המתמטי של ההוכחה פשוט מאוד.

אוקלידס הניח כי קיימת כמות סופית של מספרים ראשוניים:

\(\displaystyle {{p}_{1}},{{p}_{2}},{{p}_{3}}\ldots {{p}_{n}}\)

כעת ניתן להגדיר מספר חדש:

\(\displaystyle {{{p}_{{n+1}}}={{p}_{1}}\cdot {{p}_{2}}\cdot {{p}_{3}}\cdot \ldots \cdot {{p}_{n}}+1}\)

ברור כי המספר \({{p}_{{n+1}}}\) לא מתחלק באף אחד מהמספרים הראשוניים שמהם בנינו אותו, כי השארית תמיד תהיה שווה ל- \({1}\).

נוכל להוסיף את המספר החדש לרשימה המקורית: \({{p}_{1}},{{p}_{2}},{{p}_{3}}\ldots {{p}_{n}},{{p}_{n+1}}\), אבל כעת נוכל באותה שיטה לייצר מספר חדש: \({{p}_{{n+2}}}\), וכן הלאה וכן הלאה.

לכן קיימים אינסוף מספרים ראשוניים.