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

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

• מספרי המוניות

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

  נושאים:

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

• חידת המאה

  האם תוכלו לכתוב `100` בצורה של מספר מעורב, תוך שימוש בכל תשע הספרות פעם אחת בלבד? המתמטיקאי הצרפתי המכובד, אדוארד לוקאס, מצא שבע דרכים שונות לעשות זאת, והביע את ספקותיו לגבי קיומן של דרכים אחרות. למעשה יש בדיוק אחת-עשרה דרכים ולא יותר. הנה אחת מהן, `91 5742/638`. בתשע מהדרכים האחרות יש באופן דומה שתי ספרות בחלק השלם של המספר, אך לביטוי האחד-עשר יש רק ספרה אחת שם. האם הקורא יכול למצוא את הצורה האחרונה הזו?

  נושאים:

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

• כפל פשוט

  אם נמספר שישה כרטיסים `1, 2, 4, 5, 7`, ו-`8`, ונניח אותם על השולחן בסדר הזה:—

  `1\ \ \ 4\ \ \ 2\ \ \ 8\ \ \ 5\ \ \ 7`

  אנו יכולים להדגים שכדי להכפיל ב-`3` כל מה שצריך זה להעביר את ה-`1` לקצה השני של השורה, וזהו. התשובה היא `428571`. האם תוכלו למצוא מספר שכאשר מכפילים אותו ב-`3` ומחלקים ב-`2`, התשובה תהיה זהה כאילו הסרנו את הכרטיס הראשון (שבמקרה הזה צריך להיות `3`) מתחילת השורה לסופה?

  נושאים:

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

• חידת לוח שנה

  אם סוף העולם יגיע ביום הראשון של מאה חדשה, האם תוכל לומר מה הסיכויים שזה יקרה ביום ראשון?
  נושאים:

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

• שאלה

  נתון מספר ראשוני תלת-ספרתי שכל ספרותיו שונות. ידוע שהספרה האחרונה שלו שווה לסכום של שתי הספרות האחרות. מצאו את כל האפשרויות לספרה האחרונה של המספר הזה.

  הצגת רמז

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

  תורת המספרים -> מספרים ראשוניים תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-2, 4 ו-8 תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-3 וב-9 לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  כל המספרים הזוגיים מ-`12` עד `34 ` רשומים על הלוח ללא רווחים. כתוצאה התקבל המספר

  `121416182022242628303234`

  האם המספר הזה מתחלק ב-`24`?

  הצגת רמז

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

  אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-2, 4 ו-8 תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-3 וב-9
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  על הלוח רשום מספר `100`. מצאו ספרה שמקיימת את התנאי הבא:

  אם נוסיף אותה לרישום של המספר הכתוב על הלוח פעם אחת משמאל ופעם אחת מימין, נקבל מספר שמתחלק ב-`12`.

  הצגת רמז

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

  אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-2, 4 ו-8 תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-3 וב-9 תורת המספרים -> מספרים ראשוניים -> פרוק לגורמים ראשוניים
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  כמה מספרים בין `1` ל-`100` לא מתחלקים לא ב-`2`, לא ב-`5`?

  נושאים:

  אריתמטיקה תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-2, 4 ו-8 תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-5 וב-25 תורת המספרים -> המחלק המשותף המקסימלי והכפולה המשותפת המינימלית תורת הקבוצות תורת המספרים -> חלוקה

• שאלה

  על הלוח רשום מספר דו ספרתי. אבי טוען שספרת האחדות של המספר גדולה פי שניים מספרת העשרות. בני טוען כי המספר מתחלק ב-`9`. גל טוען כי המספר מתחלק ב-`4`. דני טוען כי המספר מתחלק ב-`27`. ידוע כי אחד מהם טועה, והשאר צודקים. איזה מספר כתוב על הלוח?

  נושאים:

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

• מספר קסום 15

  יוסי רושם על הלוח את המספר `15`. אחרי זה דני מוסיף למספר הכתוב על הלוח ספרה אחת מימין וספרה אחת משמאל, כך שהמספר החדש עדיין מתחלק ב-`15`.

  מצאו את המספר הזה. האם יש רק אפשרות אחת?

  הערה: הספרה שמוסיפים משמאל אינה אפס.

  הצגת רמז

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

  תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-3 וב-9 הוכחה ודוגמה -> בניית דוגמה תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-5 וב-25 תורת המספרים -> חלוקה
  מקורות:
  • אתר האינטרנט problems.ru