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

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

סימני חלוקה משפט אוילר ומשפט פרמה הקטן

• החידה של הבנקאי

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

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

• שאלה

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

  ב. הוכיחו כי  בין `11` מספרים טבעיים תמיד אפשר לבחור שניים שהפרש שלהם מתחלק ב-`10`.

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-5 וב-25