סימני חלוקה

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

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

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

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

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

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

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

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

נתחיל מ-2. מכיוון ש-10 מתחלק ב-2, אז $latex 10\equiv0\left(\mbox{mod }2\right)$, ולכן גם $latex 100\equiv0$ (באופן כללי אם $latex a$ מתחלק במספר כלשהו, אז גם $latex ab$ מתחלק בו, לכל $latex b$ שלם שבו נכפול את $latex a$), ובאופן כללי $latex 10^{k}\equiv0$ לכל $latex k\ge1$. זה אומר שמתקבלת המשוואה הבאה: $latex 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 של ספרת האחדות, $latex a_{0}$. בדיוק אותו דבר עובד גם עבור חלוקה ב-5; כשמסתכלים על המספר מודולו 5 מקבלים את $latex a_{0}$ ולכן כל שנותר לבדוק הוא אם $latex a_{0}$ שווה ל-5 או 0. ובדיוק אותו דבר עובד עבור חלוקה ב-10; גם כאן די להסתכל על הספרה האחרונה ולראות אם היא 0 (כי אף ספרה אחרת לא מתחלקת ב-10).

כפי שודאי הבנתם, 2 ו-5 אינם מספרים קדושים – פשוט יש להם את המזל לחלק את 10, שהוא בסיס הספירה שלנו. אם היינו עובדים בבסיס 12 (כש-$latex A$ מייצג 10 ו-$latex 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. במילים אחרות, נקבל $latex 10^{k}a_{k}+10^{k-1}a_{k-1}+\dots+10a_{1}+a_{0}\equiv10a_{1}+a_{0}\left(\mbox{mod }4\right)$. לכן מספיק להסתכל על שתי הספרות האחרונות, כלומר על המספר $latex 10a_{1}+a_{0}$ ולהגיד אם הוא מתחלק ב-4. כמובן, תוכלו לטעון כאן שהייתי יכול לעשות יותר מזה – מכיוון ש-$latex 10\equiv2\left(\mbox{mod }4\right)$, הייתי יכול לטעון שמספיק להסתכל על המספר $latex 2a_{1}+a_{0}$ ולשאול את עצמי אם הוא מתחלק ב-4, אבל אני טוען שזה לא בהכרח קל יותר. נניח, נסתכל על 72: אפשר להשתמש בטריק שלי כדי לקבל ש-72 מתחלק ב-4 אם ורק אם $latex 2\cdot7+2=14+2=16$ מתחלק בו; אבל החישוב הזה בראש לוקח זמן כלשהו, ואולי יותר פשוט כבר לזכור בעל פי אילו מספרים עד 100 מתחלקים ב-4 (אצלי, לפחות, אני אכן זוכר ללא מאמץ אותם, כשם שאני זוכר את לוח הכפל). לכן מעדיפים לרוב להסתפק בטריק של "שתי הספרות האחרונות".

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

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

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

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

עכשיו אני רוצה לעבור ל-11. עבורו, הכוח של החשבון המודולרי מתגלה באופן המובהק והיפה ביותר, לטעמי. אם נשאל את עצמנו למה שקול 10 מודולו 11, התשובה המיידית היא 10, כי כשמחלקים את 10 ב-11 הגדול ממנו, נותרים עם שארית 10. זה לכאורה מקשה למדי על להבין מה יהיו חזקות של 10 מודולו 11 ולכן לא ברור איך להשתמש בשיטה עבור 11, אבל שינוי קטן בנקודת המבט הופך את הכל למובן מאליו. שימו לב שמתקיים $latex 10\equiv-1\left(\mbox{mod }11\right)$ שכן אף פעם לא אסרתי על שילוב מספרים שליליים במשחק המודולו, ועל פי ההגדרה שנתתי, לפיה $latex a\equiv b\left(\mbox{mod }n\right)$ אם $latex n$ מחלק את $latex a-b$, השקילות הזו אכן תקפה. כעת שימו לב מה קורה: $latex 10^{2}\equiv\left(-1\right)^{2}\equiv1\left(\mbox{mod }11\right)$, ואילו $latex 10^{3}\equiv\left(-1\right)^{3}\equiv-1\left(\mbox{mod }11\right)$ וכן הלאה וכן הלאה – באופן כללי $latex 10^{k}\equiv\left(-1\right)^{k}\left(\mbox{mod }11\right)$ ולכן החזקות של 10 מודולו 11 "מזפזפות"בין 1 ובין מינוס 1. לכן אם נפעיל את הכל על מספר כללי נקבל $latex 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 כי $latex 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) $latex a,b$ ושניהם מחלקים את $latex n$, אז גם מכפלתם $latex ab$ מחלקת את $latex n$ (בכיוון ההפוך ברור שאם המכפלה מחלקת את $latex n$ אז כל אחד מהם לחוד מחלק את $latex n$ – מדוע?). באופן כללי לא מספיק להסתכל על הגורמים הראשוניים וצריך להתייחס גם לחזקות שלהם. כך למשל, מספר מתחלק ב-12 אם הוא מתחלק הן ב-4 והן ב-3, שכן $latex 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 אנו בודקים הוא $latex a$. נסמן את ספרת האחדות שלו ב-$latex b_{0}$, וכעת $latex a-b_{0}$ מתחלק ב-10, ולכן אפשר לסמן $latex b=\frac{a-b_{0}}{10}$, ובמילים אחרות $latex a=10b+b_{0}$, כש-$latex b$ הוא המספר שמתקבל מ-$latex a$ על ידי הסרת ספרות האחדות. אם נסתכל על זה מודולו 7 נקבל את המספר $latex 3b+b_{0}$. אם המספר הזה מתחלק ב-7, אז מתקיים $latex 3b+b_{0}\equiv0\left(\mbox{mod }7\right)$, כלומר אחרי העברת אגפים נקבל $latex 3b\equiv-b_{0}\left(\mbox{mod }7\right)$. מכיוון ש-$latex -1\equiv6\left(\mbox{mod }7\right)$, הרי שנקבל $latex 3b\equiv6b_{0}\left(\mbox{mod }7\right)$, ולאחר צמצום: $latex b\equiv2b_{0}\left(\mbox{mod }7\right)$. נחזיר את $latex 2b_{0}$ לאגף שמאל ונקבל $latex b-2b_{0}\equiv0\left(\mbox{mod 7}\right)$, וזה סימן החלוקה שלנו, כי לא ברור איך אפשר לצמצם את זה עוד.

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

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

27 תגובות בנושא “סימני חלוקה”

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

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

  3. תודה רבה, מאוד מעניין. זה בדיוק מסוג הדברים שלימדו אותנו בכיתה ה' ומאז מעולם לא שאלתי את עצמי למה זה עובד…

  4. במסכת עבודה זרה ט' ע"ב יש סימן התחלקות ב-7…

    חות מזה מאוד פשוט לבדוק האם מספר מתחלק ב-7: כותבים אותו בבסיס 8, ובודקים האם סכום הספרות מתחלק ב-7. 🙂

  5. לגבי סימן החלוקה ב7 לא הייתי קורה לזה מזל. אלא בעצם ניסיון לחלק את המספר לשני מספרים שקל לחשב אותם ה 2 יצא ולא בטעות. אנחנו מנסים להקטין את הספר אבל לוודא שהמספר שהורדנו כזה מספר שיקל על החישוב למחוק את ספרת העשרות להוריד פעמים ממנה משאר המספר הוא כמו להוריד 21*ספרת היחידות יש לזכור ש 21 מתחלק ב 7. ולכן עם נוריד 21*ספרת היחידות נקבל מספר מהסוג a*10 ואם זה מתחלק ב 7 גם a מתחלק ב 7 זאת אומרת הורדנו מספר שמתחלק ב 7. ואם המספר שנשאר מתחלק ב 7 כל המספר מתחלק ב 7. באותה צורה אפשר להגיע שסימן החילוק של 13 הוא מחיקת ספירת האחדות ולהוריד 9 פעמים ממנה מהמספר שנותר או לחליפין להוסיף 4 פעמים ממנה.

  6. בתגובה לתגובתו של צבי:
    הסימן המופיע בגמרא נוח רק למספרים קטנים-יחסית (שם מדובר בסדר גודל של מאות עד אלפים), והוא אומר בקיצור:
    המספר 100k+j שקול מודולו 7 למספר 2k+j

    ומי שרוצה סימני חלוקה נוספים – יכול לקרוא בויקיפדיה http://he.wikipedia.org/wiki/%D7%9E%D7%91%D7%97%D7%A0%D7%99_%D7%94%D7%AA%D7%97%D7%9C%D7%A7%D7%95%D7%AA

  7. לא ברור לי למה אתה כותב שסימן חלוקה דומה ל7 לא יעבוד בבסיס 12. אם אינני טועה, הסימן המקביל המתאים הוא b+7b0. באופן כללי, במידה ואתה מחפש סימן חלוקה למספר זר לבסיס שלך תמיד יהיה סימן מהצורה הזו (b+Xb0, כאשר X תלוי במחלק ובבסיס, הוא כמובן קטן תמיד מהבסיס). זה לא תמיד יהיה נוח (כי X עשוי להיות גדול בערכו המוחלט), אבל זה תמיד יהיה.

  8. ל7 בהחלט יש סימן חלוקה – חלק אותו לקבוצות של 6 ספרות וחבר אותן, וכך באופן איטרטיבי עד שתקבל קבוצה של פחות מ-6 ספרות. זה אולי לא מי יודע מה נוח בראש ולא באמת עוזר ברוב מוחלט של המקרים היום-יומיים, אבל למספר בין מאות ספרות זה ה-ר-ב-ה יותר יעיל מהשיטה שתארת (שזמן הריצה שלה זהה למה שקורה אם מחלקים חילוק ארוך וזהו) וכבונוס-זה גם משמר שארית. משפט אוילר מוכיח בקלות שלכל מספר קיים סימן חלוקה בסגנון.
    (אפשר להגיד שבפוסט דיברת רק על סימני חלוקה בע"פ, אבל לדעתי כדאי להביא את התמונה השלמה).

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

    (אני לא בטוח בקשר לניתוח הסיבוכיות שלך).

  10. יש מצב שאני מתבלבל בסיבוכיות, אבל הרעיון הוא שאם אני נותן לך מספר בין 6000 ספרות, אתה תצטרך בשיטה שלך לעשות 6000 פעולות, שאם ככה כבר עדיף לעשות חילוק ארוך וזהו. בשיטה שהצגתי תצטרך לעשות 1000 פעולות חיבור – מייגע הרבה פחות, ואת 6 הספרות האחרונות ניתן לחלק בחילוק ארוך (ויתרון נוסף-שמרנו על השארית)
    שוב-אפשר לטעון שאנחנו מדברים רק על מה שאפשר לעשות בראש וזהו, אבל לטעמי הרבה יותר מעניין לדבר על הבעיה בהקשר כולל יותר, בפרט כשזה גם מוכיח מייד שזה קיים לכל מספר.

  11. עכשיו אני שם לב שלכל ספרה יהיו 1000 פעולות חיבור, כך שיצאתי די נעל.
    ובכל זאת – חלוקה לקבוצות זה שיטה כוללת ולא אד-הוקית, שמוכיחה שיש פה משהו מעבר לדבר נחמד שפועל אקראית על מספרים.

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

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

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

    נ.ב: השיטה שלך לא יכולה לעבוד לכל המספרים( בפרט לחזקות של 2 יש בעיה)

  13. אוריאל, יש הבדל מהותי בין סדר גודל לוגריתמי ובין סדר גודל של לוגריתם בריבוע, כשמדובר על אלגוריתמים על מספרים, ובפרט כאלו בסיסיים.

  14. אוריאל, מה שצריך לעשות זה לפרק את המספר לשני מספרים זרים, אחד מהחזקות של 2-ו-5 והשני זר ל-10. מכאן אני מניח שתוכל להמשיך לבד.
    כוונתי ב"אד הוקי" זה שבסוף הפוסט נשארים עם תחושה של "אה, סימני התחלקות זה סתם משהו שפועל בצורה אקראית לגמרי, לפעמים מצליח ולפעמים לא, בלי שום חוקיות מאחוריו" לדעתי מן הראוי להבהיר שכאשר מסתכלים קצת מעבר לחישובים התלת ספרתיים בראש, אפשר לקבל שיטה כללית שעובדת לכל מספר ולכל בסיס, גם אם היא לא תעזור לקנות במכולת.

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

  16. כנראה שכבר לא נשכנע אחד את השני, אבל בכל זאת אני רוצה לציין שהמון פעמים ראיתי אותך מתרעם בבלוג על מקומות שמציגים משהו חלקי ולא מדויק ומטעים את הקורא. לדעתי להגיד לקורא שלמצוא סימני חלוקה זה דבר אקראי ונסמך מזל שלפעמים עובד ולפעמים לא זאת הטעיה. אבל זאת רק דעתי.
    חוץ מזה – תודה רבה על ההשקעה הרבה שלך באתר!

  17. כפי שאמרתי, אני לא רואה את מה שאתה מתאר כאן כ"סימן חלוקה" יותר מאשר פעולת המודולו במחשב היא "סימן חלוקה" ולכן אני לא חושב שאני מטעה אף אחד או נותן מידע חלקי. הייתי שמח מאוד לגלות שיש דרך שיטתית לבנות סימני חלוקה אבל איני מכיר כזו.

  18. גדי, לגבי תגובתך האחרונה (מלפני שנתיים, אבל לא נורא) – לצערי לא מצאתי חוקיות בערכי k המתקבלים עבור אותה פעולה של 7 המראה כי x =(7) 10b + b0 אבל אני מאמין שעם האלגוריתם האוקלידי תוכל להראות שקיים כזה לכל ראשוני

  19. בקשר לסימן חלוקה ל-7 ודומיו, השיטה די פשוטה (ומכלילה במובן מסוים גם את 3 ואת 11).
    אם ספרת האחדות של המחלק היא 1 מכפילים את ספרת האחדות של המחולק ביתר ומוסיפים ליתר של המחולק, לדוגמא, אם רוצים לבדוק את ההתחלקות של 372 ב-31 מכפילים את 2 ב-3 ומקבלים 6, מחסירים מ-37 ומקבלים את 31 (מתחלק בעצמו).
    אם ספרת האחדות של המחלק היא 9 (או באופן כללי d-1) עושים אותו הדבר רק שמחברים ובמקום ביתר של המחלק משתמשים ביתר ועוד 1. לדוגמא, אם רוצים לבדוק את ההתחלקות של 133 ב-19 מכפילים 3 ב-2 (היתר של 19 ועוד 1), מקבלים 6, מחברים ל-13 ומקבלים 19 (מתחלק בעצמו).
    במקרה שספרת האחדות של המחלק היא 7 או 3, מכפילים ב-3 ומשתמשים בסימן ההתחלקות של המספר הזה (סימן ההתחלקות ב-7 הוא דוגמא מצוינת).
    כמובן שאת השיטות אפשר להכליל לבסיסים שונים, לדוגמא בבסיס 12 אם ספרת היחידות היא 5 או 7 מכפילים ב-5 ובבסיס 7 אם ספרת היחידות היא 2 או 5 מכפילים ב-3 ואם היא 3 או 4 מכפילים ב-2, תמיד בהפכי מודלו הבסיס (או בנגדי שלו מודלו הבסיס, מה שיותר קטן).

  20. אפשר להשתמש בעובדה ש 7*11*13=1001 וכמו שעשית ב 11 לחבר ולחסר לחילופין כל שלשה של ספרות. עם המספר התלת ספרתי המתקבל אפשר לעשות את התעלול היפה שעשית וגם לבדוק חלוקה עבור 13 על הדרך.
    באותו אופן אפשר לבדוק חלוקה ב 37 על סמך זה ש 37|999.

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *