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

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

• שאלה

  הוכיחו כי קיימות שתי חזקות של `2` שהפרש שלהן מתחלק ב-`2017`.

  נושאים:

  תורת המספרים -> חשבון השאריות קומבינטוריקה -> עקרון שובך היונים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  בהינתן מספר שלם חיובי N, נתבונן בתהליך הבא: נסמן ב-`S(N)` את סכום הספרות של N ניקח את סכום הספרות של `S(N)`  נחזור על הפעולה שוב ושוב עד שנקבל מספר חד ספרתי נקרא למספר הפעמים שביצענו את התהליך הנ"ל עד שקיבלנו מספר חד-ספרתי: "העומק" של N. לדוגמה, העומק של 49 הוא `S(49)=13 -> S(13)=4)2` , הפעולה בוצעה פעמיים( והעומק של 45 הוא 1.

  א) הוכיחו כי לכל מספר N אכן יש עומק סופי, כלומר, שתמיד יתקבל מספר חד-ספרתי בשלב כלשהו של התהליך.

  ב) נסמן ב-`x(n)` את המספר המינימלי (שערכו הקטן ביותר) בעל עומק N. מצאו את השארית של `x(5776)` בחילוק ב-6 .נמקו את תשובתכם!

  ג) מצאו את השארית של המספר `x(5776) - x(5708)` בחילוק ב-2016 .נמקו את תשובתכם!

  הצגת רמז

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

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

• שאלה

  הוכיחו כי מבין חמישה מספרים שלמים ניתן לבחור שניים שהפרש שלהם מתחלק ב-`4`.

  נושאים:

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

• שאלה

  המספרים מ-`1` עד `2n` רשומים בשורה בסדר כלשהו. מוסיפים לכל מספר את אינדקס המקום עליו הוא עומד. הוכיחו כי בין `2n` הסכומים שקיבלנו יש שניים שהפרש שלהם מתחלק ב-`2n`.

  נושאים:

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

• 777

  מהי הספרה האחרונה של המספר `777^777`?

  הצגת רמז

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

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

• שאלה

  מהי הספרה האחרונה של המספר `43^43-17^17`?

  הצגת רמז

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

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

• שאלה

  האם קיים ריבוע שלם שמסתיים בספרות `...2017`?

  נושאים:

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

• שאלה

  נתונים מספרים טבעיים m,n כך ש`m/n <= sqrt 23` הוכיחו כי `m/n+3/{mn} <= sqrt 23`

  הצגת רמז

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

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

• שאלה

  האם יש פתרון בטבעיים למשוואה `x^2 + 12 = y^3` כך ש

  א. x זוגי (קל יותר)

  ב. x אי זוגי

  הצגת רמז

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

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

• סכומי עצרות

  עבור כל מספר שלם חיובי n נסמן `n! = 1*2*3*...*n`

  מצאו את כל המספרים השלמים n כך שהסכום `1! + 2! + 3! + ... + n!` הוא ריבוע של מספר שלם.

  (פורמט פתרון: a,b,c,... כלומר שלושת המספרים הקטנים ביותר מופרדים בפסיקים ללא רווחים, ושלוש נקודות אחרי אם יש יותר פתרונות)

  הצגת רמז

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

  תורת המספרים -> חשבון השאריות אלגברה -> סדרות
  מקורות:
  • תחרות גרוסמן, 2022, בוגרים שאלה 1