סימני חלוקה

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

מה זה סימן חלוקה? דוגמה היא הדבר הטוב ביותר: מספר מתחלק ב-3 אם סכום הספרות שלו מתחלק ב-3. מה שיש לנו כאן היא שיטה פשוטה - “כלל אצבע” - לבדיקה אם משהו מתחלק ב-3. אפשר לבדוק אם משהו מתחלק ב-3 על ידי ביצוע חילוק ארוך עם שארית, כמו שלמדנו ביסודי, ובדיקה אם השארית היא אפס או לא; אבל כלל האצבע של סכום הספרות הוא פשוט וקל בהרבה. אפילו אם המספר שלנו הוא גדול כך שסכום הספרות הוא גדול, אפשר להפעיל את אותו תעלול שוב על סכום הספרות. בקיצור, השיטה הזו מאפשרת לנו לדעת מאוד בקלות אם משהו מתחלק ב-3, במקום להתאמץ ולחלק. קסם לכל הדעות.

מה שחשוב להבין בכל הנוגע לסימני התחלקות (ולכן אדגיש אותו שוב ושוב בפוסט) הוא שהקסם הזה תלוי בבסיס הספירה שלנו. בסיס ספירה אומר בכמה ספרות אנחנו משתמשים - בסיס עשרוני פירושו שיש עשר ספרות. הסימון “23” בבסיס עשרוני אומר “שתי עשרות ועוד שלוש אחדות”, כאשר ה-10 שב”עשרות”נובעת מבסיס הספירה. אם היינו סופרים על בסיס שמונה ולא על בסיס עשר, אז 23 היה אומר “2 שמיניות ועוד 3 אחדות”, כלומר את המספר תשע-עשרה (שנכתב בבסיס עשרוני כ-19, אבל בבסיס שמונה אין לו בכלל משמעות - כי בבסיס שמונה משתמשים רק בספרות מ-0 ועד 7, ולכן 9 לא רלוונטית בכלל).

באופן כללי, מספר שנכתב בבסיס עשרוני באופן הבא: \( a_{k}a_{k-1}\dots a_{1}a_{0} \) כאשר כל \( a_{i} \) היא ספרה (כלומר, בין 0 ל-9), ערכו הוא \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0} \). ואם לא היינו עוסקים בבסיס עשרוני אלא בבסיס \( d \) עבור \( d \) כללי ערכו היה \( d^{k}a_{k}+d^{k-1}a_{k-1}+\dots+da_{1}+a_{0} \). הרעיון של בסיסי ספירה שונים נראה מוזר למי שהתרגל רק לבסיס ספירה עשרוני, ושאלה מתבקשת היא “אם אנחנו בבסיס גדול מ-10, נניח 16, מאיפה מגיעות כל הספרות הנוספות?” - מה שעושים בפועל הוא להשתמש באותיות מהא”ב הלטיני (\( A,B,C,D,E,F \) במקרה של בסיס 16), אבל זה לא יהיה חשוב כל כך להמשך.

סימני החלוקה שאנחנו מדברים עליהם הם בעצם שיטות לצמצם את המספר \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0} \) למספר אחר, קטן יותר, שהוא פונקציה של הספרות של המספר המקורי ושניהם מתחלקים או לא מתחלקים באותו מספר שאת ההתחלקות בו אנחנו בודקים. הדרך לעשות זאת היא באמצעות כלי חשוב ביותר בתורת המספרים (ובכלל) - חשבון מודולרי.

הרעיון הבסיסי שבחשבון מודולרי הוא להפסיק לדבר על שוויונות ולהסתפק בצורה חלשה יותר של שוויון: \( a\equiv b\left(\mbox{mod }n\right) \) (“\( a \) שקול ל-\( b \) מודולו \( n \)”) אומר שהשארית שמשאירים \( a \) ו-\( b \) כאשר מחלקים אותם ב-\( n \) היא זהה. ברור שאם \( a=b \) אז גם \( a\equiv b\left(\mbox{mod }n\right) \) לכל \( n \); אבל ההפך כמובן שאינו נכון. למשל, \( 3\equiv10\left(\mbox{mod }7\right) \). כדאי לזכור גם ניסוח אלטרנטיבי להגדרה שנתתי למעלה: \( a\equiv b\left(\mbox{mod }n\right) \) אם \( n \) מחלק את \( a-b \). מעתה אכתוב בקיצור \( a\equiv b \) ואשמיט את ה-\( \mbox{mod }n \) כל עוד ברור על איזה \( n \) מדובר (או שיהיה ברור שמדובר על \( n \) “כללי”, כלומר שהטענה שאני טוען נכונה לכל \( n \)).

חשבון מודולרי מקיים את כללי החשבון ה”רגילים” וכאן כוחו: אם \( a\equiv b \) וגם \( x\equiv y \) אז \( a+x\equiv b+y \) וגם \( a\cdot x\equiv b\cdot y \). למשל, אם ידוע ש-\( x+3\equiv17 \) אז מכיוון ש-\( -3\equiv-3 \) (אמרנו שכל מספר שקול לעצמו) אפשר לחבר \( -3 \) לשני האגפים ולקבל \( x\equiv14 \). בצורה הזו אפשר לפתור משוואות גם יותר מתוחכמות: למשל, אם \( 2x\equiv5\left(\mbox{mod }7\right) \) אז כדי לפתור את המשוואה משתמשים בתעלול - כופלים את שני האגפים ב-\( 4 \) ומקבלים \( 8x\equiv20\left(\mbox{mod }7\right) \). אבל את המשוואה הזו אפשר לפשט: מכיוון ש-\( 8\equiv1\left(\mbox{mod }7\right) \) אז \( 8\cdot x\equiv1\cdot x\left(\mbox{mod }7\right) \), כלומר אפשר להחליף את המופע של 8 ב-1, ובדומה את 20 אפשר להחליף ב-6, ומקבלים \( x\equiv6\left(\mbox{mod }7\right) \).

סימן חלוקה עבור \( n \) מתקבל מכך שמסתכלים על המספר \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0} \)מודולו \( n \) ושואלים את עצמנו מה קיבלנו. המשמעות היא שאפשר להחליף את כל המקדמים של ה-\( a_{i} \)-ים במספר ששקול להם מודולו \( n \), ולעתים קרובות המספר הזה יהיה פשוט בהרבה - זה תלוי הן ב-\( n \) והן בבסיס הספירה שלנו. בואו נראה כמה דוגמאות.

נתחיל מ-2. מכיוון ש-10 מתחלק ב-2, אז \( 10\equiv0\left(\mbox{mod }2\right) \), ולכן גם \( 100\equiv0 \) (באופן כללי אם \( a \) מתחלק במספר כלשהו, אז גם \( ab \) מתחלק בו, לכל \( b \) שלם שבו נכפול את \( a \)), ובאופן כללי \( 10^{k}\equiv0 \) לכל \( k\ge1 \). זה אומר שמתקבלת המשוואה הבאה: \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0}\equiv a_{0}\left(\mbox{mod }2\right) \), ולכן שאלת החלוקה ב-2 של המספר כולו שקולה לשאלת החלוקה ב-2 של ספרת האחדות, \( a_{0} \). בדיוק אותו דבר עובד גם עבור חלוקה ב-5; כשמסתכלים על המספר מודולו 5 מקבלים את \( a_{0} \) ולכן כל שנותר לבדוק הוא אם \( a_{0} \) שווה ל-5 או 0. ובדיוק אותו דבר עובד עבור חלוקה ב-10; גם כאן די להסתכל על הספרה האחרונה ולראות אם היא 0 (כי אף ספרה אחרת לא מתחלקת ב-10).

כפי שודאי הבנתם, 2 ו-5 אינם מספרים קדושים - פשוט יש להם את המזל לחלק את 10, שהוא בסיס הספירה שלנו. אם היינו עובדים בבסיס 12 (כש-\( A \) מייצג 10 ו-\( B \) מייצג 11). אז מכיוון שהן 2 והן 3 מחלקים את 12 הטריק שלנו היה עובד עבור שניהם. למשל, המספר “שמונה-עשרה” שמתחלק גם ב-2 וגם ב-3 מיוצג בבסיס 12 בתור 16, כלומר ספרת האחדות היא 6, והיא מתחלקת הן ב-2 והן ב-3, ולכן המספר כולו מתחלק ב-2 וב-3. זה מראה לנו שההבדל בין 2 ו-3 בכל הנוגע לסימן החלוקה שלהם בבסיס 10 (2 דורש הצצה בספרת האחדות, בעוד 3 דורש סיכום של הספרות) הוא לא משהו מהותי שטבוע בלב המתמטיקה, אלא משהו שרירותי שנובע מהבחירה שלנו לעבוד עם בסיס 10 ולא עם בסיס 12.

בואו נעבור עכשיו ל-4. לצערנו, 4 לא מחלק את 10, אבל הוא כן מחלק את 100 ולכן גם כל חזקה גדולה יותר של 10. במילים אחרות, נקבל \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0}\equiv10a_{1}+a_{0}\left(\mbox{mod }4\right) \). לכן מספיק להסתכל על שתי הספרות האחרונות, כלומר על המספר \( 10a_{1}+a_{0} \) ולהגיד אם הוא מתחלק ב-4. כמובן, תוכלו לטעון כאן שהייתי יכול לעשות יותר מזה - מכיוון ש-\( 10\equiv2\left(\mbox{mod }4\right) \), הייתי יכול לטעון שמספיק להסתכל על המספר \( 2a_{1}+a_{0} \) ולשאול את עצמי אם הוא מתחלק ב-4, אבל אני טוען שזה לא בהכרח קל יותר. נניח, נסתכל על 72: אפשר להשתמש בטריק שלי כדי לקבל ש-72 מתחלק ב-4 אם ורק אם \( 2\cdot7+2=14+2=16 \) מתחלק בו; אבל החישוב הזה בראש לוקח זמן כלשהו, ואולי יותר פשוט כבר לזכור בעל פי אילו מספרים עד 100 מתחלקים ב-4 (אצלי, לפחות, אני אכן זוכר ללא מאמץ אותם, כשם שאני זוכר את לוח הכפל). לכן מעדיפים לרוב להסתפק בטריק של “שתי הספרות האחרונות”.

בואו נעבור כעת ל-8. הוא אינו מחלק את 100 אבל כן את \( 1,000 \), ולכן - כבר ניחשתם - די לבדוק את שלוש הספרות האחרונות. כמקודם גם כאן אפשר לפשט ולהסתפק בבדיקת המספר \( 4a_{2}+2a_{1}+a_{0} \). כאן זה כבר תעלול יעיל יחסית, כי מי זוכר כבר אילו מספרים עד 1,000 מתחלקים ב-8.

שימו לב שמתקיים \( 2^{2}=4 \) ו-\( 2^{3}=8 \). אם כן, האם זה מקרי שכדי לבדוק את \( 2^{2} \) היינו צריכים להסתכל על שתי הספרות האחרונות וכדי לבדוק את \( 2^{3} \) היינו צריכים להסתכל על שלושתן? ודאי שלא. הסיבה היא פשוטה: מכיוון ש-\( 10=2\cdot5 \), ברור ש-\( 2^{2} \) לא מחלק את 10, אבל שכאשר נעלה בריבוע את \( 10 \) זה דווקא כן יתקיים, כי העלאה כזו בריבוע מעלה כל גורם בריבוע - \( 10^{2}=2^{2}\cdot5^{2} \). באופן דומה, העלאה בחזקה שלישית של 10 מבטיחה ש-\( 2^{3} \) יחלק את התוצאה, וכן הלאה. אם כן, הקריטריון הכללי הוא זה: כדי לבדוק אם \( 2^{k} \) מחלק מספר שנתון בבסיס 10, די לבדוק את \( k \) הספרות האחרונות. באופן עוד יותר כללי, אם מספר נתון בבסיס \( n \) וידוע לנו ש-\( d \) מחלק את \( n \), אז כדי לראות אם \( d^{k} \) מחלק את המספר, די לבדוק את \( k \) הספרות האחרונות שלו (ולמעשה, לפעמים אפשר להסתפק עוד בפחות ספרות - מתי? מדוע?).

טוב, מיצינו את המבחנים ה”פשוטים”, בואו נעבור למבחן המתוחכם יותר, זה של 3. כאן אנחנו מתחילים לראות את הכוח האמיתי של חשבון מודולרי. שימו לב ש-\( 10\equiv1\left(\mbox{mod }3\right) \), ולכן אנחנו יודעים בקלות מהן כל החזקות של 10 מודולו 3, מבלי שנצטרך לעשות עוד שום חישוב נוסף; זאת מכיוון ש-\( 10^{2}\equiv1^{2}\left(\mbox{mod 3}\right) \) ובאופן כללי \( 10^{k}\equiv1^{k}\left(\mbox{mod }3\right) \), ולכן כל החזקות של 10 שקולות ל-1 מודולו 3. אם נפעיל את התוצאה הזו על המספר שאנו רוצים לבדוק חלוקה בו, נקבל \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0}\equiv a_{k}+a_{k-1}+\dots+a_{0} \). קיבלנו באגף ימין בדיוק את סכום הספרות. פשוט ויפה.

השיטה תעבוד לכל מספר \( n \) כך ש-10 שקול ל-1 מודולו \( n \), אבל יש רק עוד אחד כזה: 9. זו הסיבה שבגללה השיטה עובדת בדיוק באותו האופן עבור 9. ואם היינו בבסיס 12, אז השיטה לא הייתה עובדת לא עבור 3 ולא עבור 9 (עבור 3, כזכור, המצב היה קל עוד יותר) אבל היא כן הייתה עובדת עבור 11. ואם היינו בבסיס 8, היא הייתה עובדת עבור 7 - למשל, 412 בבסיס 8 (שהוא המספר “שלוש מאות עשרים ושתיים”) בבירור מתחלק ב-7 כי \( 4+1+2=7 \). אני שוב רוצה להבהיר כאן את הנקודה המרכזית - ה”תעלול של 3”הוא בכלל לא תעלול של 3; זהו רעיון כללי ויפה, שבמקרה בבסיס 10 תקף עבור 3 ו-9 אבל בבסיסים אחרים יהיה תקף למספרים אחרים.

עכשיו אני רוצה לעבור ל-11. עבורו, הכוח של החשבון המודולרי מתגלה באופן המובהק והיפה ביותר, לטעמי. אם נשאל את עצמנו למה שקול 10 מודולו 11, התשובה המיידית היא 10, כי כשמחלקים את 10 ב-11 הגדול ממנו, נותרים עם שארית 10. זה לכאורה מקשה למדי על להבין מה יהיו חזקות של 10 מודולו 11 ולכן לא ברור איך להשתמש בשיטה עבור 11, אבל שינוי קטן בנקודת המבט הופך את הכל למובן מאליו. שימו לב שמתקיים \( 10\equiv-1\left(\mbox{mod }11\right) \) שכן אף פעם לא אסרתי על שילוב מספרים שליליים במשחק המודולו, ועל פי ההגדרה שנתתי, לפיה \( a\equiv b\left(\mbox{mod }n\right) \) אם \( n \) מחלק את \( a-b \), השקילות הזו אכן תקפה. כעת שימו לב מה קורה: \( 10^{2}\equiv\left(-1\right)^{2}\equiv1\left(\mbox{mod }11\right) \), ואילו \( 10^{3}\equiv\left(-1\right)^{3}\equiv-1\left(\mbox{mod }11\right) \) וכן הלאה וכן הלאה - באופן כללי \( 10^{k}\equiv\left(-1\right)^{k}\left(\mbox{mod }11\right) \) ולכן החזקות של 10 מודולו 11 “מזפזפות”בין 1 ובין מינוס 1. לכן אם נפעיל את הכל על מספר כללי נקבל \( 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0}\equiv\left(-1\right)^{k}a_{k}+\left(-1\right)^{k-1}a_{k-1}+\dots+a_{1}-a_{0}\left(\mbox{mod }11\right) \). המסקנה? סימן החילוק של 11 דומה מאוד לזה של 3 ו-9, פרט לכך שלא מחברים את כל הספרות, אלא מחברים ומחסרים לסירוגין את הספרות. למשל, 165 בבירור מתחלק ב-11 כי \( 1-6+5=0 \). זה ללא ספק סימן החילוק האהוב עלי.

ושוב - אם היינו בבסיס 12, זה לא היה עובד עבור 11, אבל כן עובד עבור 13; ובבסיס 8 זה היה עובד כך עבור 9, וכן הלאה.

טיפלנו ב-2,3,4,5,8,9,10,11. מי נשארו? נשאר 6, ונשאר 7. 6 הוא קל - כבר ביסודי למדנו ש”מספר מתחלק ב-6 אם הוא מתחלק גם ב-2 וגם ב-3”. הסיבה לכך היא ש-2 ו-3 הם הגורמים הראשוניים של 6, ומשפט ידוע מתורת המספרים האלמנטרית שאומר כי אם יש לנו שני מספרים זרים (בלי גורם משותף גדול מ-1) \( a,b \) ושניהם מחלקים את \( n \), אז גם מכפלתם \( ab \) מחלקת את \( n \) (בכיוון ההפוך ברור שאם המכפלה מחלקת את \( n \) אז כל אחד מהם לחוד מחלק את \( n \) - מדוע?). באופן כללי לא מספיק להסתכל על הגורמים הראשוניים וצריך להתייחס גם לחזקות שלהם. כך למשל, מספר מתחלק ב-12 אם הוא מתחלק הן ב-4 והן ב-3, שכן \( 12=4\cdot3 \). שימו לב שלמרות שהגורמים הראשוניים של 12 הם 3 ו-2, לא יכלתי להסתפק בחלוקה ב-2 והייתי חייב לדבר על חלוקה ב-4 (אחרת הייתי טוען בעצם שכל מי שמתחלק ב-6 מתחלק גם ב-12). האבחנה הזו מצביעה על כך שאנחנו לא חייבים סימן חילוק לכל מספר; רק לכאלו שהם חזקה של ראשוני. לכל מספר אחר אפשר להציע סימן חילוק שאומר “אם אני מתחלק בכל הגורמים הזרים שלך, אני מתחלק בך”.

וזה משאיר אותנו רק עם הראשוני 7. הנמסיס של סימני החילוק בבסיס 10 (בבסיס 8 ראינו שהוא טריוויאלי, למשל). הבעיה כאן היא שהחזקות של 10 “מתפרעות”כשמסתכלים עליהן מודולו 7. 10 שקול ל-3 מודולו 7, ולכן 100 (10 כפול 10) יהיה שקול ל-9 (3 כפול 3) שבעצמו שקול ל-2. החזקה הבאה תהיה שקולה ל-6 (למה?) וזו שאחריה ל-4. ואחר כך? ל-5. ואז? ל-1. ואז נחזור ל-3. שימו לב שעברנו על כל השאריות האפשריות מודולו 7 פרט ל-0. למתקדמים מבינינו, זה אומר ש-10 הוא יוצר של החבורה הכפלית מודולו 7, אבל זה לא באמת חשוב לענייננו פרט לתחושה של “נוסחה פשוטה כבר לא תצא לנו מזה”.

הדרך לפשט את העניינים בכל זאת היא זו: נניח שהמספר שאת החלוקה שלו ב-7 אנו בודקים הוא \( a \). נסמן את ספרת האחדות שלו ב-\( b_{0} \), וכעת \( a-b_{0} \) מתחלק ב-10, ולכן אפשר לסמן \( b=\frac{a-b_{0}}{10} \), ובמילים אחרות \( a=10b+b_{0} \), כש-\( b \) הוא המספר שמתקבל מ-\( a \) על ידי הסרת ספרות האחדות. אם נסתכל על זה מודולו 7 נקבל את המספר \( 3b+b_{0} \). אם המספר הזה מתחלק ב-7, אז מתקיים \( 3b+b_{0}\equiv0\left(\mbox{mod }7\right) \), כלומר אחרי העברת אגפים נקבל \( 3b\equiv-b_{0}\left(\mbox{mod }7\right) \). מכיוון ש-\( -1\equiv6\left(\mbox{mod }7\right) \), הרי שנקבל \( 3b\equiv6b_{0}\left(\mbox{mod }7\right) \), ולאחר צמצום: \( b\equiv2b_{0}\left(\mbox{mod }7\right) \). נחזיר את \( 2b_{0} \) לאגף שמאל ונקבל \( b-2b_{0}\equiv0\left(\mbox{mod 7}\right) \), וזה סימן החלוקה שלנו, כי לא ברור איך אפשר לצמצם את זה עוד.

מה סימן החלוקה אומר בפועל? שעלינו לקחת המספר המקורי, להעיף ממנו את ספרת האחדות, ומהמספר שהתקבל לחסר פעמיים את ספרת האחדות, ולבדוק אם זה מתחלק ב-7. כך למשל עבור 133 אנחנו רוצים לבדוק אם \( 13-2\cdot3 \) מתחלק ב-7 (וקל לראות שאכן כך מתקיים).

בניגוד ליתר סימני החלוקה, הסימן הזה נראה די אד-הוקי, אפילו ממוזל - אם ננסה לעשות את אותו תעלול בבסיס 12 עבור 7, זה לא יניב שום דבר מוצלח. אם תרצו, אפשר לראות בכך הוכחה לגדולתו של בסיס 10; ומצד שני, יש מספיק דברים מוצלחים בבסיסים אחרים כדי להזכיר לנו ש-10 התקבע באופן שרירותי והנימוק האמיתי היחיד שאפשר להביא לזכותו הוא האצבעות שלנו.