מבחני התחלקות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

מבחן חלוקה (נקרא גם סימן חלוקה סימן התחלקות או מבחן התחלקות) הוא דרך מהירה ונוחה לקבוע בבסיס מסוים מתי מספר שלם מסוים מתחלק במספר שלם a ללא שארית. מבחני החלוקה שונים זה מזה, בהתאם לטבעו העשרוני של המספר a, אך לכולם אותו עקרון: צמצום המספר הנבדק למספר פשוט יותר, על ידי חיסור מספר המתחלק ב- a חלקם (כמו סימני החלוקה ב2,3,4,5,11) נותנים גם את השארית וחלקם (כמו 7,13) רק את העובדה שהמספר מתחלק או לאו.

מבחני חלוקה בסיסיים[עריכת קוד מקור | עריכה]

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

  • כל מספר טבעי מתחלק ב-1.
  • מספר מתחלק ב-2 (ראו הסבר מורחב) (נקרא גם מספר זוגי) אם ורק אם ספרת האחדות שלו זוגית.
  • מספר מתחלק ב-3 (ראו הסבר מורחב) אם ורק אם סכום ספרותיו מתחלק ב-3 (למשל: 1962 מתחלק ב-3 כי סכום ספרותיו הוא 18).
  • מספר מתחלק ב-4 (ראו הסבר מורחב) אם ורק אם המספר שיוצרות שתי ספרותיו הימניות מתחלק ב-4 (ספרת העשרות זוגית וספרת האחדות מתחלקת בארבע או ספרת העשרות אי זוגית וספרת האחדות זוגית אך אינה מתחלקת ב-4).
  • מספר מתחלק ב-5 (ראו הסבר מורחב) אם ורק אם ספרת האחדות שלו מתחלקת ב-5 (כלומר, היא 0 או 5).
  • מספר מתחלק ב-6 אם ורק אם הוא מתחלק ב-2 וב-3.
  • מספר מתחלק ב-7 (ראו הסבר מורחב) אם ורק אם לאחר שמחסרים מהמספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשתיים, מקבלים מספר שמתחלק ב-7. למשל, 224 מתחלק ב-7 כיוון ש  \ 22- 2 \cdot 4 = 14 . מובן שאם עדיין מתקבל מספר שאיננו יודעים אם הוא מתחלק ב -7, ניתן לחזור על התהליך שוב.
  • מספר מתחלק ב-8 (ראו הסבר מורחב) אם ורק אם המספר שיוצרות שלוש ספרותיו הימניות מתחלק ב-8.
  • מספר מתחלק ב-9 (ראו הסבר מורחב) אם ורק אם סכום ספרותיו מתחלק ב-9.
  • מספר מתחלק ב-10 אם ורק אם ספרת האחדות שלו היא 0.
  • מספר מתחלק ב-11 (ראו הסבר מורחב) אם ורק אם לאחר שמחסרים ומחברים לסירוגין את ספרותיו מתקבל מספר שמתחלק ב-11. למשל, 924 מתחלק ב-11 שכן \ 9-2+4=11.
    • מבחן נוסף, מספר מתחלק ב-11 אם ורק אם ההפרש שיוצרות שלוש הספרות האחרונות מהמספר שיוצרות שאר הספרות מתחלק ב-11. לדוגמה המספר 948024 מתחלק ב-11 משום 948-024=924 וכאמור 924 מתחלק ב-11.
  • מספר מתחלק ב-12 אם ורק אם הוא מתחלק ב-3 וגם ב-4.
  • מספר מתחלק ב-13 (ראו הסבר מורחב) אם ורק אם כשמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת ב 4, מתקבל מספר המתחלק ב-13. מובן שאם עדיין מתקבל מספר שאין אנו יודעים אם הוא מתחלק ב -13, ניתן לחזור על התהליך שוב. למשל, \ 234 מתחלק ב 13 כי  23+4\cdot 4 = 39=3\cdot 13.
  • מספר מתחלק ב 16 אם ורק אם המספר שיוצרות ארבע ספרותיו הימניות מתחלק ב-16.
  • מספר מתחלק ב 17 אם ורק אם לאחר שמורידים חמש פעמים את הספרה האחרונה ממה שנשאר מקבלים מספר שמתחלק ב-17. למשל, 221 מתחלק ב17 בגלל ש:221: 22 − 1 × 5 = 17.
  • מספר מתחלק ב-19 אם ורק אם לאחר שמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשתיים, מקבלים מספר שמתחלק ב-19. למשל, 209 מתחלק ב-19 כיוון ש  \ 20+ 2\cdot 9 = 38 . מובן שאם עדיין מתקבל מספר שאיננו יודעים אם הוא מתחלק ב -19 , ניתן לחזור על התהליך שוב.
  • מספר מתחלק ב-23 אם ורק אם לאחר שמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשבע, מתקבל מספר שמתחלק ב-23. למשל, 414 מתחלק ב-23 כיוון ש- 41+7\cdot 4=69 , 69 מתחלק ב-23.
  • מספר מתחלק ב-25 אם ורק אם המספר שיוצרות שתי ספרותיו הימניות מתחלק ב-25
  • מספר מתחלק ב 27 אם ורק אם לאחר שמורידים 8 פעמים את הספרה האחרונה ממה שנשאר מקבלים מספר שמתחלק ב-27. למשל, 621 מתחלק ב27 בגלל ש: 621: 62 − (1×8) = 54.
  • מספר מתחלק ב-29 אם ורק אם הוספת 3 פעמים הספרה האחרונה למספר שמתקבל מהורדת הספרה האחרונה מתחלק ב-29 למשל 319 מתחלק ב-29

31+3\cdot 9=58

  • מספר מתחלק ב-31 אם ורק אם הורדת 3 פעמים הספרה האחרונה למספר שמתקבל מהורדת הספרה האחרונה מתחלק ב-31 למשל 341 מתחלק ב-31

34-3\cdot 1=31

  • מספר מתחלק ב-32 אם ורק אם לאחר שמוסיפים 4 פעמים את שתי הספרות הראשונות לשאר. למשל, 1312 מתחלק ב-32 בגלל ש: 1,312: (13×4) + 12 = 64.
  • מספר מתחלק ב 37 אם ורק אם לאחר שמורידים 11 פעמים את הספרה האחרונה ממה שנשאר מקבלים מספר שמתחלק ב-37.
  • מספר מתחלק ב-100 (או בכל גורם שלו) אם הוא נגמר בשני אפסים (00), ב-1000 אם הוא נגמר בשלושה אפסים (000) וכך הלאה.

מספרים שאינם חזקות של מספרים אחרים או ראשוניים, פרט ל-10, לא מופיעים ברשימה וסימן התחלקותם הוא כדלקמן: אם המחולק מתחלק בכל הגורמים הראשוניים של המחלק, המחולק מתחלק גם במחלק. למשל, סימן ההתחלקות של-6 הוא התחלקות בשני גורמיו הראשוניים: 3,2.

באופן כללי, אם המספרים n,m זרים, כגון 3 ו- 4, אז מספר מתחלק במכפלתם אם ורק אם הוא מתחלק בכל אחד מהם לעצמו. לכן סימן החלוקה ב- nm הוא שילוב של שני הסימנים. לדוגמה, המספר 216 מתחלק ב-12=3*4 , מכיוון שהוא מתחלק ב-3 (סכום ספרותיו 9), וגם ב-4 (המספר 16 מתחלק ב-4).

שמירת שארית[עריכת קוד מקור | עריכה]

המבחנים שניתנו לעיל למספרים 7, 13, 19, 23, 29, 31, אינם משמרים את השארית אלא מסוגלים רק לקבוע האם המספר מתחלק בו או לא. כדי לשמור על השארית ניתן לחלק את המספר המקורי לקבוצות שגודלן n כך שהמספר שבו רוצים לבדוק התחלקות מחלק את 10^n-1 ולחבר אותן, וכך שוב ושוב עד שמקבלים מספר עם n ספרות ומטה. השיטה הזאת בדרך כלל לא יעילה לחישובים בעל פה, מאחר שהמספר שנותר בסוף התהליך עשוי להיות גדול.

המבחנים שניתנו לעיל למספרים 2, 3, 4, 5, 6, 8, 9, 10, 11 משמרים את השארית.

2[עריכת קוד מקור | עריכה]

מספר מתחלק ב-2 אם ורק אם ספרת האחדות שלו מתחלקת ב-2. במילים אחרות, מספר הוא זוגי, אם ורק אם ספרת האחדות שלו היא זוגית. לדוגמה, המספרים 8, 72 ו-9746 הם זוגיים, והמספרים 3, 79 ו-957 הם אי-זוגיים.

3[עריכת קוד מקור | עריכה]

מספר מתחלק ב-3 אם ורק אם סכום הספרות שלו מתחלק ב-3. לדוגמה, המספר 201 מתחלק ב 3 כי סכום הספרות הוא 2+0+1=3. גם המספר 837 מתחלק בשלוש כי סכום הספרות הוא 8+3+7=18, ו-18 מתחלק ב-3 כי סכום הספרות של 18 הוא 1+8=9, ו-9 מתחלק בשלוש. המספר 65 לא מתחלק ב-3 כי 6+5=11, ו-11 לא מתחלק בשלוש (כי 1+1=2).

4[עריכת קוד מקור | עריכה]

מספר מתחלק ב 4 אם ורק אם הסכום הנוצר מספרת העשרות שלו מוכפלת בשתיים ועוד ספרת האחדות - מתחלק ב-4. לדוגמה, המספר 1,832 מתחלק ב 4 כי 32 מתחלק ב 4 (3X2 + 2 = 8). המספר 98,214 לא מתחלק ב 4, כי 14 לא מתחלק ב 4 (1X2 + 4 = 6).

5[עריכת קוד מקור | עריכה]

מספר מתחלק בחמש אם ורק אם ספרת האחדות שלו היא 5 או 0. במילים אחרות - מספר מתחלק בחמש אם ורק אם ספרת האחדות שלו מתחלקת בחמש.

לדוגמה, המספרים 85, 100 ו 84,535 מתחלקים בחמש, והמספרים 94, 758, ו74,542 אינם מתחלקים בחמש.

7[עריכת קוד מקור | עריכה]

מספר מתחלק בשבע אם ורק אם לאחר שמחסרים מהמספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשתיים, מקבלים מספר שמתחלק ב-7. למשל, 224 מתחלק ב-7 כיוון ש  \ 22- 2 X 4 = 14 .

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

8[עריכת קוד מקור | עריכה]

מספר מתחלק ב-8 אם ורק אם המספר שיוצרות שלוש ספרותיו הימניות מתחלק ב-8.

9[עריכת קוד מקור | עריכה]

מספר מתחלק ב-9 אם ורק אם סכום ספרותיו מתחלק ב-9. לחלופין מספר חיובי מתחלק ב-9 אם ורק אם סכום הספרות הסופי שלו שווה ל-9.

11[עריכת קוד מקור | עריכה]

מספר מתחלק ב-11 אם ורק אם לאחר שמחסרים ומחברים לסירוגין את ספרותיו מתקבל מספר שמתחלק ב-11 למשל, 924 מתחלק ב-11 שכן 11 = 4 + 2 - 9.

דרך נוספת: מספר מתחלק ב-11 אם ורק אם לאחר שמחסרים מהמספר ללא ספרת האחדות את ספרת האחדות, מתקבל מספר שמתחלק ב-11 למשל, 924 מתחלק ב-11 שכן 88 = 4 - 92

דרך נוספת: מתחילים מן הספרה הימנית ומחלקים את ספרות המספר לזוגות (במקרה של מספר בעל מספר אי-זוגי של ספרות הספרה השמאלית תישאר לבד) לאחר מכן מחברים את הזוגות עד שמקבלים מספר דו-ספרתי שמתחלק ב-11 למשל, 924 מתחלק ב-11 מכיוון שכן 24+9=33

13[עריכת קוד מקור | עריכה]

מספר מתחלק ב 13 אם ורק אם לאחר שמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת בארבע, מקבלים מספר שמתחלק ב-13. למשל, 234 מתחלק ב-13 כיוון ש  \ 23+ 4\cdot 4 = 39 .

19[עריכת קוד מקור | עריכה]

מספר 10a+b מתחלק ב 19 אם ורק אם a+2b מתחלק ב-19. לדוגמה, כדי לבדוק את המספר 5149 מחשבים את \ 514+2\times 9=532. ניתן להמשיך בתהליך ולקבל \ 53+2\times 2=57, ושוב: \ 5+2\times7=19, ולכן 57 מתחלק ב-19, כמו גם 532 ו 5149.

מבחני חלוקה התלויים בבסיס הספירה[עריכת קוד מקור | עריכה]

א. באופן כללי, אם מספר נתון בבסיס ספירה b, ניתן לבדוק אם הוא מתחלק ב-b-1 או בכל מחלק של b-1 על ידי סיכום ספרותיו, כפי שנעשה עבור 9 ו-3 בבסיס 10. כך למשל עבור מספר שנתון בבסיס 8 די לבדוק אם סכום ספרותיו מתחלק ב-7 כדי לדעת אם המספר כולו מתחלק ב-7. ההסבר זהה להסבר של סימן החלוקה של 3 ו-9.

ב. באופן דומה, אם מספר נתון בבסיס ספירה b, ניתן לבדוק אם הוא מתחלק ב-b+1, על ידי חיבור וחיסור ספרותיו לסירוגין, כפי שנעשה עבור 11.

ג. כמו כן, לכל מחלק של bn (כאשר b הוא בבסיס הספירה), מספר מסוים מתחלק בו אם ורק אם n הספרות האחרונות שלו מתחלקות בו. ההסבר זהה להסבר של 2, 5, 4 ו-8 בבסיס 10.

דוגמה ליישום 3 כללים הנ"ל: למספר בבסיס 6 יהיו מבחני חלוקה למספרים 2,3 (לפי כלל ג), 5 (לפי כלל א) ו- 7, (לפי כלל ב). מה שהופך את בסיס 6 לבסיס הקטן ביותר שיש לו מבחני חלוקה פשוטים לארבעת המספרים הראשוניים הראשונים.

מבחני התחלקות כלליים[עריכת קוד מקור | עריכה]

המספר 10x+y מתחלק ב-10a+1 אם ורק אם x+(9a+1)y מתחלק ב-10a+1
המספר 10x+y מתחלק ב-10a+3 אם ורק אם x+(3a+1)y מתחלק ב-10a+3
המספר 10x+y מתחלק ב-10a+7 אם ורק אם x+(7a+5)y מתחלק ב-10a+7
המספר 10x+y מתחלק ב-10a+9 אם ורק אם x+(a+1)y מתחלק ב-10a+9

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

קיום מבחן התחלקות[עריכת קוד מקור | עריכה]

להלן הוכחה שלכל מספר קיים מבחן התחלקות:

ראשית נפרק את המספר לשני מחלקים: אחד מכל הגורמים הראשוניים שהם או 2 או 5, והשני מכל השאר. שני המספרים שהתקבלו זרים, ולכן מספיק להראות שלשניהם קיים סימן התחלקות.

לראשון: אם הוא מהצורה 2^m \cdot 5^n מספיק לבדוק את \max \{ m,n \} הספרות האחרונות.

לשני: המספר זר ל-10 (כי אין בו גורמים 2 או 5) ולכן על פי משפט אוילר קיים k כך שהוא מחלק את 10^k-1. לפיכך, אם נחלק את המספר למספרים באורך k (מתחילים מצד ימין) ונחבר אותם, ונחזור על התהליך איטריטבית עד שנקבל מספר עם פחות מ-k ספרות, נוכל לדעת אם המספר המקורי התחלק במספר השני.

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]