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

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

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

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

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

  • כל מספר טבעי מתחלק ב-1.
  • מספר מתחלק ב-2 (ראו הסבר מורחב) (נקרא גם מספר זוגי) אם ורק אם ספרת האחדות שלו מתחלקת ב-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.
  • מספר מתחלק ב-12 אם ורק אם הוא מתחלק ב-3 וגם ב-4.
  • מספר מתחלק ב-13 (ראו הסבר מורחב) אם ורק אם כשמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת ב 4, מתקבל מספר המתחלק ב-13. מובן שאם עדיין מתקבל מספר שאין אנו יודעים אם הוא מתחלק ב -13, ניתן לחזור על התהליך שוב. למשל, \ 234 מתחלק ב 13 כי  23+4\cdot 4 = 39=3\cdot 13.
  • מספר מתחלק ב 14 אם ורק אם הוא מתחלק גם ב-2 וגם ב-7.
  • מספר מתחלק ב 15 אם ורק אם הוא מתחלק גם ב-3 וגם ב-5.
  • מספר מתחלק ב 18 אם ורק אם הוא מתחלק גם ב-2 וגם ב-9.
  • מספר מתחלק ב-19 אם ורק אם לאחר שמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשתיים, מקבלים מספר שמתחלק ב-19. למשל, 209 מתחלק ב-19 כיוון ש  \ 20+ 2\cdot 9 = 38 . מובן שאם עדיין מתקבל מספר שאיננו יודעים אם הוא מתחלק ב -19 , ניתן לחזור על התהליך שוב.
  • מספר מתחלק ב-21 אם ורק אם הוא מתחלק גם ב-7 וגם ב-3 למשל, 42 מתחלק ב-21 כי הוא מתחלק גם ב-7 (6=42:7) וגם ב-3 (14=42:3).
  • מספר מתחלק ב-22 אם ורק אם הוא מתחלק גם ב-11 וגם ב-2. למשל, 44 מתחלק ב-22 כי הוא מתחלק גם ב-11 (4=44:11) וגם ב-2 (22=44:2).
  • מספר מתחלק ב-23 אם ורק אם לאחר שמוסיפים למספר ללא ספרת האחדות את ספרת האחדות מוכפלת בשבע, מתקבל מספר שמתחלק ב-23. למשל, 414 מתחלק ב-23 כיוון ש- 41+7\cdot 4=69 , 69 מתחלק ב-23.
  • מספר מתחלק ב-29 אם ורק אם הוספת 3 פעמים הספרה האחרונה למספר שמתקבל מהורדת הספרה האחרונה מתחלק ב-29 למשל 319 מתחלק ב-29

31+3\cdot 9=58

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

34-3\cdot 1=31

  • מספר מתחלק ב-100 (או בכל גורם שלו) אם הוא נגמר בשני אפסים (00), ב-1000 אם הוא נגמר בשלושה אפסים (000) וכך הלאה.

באופן כללי, אם המספרים 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 הם אי-זוגיים.

הסבר

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

 \ 318 = 310 + 8 = 31 \cdot 10 + 8 .

אנו יודעים כי 10 מתחלק ב-2 ללא שארית (הרי  \ 10= 5 \cdot 2). מצאנו כי 318 הוא סכום של 2 מחוברים, כשהראשון מביניהם מתחלק ב-2, ולכן נותר רק לדרוש כי המחובר השני, שהוא ספרת האחדות של המספר המקורי, יתחלק ב-2.

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).

הסבר

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

 \ 10= 9+1 =3 \cdot 3+ 1

 \ 100= 99+1 =33 \cdot 3+ 1

 \ 1,000= 999+1 =333 \cdot 3+ 1

 \ 10,000= 9,999+1 =3,333 \cdot 3+ 1

 \ 100,000= 99,999+1 =33,333 \cdot 3+ 1

וכן הלאה. ניקח את לדוגמה את המספר 7,581. הכוונה היא בעצם ל

 \ 7,581= 7 \cdot 1000 + 5 \cdot 100 + 8 \cdot 10 + 1 \cdot 1 .

ונשתמש בעובדה שציינו קודם, כדי לכתוב זאת מחדש:

 \ 7,581= 7 \cdot (3 \cdot 333+1) + 5 \cdot (3 \cdot 33+1) + 8 \cdot (3 \cdot 3+1) + 1 \cdot (0+1) .

נפתח סוגריים, ונקבץ את כל האברים המוכפלים ב 3.

 \ 7,581 =3 \cdot (7 \cdot 333 + 5 \cdot 33 + 8 \cdot 3) + (7+5+8+1) .

גילינו כי  \ 7,581 מורכב מחיבור של שני אברים. האיבר הראשון מתחלק ב 3 בוודאות, כי הוא מכפלה של 3 במספר שלם, והאיבר השני הוא בדיוק סכום הספרות  \ 7+5+8+1=21 . מכיוון שהמחובר הראשון מתחלק ב 3 בוודאות, נותר רק לדרוש כי המחובר השני, שהוא סכום הספרות, יתחלק בשלוש.

 \ 21 מתחלק בשלוש, שהרי \ 2+1 = 3 ואנו יודעים כי  \ 21 = 3 \cdot 7 . לכן  \ 7,581 מתחלק בשלוש. ואכן,  7,581 = 3 \cdot 2527 .

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

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

הסבר

100 מתחלק ב 4 ללא שארית -  \ 100=4 \cdot 25 , ולכן מספר מהצורה \ 100n+a מתחלק ב- 4 אם ורק אם a מתחלק ב- 4.

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

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

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

הסבר

ההסבר דומה מאוד להסבר של סימן החלוקה הקודם. ניתן להציג כל מספר המורכב משתי ספרות ויותר כסכום של ספרת האחדות ומכפלת שאר המספר ב10. ניקח לדוגמה את 765. ניתן לייצגו גם כך:

 \ 765 = 76 \cdot 10 + 5 .

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

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

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

הסבר

נסמן את ספרת האחדות ב \ a, ואת שאר המספר ב  \ b. בדוגמה הנתונה למשל (224),  \ b=22, a=4 .

המספר שאנו בוחנים הוא  \ 10b+a. מבחן החלוקה אומר למעשה ש  \ b-2a מתחלק ב 7 אם ורק אם  \ 10b +a מתחלק גם כן ב 7. קל להראות זאת, כי  \ b-2a מתחלק ב 7 אם ורק אם  \ 10 \cdot (b-2a) מתחלק ב 7, וכשנפתח את הסוגריים נגלה שביטוי זה שווה ל \ 10 b-20 a. כדי להגיע למספר המבוקש, שהוא  \ 10b+a, עלינו להוסיף בדיוק  \ 21 a. הוספנו ביטוי המתחלק ב 7 לביטוי אחר המתחלק ב 7, ולכן סכומם מתחלק ב 7 בוודאות. במילים אחרות, אם  \ 10 b-20 a מתחלק ב 7 אז בהכרח  \ 10b+a מתחלק ב 7, ובכך הוכחנו למעשה את תקפות הסימן.

הסבר פורמלי

נעבוד בשדה השאריות מודולו 7. נסמן את המספר ללא ספרות האחדות ב b, ואת ספרת האחדות ב a. בדוגמה הנתונה למשל (224),  \ b=22, a=4 . השאלה האם המספר מתחלק ב 7 שקולה לשאלה האם המקדמים a,b פותרים את המשוואה

 \ 10 b+a = 0 , השקולה, מודולו 7, למשוואה

 \ 3 b+a = 0 . עתה נכפיל ב  \ 3 ^{-1}, שהוא  \ 5 כי \ 3\cdot 5=15\equiv_7 1 תתקבל המשוואה

\ b + 5 a = 0 , השקולה, מודולו 7, למשוואה

 \ b-2a = 0 וזו היא בדיוק הנוסחה המבוקשת - המספר ללא ספרת האחדות, פחות פעמיים ספרת האחדות.

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

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

הסבר

כל אחד מהמספרים מופיע ככפולה של 10^6. כיוון ש-999999 מתחלק ב-7, ניתן להוריד אותו מבלי לשנות את ההתחלקות, וכך נשאר רק עם המספר עצמו.

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

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

הסבר

ההסבר דומה מאוד להסבר של סימן החלוקה של 4. המספר 1,000 מתחלק ב 8 ללא שארית, שהרי  \ 1,000 = 8 \cdot 125 . נסתכל לדוגמה על המספר 2,064. ניתן להסתכל עליו בתור הסכום

 2,064 = 2,000 + 64 = 2 \cdot 1,000 + 64 .

נפרק את 1,000 למכפלה

 2,064 = 2 \cdot (125 \cdot 8) + 64 .

גילינו ש 2,064 מורכב מסכום של שני מספרים, כשהראשון מתחלק ב 8. לכן, על מנת ש 2,064 יתחלק ב 8 דרוש רק כי המחובר השני יתחלק בארבע, וזהו המספר שיוצרות שתי הספרות האחרונות - 64. ואכן,

\ 2,064 = 258 \cdot 8 .

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

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

הסבר

ההסבר זהה כמעט לגמרי לזה של סימן החלוקה של 3. כל חזקה של 10 נותנת שארית 1 בחלוקה ב 9. לדוגמה:

 \ 10= 9+1 =9 \cdot 1+ 1

 \ 100= 99+1 =9 \cdot 11+ 1

 \ 1,000= 999+1 =9 \cdot 111+ 1

וכן הלאה. מכאן ואילך ההסבר זהה לגמרי.

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

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

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

הסבר

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

 \ 10^n =_{11} (-1) ^n . קל להבין זאת מהסתכלות על החוקיות הבאה:

 \ 10= 11-1

 \ 100= 99+1 = 11\cdot 9 +1

 \ 1,000= 1001-1=11 \cdot 91 -1

 \ 10,000= 9,999+1 = 11 \cdot 909 +1

 \ 100,000= 100,001-1=11 \cdot 9091 -1

 \ 1,000,000= 999,999+1=11 \cdot 90,909 +1

 \ 10,000,000= 10,000,001 -1 =11 \cdot 909,091 -1

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

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

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

הסבר

ההסבר דומה מאוד להסבר של סימן החלוקה של 7.

נסמן את ספרת האחדות ב \ a, ואת שאר המספר ב  \ b. בדוגמה הנתונה למשל (234),  \ b=23, a=4 .

המספר שאנו בוחנים הוא  \ 10b+a. מבחן החלוקה אומר למעשה ש  \ b+4a מתחלק ב 13 אם ורק אם  \ 10b +a מתחלק גם כן ב 13. קל להראות זאת, כי  \ b+4a מתחלק ב 13 אם ורק אם  \ 10 \cdot (b+4a) מתחלק ב 13, וכשנפתח את הסוגריים נגלה שביטוי זה שווה ל  \ 10 b+40 a. כדי להגיע למספר המבוקש, שהוא  \ 10b+a, עלינו להוסיף בדיוק  \ 39 a. הוספנו ביטוי המתחלק ב 13 לביטוי אחר המתחלק ב 13, ולכן סכומם מתחלק ב 13 בוודאות. במילים אחרות, אם  \ 10 b+40 a מתחלק ב 13 אז בהכרח  \ 10b+a מתחלק ב 13, ובכך הוכחנו למעשה את תקפות הסימן.

הסבר פורמלי

נעבוד בשדה השאריות מודולו 13. נסמן את המספר ללא ספרות האחדות ב a, ואת ספרת האחדות ב b. בדוגמה הנתונה למשל (234),  \ a=23, b=4 . השאלה האם המספר מתחלק ב 13 שקולה לשאלה האם המקדמים a,b פותרים את המשוואה

 \ 10 a+b = 0 , השקולה, מודולו 13, למשוואה

 \ -3 a+b = 0 . עתה נכפול ב  \ (-3) ^{-1}, שהוא  \ 4 , כי \ (-3)\cdot 4 =14\equiv_{13} 1. תתקבל המשוואה

\ a + 4 b = 0 , וזו היא בדיוק הנוסחה המבוקשת - המספר ללא ספרת האחדות, ועוד 4 פעמים ספרת האחדות.

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.

הסבר

נסמן את ספרת האחדות ב \ a, ואת שאר המספר ב  \ b. בדוגמה הנתונה למשל (5149),  \ b=514, a=9 .

המספר שאנו בוחנים הוא  \ 10b+a. מבחן החלוקה אומר למעשה ש  \ b+2a מתחלק ב 19 אם ורק אם  \ 10b +a מתחלק גם כן ב 19. קל להראות זאת, כי  \ b+2a מתחלק ב 19 אם ורק אם  \ 10 \times (b+2a) מתחלק ב 19, וכשנפתח את הסוגריים נגלה שביטוי זה שווה ל \ 10 b+20 a. כדי להגיע למספר המבוקש, שהוא  \ 10b+a, עלינו להוסיף בדיוק  \ 19 a. הוספנו ביטוי המתחלק ב 19 לביטוי אחר המתחלק ב 19, ולכן סכומם מתחלק ב 19 בוודאות. במילים אחרות, אם  \ 10 b+20 a מתחלק ב 19 אז בהכרח  \ 10b+a מתחלק ב 19, ובכך הוכחנו למעשה את תקפות הסימן.

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

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

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

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

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

המספר 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 ספרות, נוכל לדעת אם המספר המקורי התחלק במספר השני.

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

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