בוודאי ידוע לכולכם שישנם אינסוף מספרים ראשוניים. היוונים הקדמונים כבר הוכיחו זאת, ואולי חלקכם מכירים גם את ההוכחה. הקסם בהוכחה הזו הוא שהשאלה הנשאלת נוגעת לאבני היסוד של המתמטיקה – ושאלות כאלו כרוכות ברובן בהוכחות סבוכות שלעתים רק מתמטיקאים ספורים שולטים בהן. אך ההוכחה היוונית מובנת גם לתלמיד רגיל בבית הספר היסודי. נביא אותה בקיצור, כי היא דוגמה נפלאה להוכחה בדרך השלילה – ואף נציע בה שיפור משמעותי אך פשוט להפליא לגבי המסקנה.
והנה ההוכחה בדרך השלילה:
נניח שיש רק מספר סופי n של מספרים ראשוניים:
נסדר אותם לפי גודלם בסדר עולה וניצור מספר M שיהיה מכפלת כולם בתוספת 1. כלומר: (p1*p2*p3*…*pn)+1=M.
לפי ההנחה, מאחר ש-M שונה מכל המספרים הראשוניים, הוא אינו ראשוני וחייב להתחלק לפחות באחד מהם, אבל זה לא ייתכן, כי המכפלה בסוגריים מכילה (לפי ההנחה) את כל המספרים הראשוניים, ולכן מתחלקת בכל אחד מהמספרים הראשוניים – אך בתוספת ה-1 הוא אינו מתחלק באף אחד מהם. סתירה!
לכן M הוא מספר ראשוני נוסף או שהוא מתחלק במספר ראשוני שאינו כלול ברשימה הסופית ולכן גדול מכולם. סתירה!
ומכאן, לא ייתכן שיש מספר סופי של ראשוניים, והוכחנו שמספרם אינסופי.
להוכחה הזו יש בונוס נוסף: אנו יודעים שבין pn ל- Mחייב להיות לפחות מספר ראשוני אחד. אפשר לשפר מעט את התוצאה הזו ובמקום להוסיף 1 למכפלה – להוריד אחד, והמסקנה עדיין תישאר בלחי שינוי.
נתרגם את M לדוגמאות על בסיס המספרים הראשוניים הראשונים 2, 3, 5, 7, 11. לגבי שני הראשונים, אזי M=2*3-1=5, ואכן זה המספר הראשוני הראשון אחרי 3.
משלושת הראשונים נקבלM=2*3*5-1=29 , ואכן 29 הוא מספר ראשוני – אך החמצנו בדרך עוד שישה ראשוניים אחרים: 7, 11, 13, 17, 19, 23.
ההחמצה הולכת וגדלה ככל שהראשוניים האחרונים גדלים. לדוגמה: אם נחפש בשיטה זו מספר ראשוני אחרי 11, כל שנדע הוא שקיים לפחות מספר אחד כזה בין 11 ל-2*3*5*7*11-1=2,309, אך בפועל אנו יודעים שקיימים מאות כאלה ושהבא בתור הוא 13 – רחוק מאוד מ-2,309...
האם ניתן לשפר את השיטה הזאת ולקבל תחום חיפוש קטן בהרבה?
אכן קיימים שיפורים עצומים. לדוגמה: משפט שאומר שבין כל n ל-2n קיים לפחות ראשוני אחד – במקרה שלנו בין 11 ל-22. ככל ש n-גדל - מספר הראשוניים בין n ל-2n מתקרב למספר הראשוניים עד ל-n. אך ההוכחה של משפטים כאלה דורשת "מתמטיקה גבוהה", בעוד שאנחנו מחפשים "הוכחה יוונית" פשוטה וקלה, שאמנם לא תצמצם את 2,309 ל-22, אך תאפשר לצמצם באופן ניכר את טווח החיפוש של מספר ראשוני.
ואכן, שיפור פשוט בהוכחה היוונית משדרג את הטווח.
נדגים לגבי אותם חמישה מספרים ראשוניים. נבחר במספר M=(5*11)-(2*3*7)=13. הוא לא מתחלק באחד מחמשת המספרים הראשוניים הראשונים, כי כל ראשוני כזה כלול במכפלה אחת ולא כלול בשנייה. והנה יש לנו סכום שאינו מתחלק בראשוניים הכלולים בו.
בשיטה זו אכן צמצמנו את תחום החיפוש בין 2,309 ל-11 ל-13, שהוא עצמו הראשוני הראשון! האם מצאנו דרך קלה להפליא לגלות את הראשוני הראשון בלי להזדקק ל"מתמטיקה גבוהה"?
שימו לב: אילו היינו בוחרים לחלק את המכפלות אחרת, למשל (11*7)-(2*3*5)=47 – התוצאה הייתה פחות טובה! אך אם תנסו למצוא בדרך זו את המספר הבא אחרי 13, תגלו את 17:
2*7*13=182
3*5*11=165
182-165=17
שהוא מושלם גם בהשוואה למשפט על 2n!
חישבו מהי הדרך הטובה ליצור M קטן ככל האפשר עבור כל סידרה עולה של כל המספרים הראשוניים שמצאנו, כדי לחפש בטווח הזה את הראשוני הבא.
בבלוג הבא נדון גם בכך.
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
