שלום רב,

האם כמות המספרים הראשוניים היא בהכרח אינסופית?

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

אם כן, מהו האלגוריתם לבניית מספר ראשוני כך שיהיה גדול ממספר נתון?

כמו כן, אם כן אשמח לדעת באיזה מידה כמות המספריים הראשוניים הולכת וקטנה, והאם יהיה נכון לאמר שאם היא קבוצה אינסופית אז היא בעלת תכולה אפס?

בתודה מראש,

יואב זילברמן

ליואב שלום רב,

לא ידוע תפריט לבניית מספרים ראשוניים, אבל לא קשה להוכיח שלכל מספר טבעי נתון N יש מספר ראשוני גדול ממנו:

לשם כך נסתכל במכפלה !N של כל המספרים הטבעיים מ- 1 עד N. N! מתחלק בכל מספרים טבעי מ-1 עד N, ולכן המספר Q=N!+1 משאיר שארית 1 בחלוקה בכל אחד מהם, ובוודאי אינו מתחלק באף מספר טבעי עד N. אם Q אינו ראשוני, אזי חייב להיות לו גורם ראשוני, אבל גורם זה חייב להיות גדול מ-(N כיוון שאין ל- Q גורמים קטנים מ- (. מכאן שיש אינסוף מספרים ראשוניים (זוהי הוכחתו בת 2500 השנים של אוקלידס!). צפיפות המספרים הראשוניים אכן הולכת וקטנה כל שאנו מתקדמים בסדרת הטבעיים, ובין N המספרים הטבעיים הראשונים נמצאים בקירוב N/logN מספרים ראשוניים (זהו משפט המספרים הראשוניים – ראה בויקיפדיה). אני מניח שלכך אתה מתכוון במילים "תכולה 0".

בברכה,