תורת המספרים, המחלק המשותף המקסימלי והכפולה המשותפת המינימלית, אלגוריתם אוקלידס

אלגוריתם אוקלידס הוא שיטה יעילה לחישוב המחלק המשותף המקסימלי (ממ"מ) של שני מספרים שלמים. הוא מבוסס על העיקרון ש-`\text{GCD}(a, b) = \text{GCD}(b, a \pmod{b})`. שאלות כוללות יישום האלגוריתם והבנת השימוש בו, כולל הגרסה המורחבת למשוואות דיופנטיות לינאריות.

• שאלה

  בחדר יש כיסאות עם `4` רגליים ועם `3` רגליים. כאשר על כל הכיסאות התיישבו אנשים, נהיה `39` רגליים בחדר (לא נשארו אנשים שעומדים). כמה כיסאות מכל סוג יש בחדר?

  נושאים:

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

• שאלה

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

  ב. אותה השאלה, אבל במקום הכל של 5 ליטרים יש כלי של 4 ליטרים.

  נושאים:

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

• שאלה

  בארץ הקסומה יש רק שני סוגים של מטבעות: `16` ל"ק (לירות קסומות) ו-`27` ל"ק. האם ניתן לקנות מחברת שעולה לירה קסומה אחת ולקבל עודף מדויק?

  נושאים:

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

• חילוק פשוט

  לפעמים שאלה פשוטה מאוד באריתמטיקה אלמנטרית תגרום למבוכה רבה. לדוגמה, אני רוצה לחלק את ארבעת המספרים, `701, 1,059, 1,417`, ו-`2,312`, במספר הגדול ביותר האפשרי שישאיר את אותה שארית בכל מקרה. איך אני אמור להתחיל לעבוד? כמובן, על ידי מערכת ניסויים מייגעת אפשר עם הזמן לגלות את התשובה, אבל יש שיטה די פשוטה לעשות זאת אם רק תוכל למצוא אותה.
  נושאים:

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