לקראת יום העצמאות הקרב ובא החלטנו להקדיש את הכתבה שלנו למספר 60, ותוך כדי כך להתעמק קמעא גם בפירוק מספר לגורמים ראשוניים.
60 הוא מספר מיוחד במינו שמופיע באין-ספור הקשרים מתמטיים. למשל, כל הזוויות במשולש שווה צלעות הן של שישים מעלות, וכך גם הזוויות החיצוניות של משושה משוכלל. כל מעלה מחולקת לשישים חלקים (דקות), שמחולקים בתורם לשישים חלקים קטנים יותר (שניות). המעגל מחולק ל-360 מעלות, שהן שש פעמים 60. שעה מחולקת לשישים דקות ודקה מחולקת לשישים שניות.
כל העובדות הללו אינן מקריות. הן מבוססות על המתמטיקה הבבלית העתיקה שהשתמשה בבסיס 60. הבבלים ירוש ככל הנראה את שיטת הספירה הזו הנ"ל מהשוּמֵרים, אולם ההיסטוריונים של המתמטיקה חלוקים בדעתם מדוע בחרו הבבלים דווקא בבסיס הזה. ההיסטוריון מוריץ קנטור שיער שהבבלים עיגלו את מספר הימים בשנה ל-360 השקול כמובן לשש פעמים 60. אדמונד רוברטסון, לעומת זאת, טוען שהסיבה הייתה שהבבלים השתמשו בשלושת הפרקים של אצבעות הידיים כדי לספור עד שישים.
הגורמים של 60... ובכלל
אחת ההשערות הבולטות ביותר מתבססת על תכונה מאוד מיוחדת של המספר 60: העובדה שהוא המספר הקטן ביותר שיש לו 12 מחלקים שלמים (גורמים) שונים: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 ו-60 עצמו. כמו כן, 60 הוא המספר הקטן ביותר שמתחלק בכל המספרים שבין 1 ל-6. אפשר לפרק את המספר 60 גם לגורמים ראשוניים, בצורה הבאה: 60=2*2*3*5.
פירוק מספר לגורמים או לגורמים ראשוניים אינו תמיד משימה קלה. ככל שהמספר גדול יותר, הפירוק לגורמים הופך להיות אטי ומסובך יותר. זו אחת הסיבות לכך שפרופסור עדי שמיר ממכון ויצמן למדע, יחד עם חבריו רוט ריבסט וליאונרד אדלמן מאוניברסיטת MIT, הדשתמשו בקושי הזה כדי להמציא את שיטת ההצפנה הנפוצה RSA, הקרויה על שם ראשי התיבות של שמות המשפחה שלהם.
שמיר, ריבסט ואדלמן ביססו את שיטת ההצפנה שלהם על כך שקשה מאוד למצוא מספרים שאפשר לפרקם לשני גורמים ראשוניים בלבד (מספרים כאלו נקראים מספרים ראשוניים למחצה). שיטות רבות מאוד הוצעו כדי למצוא את מספר הגורמים של מספר שלם נתון. אחת מהן היא שיטתו של המתמטיקאי הצרפתי הנודע בן המאה ה-18 פייר דה-פרמה, שמאפשרת לנו למצוא לא רק את הגורמים של מספר נתון N אלא גם את התשובה לשאלה אם מספר כלשהו הוא ראשוני. לשיטה הזו יש כמה שלבים ונדגים אותה על המספר 2047.
בשלב הראשון בוחרים מספר k כך ש-k הוא המספר הקטן ביותר הגדול מ-
. במקרה שלנו k=46. בשלב השני בודקים אם k2-N הוא מספר ריבועי מושלם. אם כן, סימן ש-N איננו פריק והוא ראשוני. מספר ריבועי מושלם הוא מספר שהשורש שלו הוא מספר שלם. ישנו משפט שיכול לעזור לנו למצוא אם מספר יכול להיות מספר ריבועי מושלם: מספר המסתיים בספרות 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 או 96 יכול להיות מספר ריבועי מושלם (אך אינו חייב להיות). אם מספר איננו מסתיים בספרות האלו הוא בוודאי אינו מספר ריבועי מושלם.
במקרה שלנו: 462-2047=2116-2047=69. אף על פי ש-69 מופיע ברשימה, כלומר עקרונית יש סיכוי שהוא יהיה מספר ריבועי מושלם, אנו יודעים שהוא איננו כזה ולכן עדיין לא ברור אם N פריק.
בשלב הבא ממשיכים לבדוק את סדרת המספרים k+1)2-N , (k+2)2-N) ... עד ל- N+1)/2). במקרה שלנו צריכים לבדוק את כל הערכים שבין 46 ל-1024! זה אמנם נשמע הרבה, אך בדרך כלל מספיקות בדיקות בודדות כדי להגיע לתשובה נכונה. להפשטת החישוב אפשר להיעזר בנוסחה:
k+1)2-N=k2-N+2k+1), ביטוי שמשמעו פשוט להוסיף 12k לתוצאה בשלב הקודם.
נמשיך לבדוק בשיטה הזו את המקרה שלנו:
מצאנו כבר ש-462-2047=69 מכיון ש-69 איננו מספר ריבועי מושלם, נמשיך לבדוק את המספר הבא: 472-2047=69+2*46+1=162. לפי הכלל של מספרים ריבועיים מושלמים, המספר הזה איננו מופיע ברשימה ולכן איננו מספר ריבועי מושלם. לכן נמשיך הלאה:
482-2047=162+2*47+1=257. לפי הכלל של מספרים ריבועיים מושלמים, המספר הזה איננו מופיע ברשימה ולכן איננו מספר ריבועי מושלם. לכן נמשיך הלאה עוד כמה צעדים עד שנגיע למספר:
562-2047=1089=332– מספר ריבועי מושלם! ולכן 2047 איננו מספר ראשוני!
יתרה מזאת, אפשר לרשום ישר את גורמי המספר: 2047=562-332=(56+33)*(56-33)=89×23. זה מתאפשר תודות לכלל הבא: אם N הוא מספר שניתן לרשמו כ-N2=a2-b2 כאשר a ו-b הם מספרים שלמים, אזי (N2=(a+b)*(a-b.
במקרה הזה שני הגורמים שהתקבלו (89 ו-23) הם מספרים ראשוניים. אם מתקבלים מספרים פריקים, יש לפרק גם אותם לגורמים באותה שיטה.
כמה פעמים 2?
נחזור למספר 60 ונשים לב שהוא גם מכפלה של שלושה מספרים עוקבים: 60=3*4*5=2*2*3*5. זה מעלה שאלה מעניינת נוספת במתמטיקה – כמה פעמים מופיע גורם ראשוני מסוים במכפלה של מספרים עוקבים?
בדוגמה שלמעלה אנו רואים מיד שהמספר 2 מופיע פעמיים במכפלת שלושת המספרים העוקבים: 3, 4 ו-5, אולם כשמחפשים כמה פעמים מופיע הגורם 2 במכפלת המספרים שבין 51 ל-100 המצב קצת מסתבך. אמנם נכתבו אלגוריתמים לפתרון הבעיה הזו, אולם כאן אנחנו רוצים להציג שיטה יפה שפיתח תלמיד שלנו, טל שחם מכיתה ח', המשתתף בחוג למתמטיקה בהתכתבות של מכון ויצמן למדע. ככל הידוע לנו השיטה אינה מוכרת במקומות אחרים.
נמחיש זאת בדוגמה הבאה: נניח שאנחנו רוצים למצוא כמה פעמים מופיע הגורם 2 במכפלת המספרים שבין 51 ל-100. ממלאים טבלה באופן הבא: רושמים את הגבול העליון (100) בעמודה הימנית ואת הגבול התחתון בעמודה השמאלית (51). מחלקים את שני המספרים בגורם שאותו אנו מעוניינים לבחון (2) ורושמים את התוצאה בשורה שמתחת. אם המספר אינו מתחלק בדיוק בגורם, בודקים אם המספר נמצא בעמודה הימנית, מעגלים את תוצאת החלוקה למספר השלם הקרוב כלפי מטה ורושמים אותו; אם המספר נמצא בעמודה השמאלית, מעגלים את תוצאת החלוקה כלפי מעלה.
בעמודה שלישית באותה שורה רושמים בסך הכל כמה מספרים שלמים מצויים בין המספר בעמודה השמאלית לבין המספר בעמודה הימנית, כולל המספרים הקיצוניים עצמם. ממשיכים למלא את הטבלה, כך שבכל פעם מחלקים את המספרים שבשורה בגורם שאותו אנו מעוניינים לבחון, עד שמגיעים לשורה שבה רשומים המספרים 1 ו-1.
כדי למצוא את מספר הפעמים שהגורם מופיע במכפלת המספרים העוקבים, כל שעלינו לעשות הוא לסכם את המספרים שבעמודה השלישית – שימו לב שהמשבצת בפינה השמאלית העליונה חייבת להישאר ריקה). במקרה שלפנינו התשובה היא: 50.
ושוב 60
לסיום נחזור שוב למספר 60 ונודה שהזכרנו רק מעט מהתכונות של המספר המופלא הזה. תכונות נוספות, כגון העובדה ש-60 הוא המכפלה הקטנה ביותר האפשרית של צלעות משולש פיתגוראי, או העובדה שסכום גורמיו של 60 גדול מהמספר עצמו, וכן עובדות מעניינות נוספות, אפשר למצוא באתר המעולה Number Gossip של טניה חובנובה, מתמטיקאית מוכשרת מארצות הברית.
החידה ראתה אור במקור בכתב העת למדע ולמחשבה גליליאו.
יוסי ומיכל אלרן
מכון דוידסון לחינוך מדעי
מכון ויצמן למדע
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום ואנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
