תורת המספרים, חשבון השאריות

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

• המספר

  נתון מספר שלם חיובי שקטן מ-2000.
  אם הוא לא מתחלק ב-43 אז הוא מתחלק ב-41,
  אםהוא לא מתחלק ב-53 אז הוא מתחלק ב-43,
  אם הוא לא מתחלק ב-41 אז הוא מתחלק ב-53.
  מצאו את המספר.

  נושאים:

  תורת המספרים -> מספרים ראשוניים אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה לוגיקה -> הגיון תורת המספרים -> המחלק המשותף המקסימלי והכפולה המשותפת המינימלית קומבינטוריקה -> בדיקת מקרים -> תהליכים תורת המספרים -> חלוקה
  מקורות:
  • האולימפיאדה לצעירים, תש"פ, שלב ב, כיתות ג-ד שאלה 6
  • האולימפיאדה לצעירים, תש"פ, שלב ב, כיתות ה-ו שאלה 4

• ספרת היחידות

  למרים יש שמונה כרטיסים עם מספרים תלת ספרתיים עוקבים. ספרת היחידות של המספר הקטן ביותר היא 1,
  ספרת היחידות של המספר הגדול ביותר היא 8. מרים סדרה את הכרטיסים בשורה כך שהמספר הראשון מתחלק ב-2,
  המספר השני מתחלק ב-3, המספר השלישי מתחלק ב-4, וכן הלאה עד המספר השמיני שמתחלק ב-9.
  מהי ספרת היחידות של המספר שמתחלק ב-7?

  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • האולימפיאדה לצעירים, תשפ"א, שלב א, כיתה ט שאלה 6

• מספרים על לוח

  בתחילת היום, על הלוח רשומים ארבעה מספרים שלמים (`a_0,b_0,c_0,d_0`). בכל דקה, דני
  מחליף את ארבעת המספרים שעל הלוח ברביעיית מספרים חדשה לפי הכלל הבא: אם
  המספרים הרשומים על הלוח הם (a,b,c,d), ראשית דני מייצר את המספרים
  `a'=a+4b+16c+64d`
  `b'=b+4c+16d+64a`
  `c'=c+4d+16a+64b`
  `d'=d+4a+16b+64c`
  ולאחר מכן הוא מוחק את המספרים (a,b,c,d) ורושם במקומם את המספרים
  ('a'd',d'c',c'b',b'a). לאילו רביעיות התחלתיות (`a_0,b_0,c_0,d_0`) ירשום דני
  בסופו של דבר רביעיית מספרים שכולם
  מתחלקים ב`5780^5780`

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה תורת המספרים -> חלוקה -> זוגיות אלגברה -> סדרות
  מקורות:
  • אולימפיאדת גיליס, תש"פ שאלה 4

• חילוק סופי

  מצאו את כל ה x,y,z,w השלמים שמקיימים `x^2+y^2=3z^2+3w^2 `.

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

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

• שאלה

  בשורה רשומים שישה מספרים טבעיים עוקבים בסדר עולה. האם ייתכן שסכום הספרות של המספר הראשון הוא 40 וגם שסכום הספרות של המספר האחרון הוא 18?

  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • אולימפיאדת בנו ארבל, 2019, כיתה ח שאלה 1

• שאלה

  המורה חילקה (עם שארית) את מספר התלמידים בשכבה ב-2, ב-3, ב-4, ב-5 וב-9. כשסיכמה את השאריות, קיבלה 18. מצא את מספר התלמידים בשכבה, אם ידוע שהמספר קטן מ-300.

  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה אלגברה -> בעיות מילוליות קומבינטוריקה -> בדיקת מקרים -> תהליכים אריתמטיקה -> חילוק עם שארית
  מקורות:
  • מבחני בחירה ל-IMO בישראל, תשע"א, שלב א שאלה 6

• שאלה

  בכמה דרכים שונות ניתן לבחור 6 ספרות a,b,c,d,e,f שכולן שונות מ-0 (ולא בהכרח שונות זו
  מזו), כך שהמספר השש-ספרתי `ab00cd` יתחלק במספר השש-ספרתי `cd00ef`?
  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • מבחני בחירה ל-IMO בישראל, תשפ"ה, שלב ב שאלה 5

• שאלה

  מספר N יקרא מוצלח אם הוא מקיים את שני התנאים הבאים:
  * N הוא מספר חיובי שלם שמתחלק ב-101,
  * ברישום של N מופיעות בדיוק שתי ספרות לא אפסיות.
  למשל המספר 2020 הוא מוצלח, ואילו המספר 12120 אינו מוצלח כי יש בו 4 ספרות לא אפסיות.
  מצאו את כמות המספרים המוצלחים שקטנים מ- `10^40`.
  נושאים:

  תורת המספרים -> חשבון השאריות -> סימני חלוקה קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • מבחני בחירה ל-IMO בישראל, תשפ"ה, שלב ב שאלה 7

• הבקר של ג'אדקינס

  היירם ב. ג'אדקינס, סוחר בקר מטקסס, היו לו חמש עדרי חיות, שהורכבו משוורים, חזירים וכבשים, עם אותו מספר חיות בכל עדר. בוקר אחד הוא מכר את כל מה שהיה לו לשמונה סוחרים. כל סוחר קנה את אותו מספר חיות, שילם שבעה עשר דולר עבור כל שור, ארבעה דולר עבור כל חזיר ושני דולר עבור כל כבש; והיירם קיבל בסך הכל שלוש מאות ואחד דולר. מהו המספר הגדול ביותר של חיות שיכל להיות לו? וכמה יהיו מכל סוג?
  נושאים:

  אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה אלגברה -> בעיות מילוליות תורת המספרים -> חלוקה
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 35

• ספרות וריבועים

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

  אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 77