אילו מספרים ניתן לקבל באמצעות חי וחמסה?

אני חושב שזה לא סוד שהמתמטיקה מתגנבת אלינו לעתים קרובות בדרכים מטופשות במיוחד. אחת מהדרכים הללו הייתה הישיבה השבעים-ואחת של הכנסת העשרים-ושלוש שהתקיימה בתאריך 24/8/2020. בישיבה הזו נידונה “הצעת חוק שכר שווה לעובדת ולעובד” ומי שעלה לנאום היה יו”ר ועדת העבודה, הרווחה והבריאות חיים כץ. החוק שעליו דיבר כץ עוסק בהטלת חובה על מעסיק פרטי לאסוף נתונים ולערוך דין וחשבון על רמות השכר ופערי השכר במקום העבודה; עד כאן טוב ויפה. אלא שההחלטה קבעה שהחובה הזו תוטל רק על מעסיק שמעסיק מעל 518 עובדים, וכאן עולה מאליה השאלה - מאיפה המספר הקסום הזה בא?

כמובן, הצינקנים שבחבורה אולי ימלמלו משהו על חברים של כץ שמעסיקים בדיוק 517 עובדים או משהו בסגנון, אבל בואו לא נהיה ציניקנים ונזרום עם ההסבר המופלא של כץ שהסביר “518 זה 100 פעמים חמסה ופעם אחת חי, זה מקור המספר”. כלומר, כץ נימק את מקור המספר 518 בכך שהביטוי \( 5x+18y \) שווה 518 כאשר מציבים \( x=100,y=1 \).

בהמשך לקח כץ את הספק-בדיחה שלו לרמה הבאה, כשאמר שאפשר יהיה בשנת 2022 להרחיב את החוק גם על מעסיקים קטנים יותר שמעסיקים פחות מ-518 עובדים, אבל גם אז: “שיתייחס למספרים חי וחמסה”.

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

ולא, כנראה שכץ לא רציני. בחוק מופיע המספר 518 אבל לא מצאתי שם אזכור לחי, חמסה או המספרים 18 ו-5. אז כנראה שלא נזדקק לתיאוריה המופלאה שאציג בפוסט.

הכוכב של הפוסט הזה יהיה מה שמכונה “המחלק המשותף המקסימלי” של שני מספרים, או “המחלק המשותף הגדול ביותר” ובקיצור ממג”ב (ובאנגלית gcd). יש לי עליו פוסט אבל למה לא להציג את התיאוריה הבסיסית שוב. אם \( a,b \) הם מספרים טבעיים (במקרה שלנו, \( a=5,b=18 \)) הממג”ב שלהם מוגדר להיות המספר \( d \) הגדול ביותר שמחלק את שניהם (בסימון מתמטי, \( d|a \) וגם \( d|b \)). אנחנו יודעים ש-1 בהכרח מחלק את שניהם, אז השאלה לגבי ממג”ב היא האם קיים מספר גדול יותר מ-1 שמחלק את שניהם. במקרה של חי וחמסה לא קיים כזה, כי 5 הוא ראשוני ולכן מתחלק רק ב-1 וב-5, אז אלו שני המספרים היחידים שיש להם פוטנציאל להיות הממג”ב; ו-5 לא מחלק את 18 ולכן אינו יכול להיות הממג”ב. במתמטית מסמנים זאת \( \text{gcd}\left(5,18\right)=1 \).

מה שנפלא כל כך בממג”ב הוא שקל לחשב אותו. התעלול הוא כזה: נניח ש-\( a\ge b \), אז אפשר לחלק את \( a \) ב-\( b \) ולקבל מנה \( q \) ושארית \( r \), כלומר \( a=bq+r \) כך ש-\( 0\le r \) - השארית קטנה מהמספר \( b \) שבו חילקנו. עכשיו לא קשה להוכיח את הטענה הבאה: \( \text{gcd}\left(a,b\right)=\text{gcd}\left(b,r\right) \), כלומר כדי למצוא את הממג”ב של \( a,b \) מספיק למצוא את הממג”ב של \( b \) ושל השארית \( r \) - בצורה הזו אנחנו מקטינים עוד ועוד את גודל המספרים שעליהם אנחנו פועלים, ואפשר להוכיח שמהר מאוד נגיע למספרים קטנים. מתישהו נגיע למצב שבו השארית \( r \) היא 0, מה שאומר ש-\( b|a \), ולכן \( b \) עצמו הוא הממג”ב במקרה זה.

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

1. \( 18=5\cdot3+3 \) (\( q=3 \) וגם \( r=3 \))
2. \( 5=3\cdot1+2 \) (\( q=1 \) והפעם \( r=2 \))
3. \( 3=2\cdot1+1 \) (\( q=1 \) ו-\( r=1 \))
4. \( 2=2\cdot1+0 \) (השארית היא 0 ולכן הממג"ב הוא 1)

לא כל כך ברור למה טרחתי לכתוב את האלגוריתם במפורש אם כבר מצאתי את הממג”ב במקרה הזה, אבל הסיבה לכך היא שהאלגוריתם יודע לתת יותר מאשר את הממג”ב בלבד, אם יודעים לבצע אותו בצורה זהירה. המשפט החשוב והמרתק יותר הוא זה: אם \( g=\text{gcd}\left(a,b\right) \) אז קיימים \( x,y \) שלמים (כלומר, שיכולים להיות שליליים) כך ש-\( d=ax+by \). כלומר, תמיד אפשר לכתוב את הממג”ב של שני מספרים בתור “משהו כפול הראשון ועוד משהו כפול השני”, בדיוק בתבנית של חיים כץ ידידינו.

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

• \( 1=3-2\cdot1 \)

שמציגה את הממג”ב 1 בתור צירוף לינארי של שני האיברים הקודמים - 3 ו-2. מהשלב הקודם, משוואה 2 אפשר לחלץ את 2 ולקבל \( 2=5-3\cdot1 \). נציב אצלנו:

• \( 1=3-\left(5-3\cdot1\right)\cdot1=3\cdot2-5\cdot1 \)

ניקח עוד שלב אחורה ונחלץ את 3 מהשלב הקודם, משוואה 1, ונקבל \( 3=18-5\cdot3 \). נציב אצלנו:

\( 1=\left(18-5\cdot3\right)\cdot2-5\cdot1=18\cdot2-5\cdot7 \)

כלומר, קיבלנו את מה שרצינו: \( 5x+18y=1 \) כאשר \( x=-7 \) ו-\( y=2 \). אפשר היה לחשב את זה בקלות גם ידנית, עם קצת ניסוי וטעיה, אבל האלגוריתם עושה את הקסם הזה גם למספרי ענק, ועל זה בנויה לא מעט מתורת המספרים האלגוריתמית. הנה קוד בשפת פייתון שעושה את זה באופן כללי:

def extended_gcd(a,b):    
    if b == 0:
        return (a,1,0)
    q = a // b
    r = a % b
    (gcd, x, y) = extended_gcd(b,r)
    return (gcd, y, x-q*y)

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

\( 18\cdot2-5\cdot7=1 \)

ואנחנו כופלים את שני האגפים שלה ב-\( n \). אנחנו מקבלים:

\( 18\cdot2n-5\cdot7n=n \)

וסיימנו - מצאנו הצגה של \( n \) בעזרת חי וחמסה! במקרה שלנו, גילינו שאפשר לייצג את 518 גם כך: \( 18\cdot1036-5\cdot3626 \). שימו לב שזה פתרון שונה מזה של חיים כץ (שהוא \( 18\cdot1+5\cdot100 \)) ועם מספרים גדולים יותר, אבל מתמטית הוא תקין באותה מידה, והשיטה הזו עובדת לכל מספר שנרצה לייצג. בעצם ראינו פה מקרה פרטי של משפט כללי: לכל \( a,b \), אפשר לייצג בצורה \( ax+by \) כל מספר שמתחלק על ידי \( \text{gcd}\left(a,b\right) \).

אבל מה קורה אם חיים כץ לא מרשה לנו לחסר? האם נוכל לקבל כך כל מספר טבעי? ובכן, ברור שלא. את 1 עצמו אין לנו סיכוי לקבל כך, כי גם 5 וגם 18 גדולים מ-1 ולכן על ידי חיבור שלהם לא נוכל להגיע אל 1. אז אל אילו מספרים כן ניתן להגיע?

ובכן, הנה האתגר שלנו. נניח שיש לנו ייצוג של מספר: \( n=18x-5y \). כאשר \( x,y \) חיוביים. מה שמפריע לנו זה המינוס הזה שתקוע ליד 5. אני יכול להשתמש בתעלול - לחבר חמסות למשוואה הזו, אבל לחסר ממנה חי-ים, עד שזה “יתאזן”. כדי לעשות את זה, שימו לב לכך ש-\( 90=5\cdot18 \), מה שאומר שאם אני מוסיף 18 עותקים של חמסה למשוואה אבל מחסר 5 פעמים חי, אני אקבל את אותו מספר בדיוק:

\( n=18\left(x-5\right)-5\left(y-18\right) \)

בואו נראה דוגמא קונקרטית כי זה יותר מדי באוויר. למשל, נבחר \( x=12 \) ו-\( y=20 \) ונקבל את הייצוג הבא:

\( 18x-5y=18\cdot12-5\cdot20=216-100=116 \)

אוקיי, אז קיבלנו ייצוג של 116 שכולל חיסור. עכשיו ננקוט בתעלול של לחבר 18 פעמים את 5 ולחסר 5 פעמים את 18 ונקבל:

\( 18\cdot7-5\cdot2=126-10=116 \)

עוד ייצוג ל-116! אבל עדיין עם חיסור. אז אולי נחזור על התהליך עוד פעם, ונקבל:

\( 18\cdot2+5\cdot16=36+80=116 \)

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

ובכן, אתחיל מהתוצאה, כי בהמשך אגלוש למתמטיקה טכנית שאולי אפשר ללכת בה לאיבוד. כל מספר שגדול מהמכפלה \( 15\cdot8=90 \) ניתן לייצוג חיובי שכזה. באופן כללי עוד יותר, אם \( \text{gcd}\left(a,b\right)=d \) אז כל מספר שמתחלק ב-\( d \) וגדול מ-\( \frac{ab}{d} \) ניתן לייצוג מהצורה \( ax+by \) כאשר \( x,y \) לא שליליים. ומה קורה עם מספרים קטנים יותר? אני לא מכיר ייצוג נחמד עבורם - צריך לעבור ולבדוק (אין הרבה אפשרויות). ספציפית עבור 5 ו-18, בדיקה מפורשת מראה שיש רק 34 מספרים שלא ניתנים לייצוג על ידם, והגדול שבהם הוא 67.

בואו נעבור למתמטיקה הכללית. נתחיל מהמקרה הפשוט, שבו \( \text{gcd}\left(a,b\right)=1 \). יש לנו מספר עם הייצוג \( n=ax_{0}+by_{0} \), כשהבעיה היא שלא מובטח לנו ש-\( x_{0},y_{0} \) שניהם אי-שליליים. איך אפשר לכתוב את שאר הייצוגים של \( n \)? כמו שראינו, הטריק הוא לחבר ולחסר את \( a\cdot b \). כלומר:

\( n=ax_{0}+by_{0}=ax_{0}+by_{0}+ab-ab \)

\( =a\left(x_{0}+b\right)+b\left(y_{0}-a\right) \)

(כאן אני מניח במובלע בלי הגבלת הכלליות ש-\( x_{0}<0\le y_{0} \), אבל אפשר לעשות את אותו ניתוח גם במקרה השני)

אפשר לחזור על התעלול הזה כמה פעמים שרוצים, וזה מתבטא בחיבור/חיסור של \( t\cdot ab \) עבור \( t \) שלם כלשהו. מקבלים בסופו של דבר את הייצוג \( n=ax+by \) כאשר

\( x=x_{0}+bt \)

\( y=y_{0}-at \)

והשאלה שלנו היא זו: האם קיים \( t \) שלם כך ש-\( x\ge0 \) וגם \( y\ge0 \)? בשביל שזה יקרה, צריכים להתקיים שני דברים:

• \( x_{0}+bt\ge0 \), כלומר \( t\ge-\frac{x_{0}}{b} \)
• \( y_{0}-at\ge0 \), כלומר \( t\le\frac{y_{0}}{a} \)

במילים אחרות, אנחנו מסתכלים בקטע \( \left[-\frac{x_{0}}{b},\frac{y_{0}}{a}\right] \) ושואלים את עצמנו - האם קיים בו מספר שלם? זה תלוי באורך שלו. קטע מאורך לפחות 1 כולל מספר שלם בתוכו. אורך הקטע הזה הוא בדיוק \( \frac{y_{0}}{a}+\frac{x_{0}}{b}=\frac{ax_{0}+by_{0}}{ab}=\frac{n}{ab} \) ולכן אם \( n\ge ab \) אז אורך הקטע הוא לפחות 1 והייצוג שאנו מחפשים קיים. פשוט עד להפתיע!

עכשיו נעבור למקרה הכללי שבו \( \text{gcd}\left(a,b\right)=d \) ו-\( d \) אולי איננו 1 אלא גדול יותר. במקרה הזה, אפשר לחלק: \( a^{\prime}=\frac{a}{d} \) ו-\( b^{\prime}=\frac{b}{d} \). שתי תוצאות החילוק \( a^{\prime},b^{\prime} \) כן יקיימו ש-\( \text{gcd}\left(a^{\prime},b^{\prime}\right)=1 \) ואפשר להשתמש עליהן בתוצאה שראינו. בואו נראה איך בדיוק.

אנחנו יודעים שאם \( n \) לא מתחלק ב-\( d \), אז אין שום סיכוי שאפשר יהיה להציג את \( n \) בצורה \( ax+by \) מלכתחילה (כי \( d \) מחלק את שני המחוברים ולכן מחלק את הסכום כולו). אז נניח ש-\( d \) כן מחלק את \( n \) ונסמן \( n^{\prime}=\frac{n}{d} \). כעת, אם \( n\ge\frac{ab}{d} \) אז \( n^{\prime}=\frac{n}{d}\ge\frac{ab}{d\cdot d}=\frac{a}{d}\cdot\frac{b}{d}=a^{\prime}\cdot b^{\prime} \) ולכן קיים ייצוג חיובי \( n^{\prime}=a^{\prime}x+b^{\prime}y \). נכפול את שני האגפים ב-\( d \) ונקבל \( n=ax+by \) כפי שרצינו, מה שמסיים את ההוכחה גם במקרה זה.

לסיכום, אני שמח על כך שממשלת ישראל לומדת לאט לאט להתבסס על מספרים, ומקווה שכדי שיהיו פוסטים מעניינים בעתיד, הם יבססו את החוק הבא שלהם על עקומים אליפטיים.