לא מדויק

נפש תועה הגיעה לאתר בחיפוש אחר הוכחה ש”שורש 6 אינו רציונלי”. הוא אמנם הגיע, ככל הנראה, אל ההוכחה שהצגתי לכך ששורש 2 אינו רציונלי, כלומר אינו ניתן להצגה כמנה של שני מספרים שלמים. אפשר היה להשאיר את הרחבת ההוכחה עבור 6 כתרגיל, אך נראה לי שכדאי להקדיש להרחבה הזו פוסט בפני עצמו ולא להשאיר אותה לקורא הטרוד. בכך אפשר גם לענות על שאלה שאולי צצה למי שקורא את ההוכחה לאי הרציונליות של שורש 2 - למה אי אפשר להשתמש בהוכחה גם כדי להוכיח ש-4, למשל, אינו רציונלי? איך ההוכחה “מזהה” את הריבועיות של המספרים שעליהם היא נכשלת?

אני מזהיר מראש שהפוסט הזה טיפה טכני, ומצד שני גם קצת מחפף, כך שאני יוצא קרח מכאן ומכאן. אם משהו לא ברור, או ברור מדי, אפשר להעיר על כך בתגובות.
אם כן, הבה ננסה להכליל את ההוכחה באופן הישיר ביותר שרק אפשר. נתון מספר שאנו רוצים להוכיח שהשורש שלו איננו רציונלי. נניח בשלילה שהוא כן רציונלי, אז אפשר לכתוב את השורש בתור עבור טבעיים זרים זה לזה, כלומר שאין מספר גדול מ-1 שמחלק את שניהם בו זמנית. מכאן שמתקיים , כלומר . עד כאן - שום דבר חדש. כעת ההוכחה עבור שורש 2 מתחילה לדבר על הזוגיות של ; היא אומרת “מכך ש- נובע ש- זוגי, ולכן גם זוגי”.

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

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

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

אם כן, נצמצם את עצמנו ל--ים פשוטים יחסית - מכפלות של ראשוניים כך שכל ראשוני מופיע בדיוק פעם אחת (כלומר, אף ראשוני לא מופיע בפירוק לגורמים עם חזקה גבוהה מ-1). למשל, 6 הוא כזה אך 12 לא. במילים אחרות, מספרים שאף ריבוע לא מחלק אותם. מספרים כאלו מכונים “חופשיים מריבועים” (Square-free). לא קשה להוכיח פורמלית, בהתבסס על מה שאמרנו כבר, שאם שהוא חופשי מריבועים מחלק את   אז הוא בהכרח מחלק גם את (כי כל גורם של מחלק את , כלומר מופיע בפירוק שלו לגורמים; והפירוק הזה מכיל רק גורמים שנמצאים גם ב-).

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

היוצאים מן הכלל היחידים בהוכחה שלנו הם הריבועים, שכן אותם לא ניתן להציג בתור מכפלה של ריבוע ושל מספר חופשי מריבועים - ההצגה שלהם היא “ריבוע כפול 1″ (אנחנו לא מחשיבים כאן את 1 כחופשי מריבועים כדי שזה יתאים לנו להגדרה המקורית של מכפלת ראשוניים).

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

1) “למה הבבלים לא השתמשו בשיטה העשרונית”. שאלה קשה, בערך כמו “למה אנחנו לא משתמשים בשיטה על בסיס 12″ (יש כאלו שטוענים שלבסיס 12 יתרונות על בסיס 10 ואולי הצדק עמם, מתמטית). המספר 60 הוא לא כל כך מקרי - הוא מתחלק ב-2, ב-3, ב-4, ב-5 וב-6 (ולכן גם ב-30, ב-20, ב-15, ב-12 וב-10), כך שביצוע פעולות חשבוניות וזיהוי התחלקויות הוא יחסית פשוט. הבעיה בבסיס היא שצריך לייצג את כל המספרים מ-1 עד 59 עם סימון שונה, ולכן הבבלים השתמשו בשיטת ספירה משנית - היה להם סימן אחד לאחדות, וסימן אחד לעשרות, והמספר 32, למשל, נכתב בתור 3 מופעים של סימן העשרות ו-2 מופעים של סימן האחדות. זה אמנם מסורבל יחסית אבל כשמתרגלים זה כנראה ממש לא נורא - ובבסיסי ספירה, התרגלות זה לב העניין.

2) “מה היה קורה אם אוילר לא היה קיים” - שאלה נפלאה, בעיקר כשמדובר במתמטיקאי סופר-פורה כמו אוילר. הניחוש שלי - המתמטיקה אמנם הייתה מגיעה לרמתה הנוכחית, אבל באיחור של כמה שנים טובות (אין לי מושג כמה), ובוודאי שהסימונים שבהם אנחנו משתמשים (שאוילר המציא חלק מהם) היו שונים.

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

4) “אין סוף x^2+y^2=z^2″ - אני מניח שהכוונה לאינסוף פתרונות של המשוואה המדוברת, שמגדירה שלשה פיתגורית (צלעות בגודל שלם של משולש ישר זווית). זה שיש אינסוף פתרונות הוא טריוויאלי בהינתן פתרון אחד שכבר ידוע, למשל 3,4,5: פשוט מכפילים את כל אברי הפתרון באותו מספר. לכן מה שמעניין הוא לחפש פתרונות רבים ושונים שלא יכולים להתקבל האחד מהשני באמצעות התעלול הזה - יצורים שכאלה מכונים “שלשות פיתגוריות פרימיטיביות” (וכל אחד מהם מגדיר משולש ישר זווית ש”נראה שונה”, בעוד שהתעלול שהצגתי נותן משולש שהוא יותר גדול אבל נראה זהה - בלשון מתמטית פורמלית, הוא דומה למשולש המקורי). מסתבר שגם מהם יש אינסוף, ויתר על כן - יש נוסחה פשוטה יחסית שיוצרת את כולם; קחו שזרים זה לזה (לא מתחלקים בו זמנית באף מספר ששונה מ-1), ושלפחות אחד מהם זוגי, ותגדירו . בצורה הזו תקבלו את כל השלשות הפיתגוריות הפרימיטיביות. אני מקווה להרחיב על השאלה למה זה עובד ואיך מגיעים לזה בפוסט נפרד.

5) “כפל חילוק חיסור חיבור לפי איזה סדר זה עובד” - קודם כפל וחילוק, אחר כך חיבור וחיסור. אם יש סוגריים, תמיד עושים קודם את מה שבתוך הסוגריים. בין כל שתי פעולות “שוות בכוחן” צריך לבצע את הפעולות משמאל לימין. הדוגמה הקלאסית היא ; אם קודם מחלקים ואז כופלים מקבלים 12, אבל אם קודם כופלים, ולכן מחלקים 8 ב-6, מקבלים איכסה פיכסה לא שלם (1 ושליש).

6) “למה במעגל יש 360 מעלות” - התשובה היא שאין סיבה; זה מספר שרירותי לגמרי, ואפשר היה לבחור כל מספר אחר במקומו. הסיבה ה”היסטורית” היא שהמספר הזה נבחר בידי הבבלים, שהשתמשו בבסיס 60 ואהבו כפולות שלו; וייתכן מאוד שגם לעובדה שיש בשנה כמעט 360 יום יד בעניין. אם חושבים על כך, 360 הוא מספר די טוב למעגל, כי אז הרבה מאוד זווית שמגדירות חלק ממעגל יוצאות שלמות. למשל, רבע מעגל הוא 90 מעלות - שלם. שמינית היא 45 מעלות - עדיין שלם. חמישית מעגל (מספר חשוב למדי, כי הוא מופיע בצורה “טבעית” פה ושם) הוא 72 - גם שלם. בקיצור, אפילו שאפשר לבחור כל מספר שרוצים, 360 הוא בחירה די טובה. כמובן שיש שיטת מדידה יותר “טבעית” ובעלת סיבות טובות מאוד לקיומה - שיטת הרדיאנים.

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

8) “להראות שכל מספר מורכב מסכום שני מספרים ראשוניים” - הויסה, עדיין לא ברור אפילו אם כל מספר זוגי מורכב מסכום שני מספרים ראשוניים.

9) “חומר קל להבנה בתורת המספרים” - שאלה קשה יחסית, שכן תורת המספרים היא דווקא אחד מתחומי המתמטיקה שאליו “מתנקזים” רוב התחומים המתמטיים הבסיסיים, החל באלגברה מופשטת קלה יחסית וכלה באנליזה מסובכת של פונקציות מרוכבות. הספר שממנו למדתי את הבסיס הוא A Classical Intoduction to Modern Number Theory של Ireland ו-Rosen שמתחיל מדברים פשוטים יחסית ומגיע לטעימה קלה שבקלות מהנושאים המורכבים; הוא דורש ידע מוקדם במתמטיקה ברמה של סמסטר ראשון או שני לערך (תלוי מה לומדים). איני מכיר (והאמת, אשמח להכיר) טקסטים מתמטיים (לא מדע-פופולריים) פשוטים יותר שעוסקים בנושא.

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

בפוסט הקודם דיברתי קצת על למה לא נהוג במתמטיקה להגדיר חלוקה באפס, מתי כן מגדירים חלוקה באפס (למשל, מתי נוח לנו לסמן את החלוקה של אחד באפס כ”אינסוף” ומה המשמעות של זה) ולמה 0/0 היה ונותר ביטוי חסר טעם להגדרה ולכן בתוכנות מחשב מתמטיות דוגמת Matlab נהוג שתוצאת הפעולה 0/0 היא קבוע בשם NaN, שמשמעותו “לא מספר” (Not a Number). קבוע בעל התכונה הסבירה שכל פעולה מתמטית שנעשה עליו לא תשנה אותו (1 ועוד “לא מספר” יהיה “לא מספר”, למשל). המוטיבציה לדיון הזה הייתה הסיפור (שכעת הוא כמעט בן שנתיים) על מורה למתמטיקה שלימד את תלמידיו תורה מתמטית חדשה שבה חלוקה באפס היא “אפשרית” ובכך פתר “בעיה בת 1,200 שנים”.

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

ראשית, הבעיה שיש לתקן. יהודה בלו אמר על בעיית השורש “מסיבה לא ברורה, לא מחפשים המתמטיקאים שיטה למצוא שורש ריבועי או שורש כלשהו. האם יש בידם הוכחה מתמטית שלא מתאפשרת שיטה שכזו? עדיין לא.” ומה ג’יימס אנדרסון אומר? ה-BBC מביאים את הציטוט הבא:

“Imagine you’re landing on an aeroplane and the automatic pilot’s working,” he suggests. “If it divides by zero and the computer stops working - you’re in big trouble. If your heart pacemaker divides by zero, you’re dead.”

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

“This presentation is dedicated to the USS Yorktown which was stranded for 2 hours 40 minutes when a division-by-zero error crashed its entire network of computers, causing its engines to stop.”

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

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

לאנדרסון הדוגמאות הללו לא מספיקות. הוא חייב לתקוף באופן ישיר את כל המתמטיקה שהייתה לפניו כדי להסביר מה הוא תורם, בעצם. לכן הוא כותב שקף בעל הכותרת המפוצצת “מה הבעיה עם האריתמטיקה?” ומפרט את הבעיות, עם עוד הערה בסוגריים לכל אחת מהן: אי אפשר למצוא את הטנגנס של זווית ישרה (אינסוף), את הלוגריתם של 0 (מינוס אינסוף), אי אפשר למצוא את אפס בחזקת אפס (האות היוונית ), ואי אפשר להסביר “איך מחשבים עובדים” (NaN). יותר חמור - האריתמטיקה המתמטית לא מתארת את האריתמטיקה שבה אנשים משתמשים בחיי היום יום שלהם בתור מתכנתים או משתמשים במחשבים, והיא “Sociologically invalid” (הצבע האדום במקור).

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

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

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

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

התוכן האמיתי מגיע בשקף הבא, שכותרתו היא “מה הבעיה עם מחשבים?” ובו הוא מציג שתי נקודות מהותיות: ראשית, NaN ו-Inf ומינוס Inf, החבר’ה שמייצגים את “בלתי מוגדר” ואת אינסוף ומינוס אינסוף בתוכנות המתמטיקה הסטנדרטיות, הם “לא מספרים” כהגדרתו של אנדרסון. שנית (וזו, לדעתי, הנקודה היחידה שבאמת שווה התייחסות בכל דבריו של אנדרסון), NaN מקיים את התכונה שאינו שווה לעצמו. כלומר, אם תבצעו שני חישובים, אפילו זהים, ותכניסו את התוצאה לתוך משתנים שונים, ושני החישובים יחזירו NaN, ותבצעו השוואה בין המשתנים - תקבלו תשובה שלילית. אנדרסון טוען ש”שוויון פירושו ש-x שווה ל-x לכל x, ולכן אריתמטיקה ממוחשבת היא invalid” (שוב, האדום המביך במקור).

לנקודת “הם לא מספרים” שהעלה אנדרסון אתייחס בקרוב. בינתיים אתייחס לנקודה המהותית - למה NaN לא זהה אפילו לעצמו? לכאורה זה באמת נראה מטופש. אלא שצריך לזכור את המוטביציה לקיום NaN - הוא בא למדל ביטויים כמו 0/0, שהם חסרי משמעות באופן טוטאלי, אפילו בגישת החשבון האינפיניטסימלי, זו שאומרת ש-1/0 ו-2/0 הם זהים במובן מסויים מאוד - הגבול של שתי הפונקציות הוא זהה כאשר איקס שואף לאפס מימין. כפי שאמרתי בפוסט הקודם, לגבול של שבר שבו גם המונה וגם המכנה שואפים לאפס (או לגבול של מכפלה שבה אחד האיברים שואף לאפס והשני לאינסוף, וכו’) יכולים להיות ערכים שונים לגמרי. לכן מבחינה רעיונית זה שגוי להגדיר את NaN כשווה לעצמו, ובכך ליצור זהות כלשהי בין שתי הסיטואציות הללו. מבחינה מעשית זה אולי מעט מסורבל, כי כדי לבדוק האם משתנה מכיל את NaN לא ניתן להשוות אותו ל-NaN; לכן לרוב מוגדרת גם פונקציה בשם isNaN שמבצעת את הבדיקה בשביל המשתמש - ואם אין כזו, הבדיקה x==x (”האם איקס שווה לאיקס?”) מאפשרת מייד לזהות האם x הוא NaN או לא - התשובה לה תהיה שלילית אם ורק אם x הוא NaN.

אם כן, מה אנדרסון מציע כדי לפתור את הבעיות הקשות (והלא קיימות) הללו? הוא מרחיב את מערכת המספרים הממשיים למערכת שהוא קורא לה “Transreal” (המצאת שמות מפוצצים לדברים קיימים זו תכונה מאפיינת סטנדרטית של טרחנים כפייתיים - עיינו ב”המספרים הדו חזקתיים” של יהודה בלו). היא מתקבלת מהממשיים על ידי הוספת אינסוף ומינוס אינסוף (עד כאן, הכל בסדר - זה גם מה שיש ב-Matlab וגם בספרי לימוד רבים שעבורם ההרחבה הזו “משתלמת”), ועוד מספר אחד חדש, שמסומן כ- ונקרא “Nullity”, ובתרגום חופשי לעברית שלי: “כלומיתי”. אני קצת מרושע, כי Nullity היא מילה קיימת במתטיקה ובעלת משמעות שונה, ובמשמעות השונה הזו לא היה עולה על דעתי לתרגם אותה כ”כלומיתי”, אבל נו טוב. גם לי מותר ליהנות.

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

1. אנדרסון מגדיר את כלומיתי להיות שווה לכלומיתי, להבדיל מ-NaN שמוגדר לא להיות שווה לעצמו (כפי שהזכרתי לעיל).
2. אנדרסון קורא לכלומיתי “מספר”, בעוד ש-NaN, במוצהר (אפילו בשמו!) איננו מספר.

לנקודה מס’ 1 התייחסתי כבר וניסיתי להסביר מדוע זה ש-NaN אינו שווה ל-NaN הוא יתרון, לא חיסרון. הגישה הטבעית והנאיבית יותר היא כן להגדיר אותו כשווה לעצמו; האנשים הטובים ב-IEEE שטרחו ועמלו על הסטנדרט של NaN לא סתם בחרו להגדיר אותו כשונה מעצמו. אנדרסון אם כן בא לתקן את מה שאינו מקולקל בכלל, והתיקון שלו הוא מה שמקלקל; אבל “מקלקל” זו הגזמה. אין בעיה מהותית לעבוד עם כלומיתי ששווה לעצמו, כשם שאין בעיה מהותית לעבוד עם NaN שלא שווה לעצמו - המתכנת פשוט צריך להיות מודע לכך שהשוויון יעבוד/לא יעבוד, ולכתוב את הקוד שלו בהתאם.

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

לקראת סוף המצגת שלו אנדרסון מגיע לרמה חדשה של עליבות: הוא אומר ש”ב-1,200 השנים האחרונות אף אחד לא הצליח לחשב את אפס בחזקת אפס בצורה אריתמטית. עד כמה זה קשה?” ואז מציג “חישוב” של אפס בחזקת אפס. רובו הוא סטנדרטי לגמרי: - זה דבר שברור לכל סטודנט למתמטיקה (וגם לתלמידי תיכון שחושבים על החומר, למען האמת), והבעיה היחידה היא שהביטויים בו אינם מוגדרים היטב - אלא שלאנדרסון יש שם אחר לביטוי הימני של אפס חלקי אפס - ניחשתם נכון, כלומיתי. הפלא ופלא! נפתרה בעיה בת 1,200 שנים! גילינו שאפס בחזקת אפס, שעד כה היה לא מוגדר, הוא… לא מוגדר!
בשלב הבא במצגת שלו אנדרסון כבר גולש למחוזות שגעון הגדלות. הוא מתיימר להיות מסוגל לבנות סופר-מחשבים בעזרת כלומיתי. לא רואים זאת במצגת, אבל במאמרים שלו הוא מציג את הרעיון יותר לעומק - מחשב שיכיל רק פקודה אחת, מסובכת משהו, של חישוב דמוי מכפלה סקלרית. אין ממש טעם להיכנס לשאלה האם היצור הזה הוא מה שנקרא Turing Complete, כלומר חזק כמו המודל המתמטי הסטנדרטי של מחשב - אני מוכן להניח שכן. מה שברור הוא שמבחינה תיאורטית הוא לא חזק יותר כל עוד מידע מיוצג בו בצורה דיגיטלית (כלומר, כל מספר בו מיוצג כרצף סופי של אפסים ואחדים או משהו דומה, כי לא ניתן לייצג כך את כל המספרים הממשיים) - הרי ניתן לסמלץ את כלומיתי בכל שפת תכנות בסיסית (תרגיל למתכנתים - אל תטרחו, יש דברים יותר מגניבים לעשות, כמו פרוייקט אוילר). כמובן שאם המחשב שלו עובד עם כל המספרים הממשיים, זה עשוי לתת לו כוח רב יותר; אבל גם מודלים שכאלו הם לא דבר חדש, ותוספת הכלומיתי, שהיא התרומה היחידה של אנדרסון, לא מוסיפה כלום.

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

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

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

אני עוקב פה ושם אחרי המטורפים שאיתם נאלץ מרק, הכותב המסכן של Good math, bad math להתמודד. הפעם הוא נאבק בברנש שעוסק בחלוקה באפס - “First off, 1/0 is infinity”. כפי שמרק אומר בבלוג, כבר כאן צריך לקטוע את הברנש עם “בזזזט. שגוי”, כי אחד חלקי אפס כלל איננו מספר; המשמעות של “אחד חלקי איקס” היא מספר שכאשר הוא מוכפל באיקס, מקבלים אחד; אבל מכיוון שכל דבר כפול אפס נותן אפס, בוודאי שלא קיים מספר שכזה. דא עקא, ההסבר הזה מותיר פתח לשאלה “אוקיי, אז מה עם 0/0?” והברנש הזכיר לי בפתיחת המכתב שלו (”I was searching the internet for stuff on Nullity, this new number that I noticed you think is crank.”) את אחת הפרשיות התמוהות ביותר מהעת האחרונה (כבר מ-2006, אמנם) שעוסקת בביטוי הלא מוגדר האומלל הזה - פרשיית “Nullity” (שאתרגם בצורה חופשית ביותר כ”כלומיתי”). זוהי פרשיית טרחן כפייתי “מודרנית” קלאסית - הטרחן הוא ללא ספק טרחן, אבל הוא היה נותר בגדר טמבל לא מזיק (הרעיונות שלו, שאציג בהמשך, אינם מופרכים או שגויים מהותית; הטרחנות שלו מתבטאת בחשיבה השגויה שהוא גילה את אמריקה) אלמלא היה זוכה לכיסוי תקשורתי מיותר, הפעם של ה-BBC.

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

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

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

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

ישתמרו גם כשמציבים בתור a,b,c מספרים “הופכיים” שכאלה. תכף ומייד מתברר לנו שאם יש לאפס הופכי ואנו רוצים שהכללים הללו ימשיכו להתקיים, צפוי לנו אסון נורא:

ומכאן נובע באמצעות העברת אגפים:

לכל a שרק תרצו. בפרט עבור . אבל הרי על פי הגדרתו, , ולכן קיבלנו את המשוואה החביבה 0=1, שבצעד אחד נוסף מוכיחה לנו שכל מספר שווה לאפס (איך?)

אאוץ’. הלכה מערכת המספרים. מסקנה: אם מוסיפים הופכי לאפס, חלק מכללי החיבור והכפל כבר לא יחולו עליו (לעומת זאת, ניתן להוכיח שעבור כל שאר ההופכיים לא יווצרו בעיות שכאלו).

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

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

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

חייבים לשים לב לכך שה”אינסוף” הזה שהצענו איננו ההופכי של 0; אחרת, למשל, אפשר לקבל ש-1=2, כי ועכשיו כפלו באפס את כל האגפים. מכאן שצריך להיות מאוד זהירים בכל הנוגע למה שקורה עם האינסוף - לרוב גם תוכנות מתמטיקה (דוגמת Matlab) שטורחות להגדיר את אחד חלקי אפס בתור “Inf” (קיצור של Infinity) משאירות את Inf כפול אפס בתור “NaN” (קיצור של Not a number). ה-NaN הזה הוא הסימול שנקבע בסטנדרט לייצוג במחשב של מספרים לא שלמים. עוד דרכים שבהן NaN עשוי להתקבל הן כתוצאה מכל מני פעולות אחרות על Inf - למשל, לחבר אותו עם מינוס עצמו, לחלק אותו בעצמו, וכדומה. ועוד חלוקה אחת שמובילה אוטומטית ל-NaN היא 0/0, חלוקה של אפס בעצמו. מה שמחזיר אותנו שוב לשאלה “למה לא להגדיר את זה כאפס וזהו?”. התשובה הקצרה היא שמנקודת מבטו של החשבון האינפיניטסימלי (שנתן לנו את המוטיבציה הראשונית להכניס את האינסוף למשחק בכלל) פונקציות שכאשר איקס שואף לאפס הן שואפות לביטוי בצורה אפס חלקי אפס יכולות לשאוף לכל מספר אפשרי. הדוגמה הפשוטה ביותר היא כאשר a הוא מספר כלשהו. כאשר איקס שואף לאפס הפונקציה תשאף ל-, ועם זאת היא שואפת לביטוי .

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

אם כן, תשאלו, מה הטעם בלתת ל-0/0 שם מפוצץ כמו “NaN”? הסיבה הפשוטה היא ש-NaN הוא סמל שהמחשב יודע לזהות ולעבוד איתו, ובפרט אפשר גם לבדוק בכל שלב אם תוצאת החישוב שלנו היא NaN או לא - ואם היא כן, להבין שמשהו השתבש ולנסות לתקן. הגיוני לצפות שבשלב שבו בוצע חישוב שתוצאתו הייתה NaN התוכנה גם תשלח אזהרה כללית, באמצעות מנגנון החריגות (Exceptions) שכל שפת תכנות מודרנית תומכת בו; אבל לא תמיד זה נוח (נניח, אם אתם מפעילים פונקציה על אלפי איברים ברצף ועבור חלק קטן מהם היא תיכשל, לא תרצו שבכל פעם שיש בעיה תצטרכו לקטוע את רצף החישוב ולטפל בחריגה - כבר יותר נוח לתת למחשב לשים את הערך NaN בתור התוצאה במקרים הללו, ואחר כך לסנן את הערכים הללו).

וכעת ניתן לחזור לטרחן הכפייתי שלנו, אחרי שהצלחתי (אני מקווה) לשכנע אתכם שבימינו אף אחד כבר לא מתרגש מחלוקה באפס, ויש הגדרות סטנדרטיות ומקובלות לתוצאה של חלוקה כזו, גם מנקודת מבט תכנותית. מה שעולל הטרחן שלנו הוא להתעלם מכל זה, להמציא מחדש את גלגל ה-NaN בלבוש פומפוזי יותר, ולטעון שבכך הוא “פתר בעייה בת 1,200 שנים”. לברנש קוראים ד”ר ג’יימס אנדרסון, ועל התגלית שלו אפשר לקרוא כאן. עם זאת, בדרך כלל המקום הטוב ביותר לקרוא על טרחנים הוא מפיהם עצמם - הנה מצגת שהוא עומד מאחוריה, ככל הנראה, והנה מאמר שמפרט קצת יותר את מה שהוא עשה. כדי להפריד בין המתמטיקה האמיתית (שאותה הצגתי, אם כי בצורה חלקית, בפוסט הזה) ובין השטויות, אדחה את העיסוק בתיאוריה שלו לפוסט הבא. לעת עתה, “טיזר” - כל מה שהגאון עושה הוא לתת ל-NaN שם אחר ולטעון שכעת זה “מספר”.

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

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

באופן דומה אפשר להסיק את הטענות המקבילות במקרים האחרים - הסתברות של 2/3 לשליפת כדור לבן מתקיימת אם ורק אם יש בדיוק שני כדורים לבנים בכד; והסתברות של 1/3 - אם ורק אם יש בדיוק כדור לבן אחד בכד. עד כאן הכל טוב ויפה, ואני מבטיח שעדיין לא רימיתי. הרעיון של שימוש במשהו הסתברותי כדי ללמוד מידע “ודאי” על העולם (במקרה הזה אנחנו לומדים מההסתברות לשליפת כדור לבן על המספר האמיתי של הכדורים הלבנים) הוא בסיסי וחשוב במתמטיקה; בפרט, כל השיטה ההסתברותית בקומבינטוריקה מבוססת עליו.

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

1. שלושה כדורים לבנים, בהסתברות 1/4 (רק אם שני הכדורים שהוגרלו היו לבנים).
2. שני כדורים לבנים ואחד שחור, בהסתברות 1/2 (אם אחד משני הכדורים שהוגרלו היה לבן והשני שחור; יש שתי אפשרויות כאן - או שהגרלנו את השחור מהכד הימני, או שהגרלנו אותו דווקא מהכד השמאלי)
3. כדור לבן אחד ושני שחורים, בהסתברות 1/4 (בדומה למקרה 1).

אחלה. כעת, מה ההסתברות שנשלוף מהכד הזה כדור לבן? זה תרגיל פשוט בהסתברות מותנה: אם אנחנו במקרה 1, אז בהסתברות 1 נשלוף לבן, ולכן ההסתברות של “אנחנו במקרה 1 וגם שלפנו לבן” היא 1/4. בדומה, ההסתברות של “אנחנו במקרה 2 וגם שלפנו לבן” היא חצי כפול שני שליש (שני שליש היא ההסתברות שנשלוף לבן בהינתן שיש שני לבנים ושחור אחד), כלומר שליש. ההסתברות של “אנחנו במקרה 3 וגם שלפנו לבן” היא 1/12, מאותם שיקולים שכבר ראינו. סכום כל ההסתברויות הללו הוא בדיוק ההסתברות של “שלפנו לבן” - וחישוב קצר יראה שהסכום הזה הוא 2/3. כלומר, על פי האבחנה שראינו בהתחלה, נובע מכך שבכד שלנו יש בדיוק שני כדורים לבנים - אבל מי מבטיח את זה? הרי גם אפשרויות 1 ו-3 הן סבירות! מה הולך כאן?

זה השלב שבו כדאי לעצור ולחשוב, ואני מביא קומיקס של xkcd כאתנחתא.

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

1. נתונה תיבה שבה כדורים לבנים ושחורים, שלושה במספר בסה”כ. ידוע שאם שולפים כדור באקראי מהתיבה, ההסתברות לשלוף כדור לבן היא 2/3. נובע מכך שיש בתיבה בדיוק שני כדורים לבנים.
2. נתון תהליך אקראי שמייצר תיבה. זה שידוע שיש הסתברות של 2/3 לשלוף כדור לבן ממנה לא מבטיח כלום לגבי הרכב הכדורים שלה.

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

למי שטרם נחה דעתו מהסבר ה”תהליך”, עודד לבנה מביא דוגמה נוספת שמבהירה את העניין עוד יותר. נניח שבמקום תהליך יצירת הכד המורכב שהצגנו קודם, עושים משהו פשוט יותר: יש שני כדים מלאים כדורים לבנים, וכד אחד מלא כדורים שחורים. בוחרים אחד מהכדים באקראי. עכשיו שולפים כדור. מה ההסתברות שנשלוף כדור לבן? כמובן, היא 2/3; אבל ברור שהכד שיש לנו לעולם לא יהיה “שני כדורים לבנים וכדור שחור אחד” - ייתכן שכל הכדים מכילים מיליארד כדורים (בשניים מהם לבנים, ובאחד מהם שחורים).

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

מכיוון שהחידה שהצגתי בפוסט הקודם עוסקת בפונקצית אוילר, כדאי להבין את הפונקציה יותר טוב על מנת שניתן יהיה להבין את הפתרון. כפי שכתבתי שם, הפונקציה מחזירה לכל מספר טבעי את מספרם של המספרים הטבעיים הקטנים ממנו וזרים לו, כלומר שאין מספר גדול מ-1 שמחלק את שניהם גם יחד. למשל, עבור 8 הפונקציה תחזיר 4, בשל המספרים 1,3,5,7 (שימו לב - 6 אמנם אינו מחלק את 8 אך גם אינו זר לו, שכן 2 מחלק את שניהם). חישוב של הפונקציה על בסיס ההגדרה הזו בלבד יהיה לא יעיל במיוחד - לעבור על כל המספרים שקטנים מ-, לבדוק לכל אחד אם הוא זר ל- (בעזרת האלגוריתם האוקלידי למציאת המחלק המשותף המקסימלי - אלגוריתם שבפני עצמו הוא יעיל למדי), ואם כן - להוסיף אותו לסכום. זה לא פתרון טוב במיוחד, כי זמן הריצה הוא פרופורציוני לגודל המספר, מה שנחשב איטי למדי (אלגוריתמים יעילים על מספרים הם כאלו שזמן הריצה שלהם הוא פולינום בלוגריתם של המספר, או בצורה פשוטה יותר - פולינומי במספר הספרות שלו).

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

את הנוסחה אפשר להסיק באמצעות שתי תכונות פשוטות של הפונקציה:

1. אם זרים, אז . כלומר, פונקצית אוילר של מכפלת שני מספרים זרים, שווה למכפלות פונקצית אוילר שלהם.
2. אם הוא ראשוני, אז

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

כלומר, אם אז

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

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

אם נשתמש בקיצור הסטנדרטי במתמטיקה לתיאור כפל בהרבה איברים, סימן גדול של האות פאי, אפשר לכתוב את כל העסק ככה:

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

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

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

ראשית, ברור שבפירוק לגורמים של המספר, כל ראשוני צריך להופיע פעם אחת (כלומר, המעריך שלו בחזקה יהיה 1; לכן מספר כמו 9 או 18 הוא פסול מראש כי 3 מופיע בפירוק שלו בחזקת 2). למה? כי זו חזקה “מבוזבזת”; היא לא מקטינה עוד יותר את המכפלה, כי הראשוני כבר מופיע בה; לכן, בהינתן מספר שעבורו היחס הוא כך וכך ויש לו ראשוני עם חזקה גבוהה מ-1 בפירוק לגורמים, אפשר להחליף אותו במספר אחר, שבו החזקה של אותו ראשוני היא 1, ונותן בדיוק את אותו היחס. נסו כמה דוגמאות - למשל, 18 חלקי פונקצית אוילר של 18 ייתן בדיוק אותה תוצאה כמו 6 חלקי פונקצית אוילר של 6: 3 בשני המקרים.

אם כן, המספר שלנו יהיה מכפלה של ראשוניים שונים זה מזה. אילו ראשוניים נבחר? הדעת נותנת שאת הקטנים ביותר שרק אפשר, שכן ככל שהראשוני גדול יותר, כך גדול יותר, ואנחנו רוצים שיהיה דווקא קטן. מכאן שהמספר שלנו הוא בהכרח המספר הגדול ביותר שקטן ממיליון ומהווה מכפלה של ראשוניים עוקבים, החל מ-2. לחשב את זה במספרים גבוהים זה כאב ראש, אבל במספרים נמוכים זה לא נורא. אפשר לגלות די בקלות, על ידי בדיקה ממצה אפילו, שהראשוניים הראשונים הם 2,3,5,7,11,13,17; חישוב קצר (לא כיפי בכלל, אבל ניתן לביצוע אפילו עם נייר ועיפרון) יראה כי מכפלתם היא 510,510; ואם נכפול את העסק הזה בראשוני הבא בתור, 19, נקבל מפלצת שעוברת את מיליון בקלות. לכן 510510 הוא המספר המבוקש - זהו פתרון החידה.

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

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

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

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

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

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

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

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

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

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

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

השאלה היא פשוטה: מבין כל המספרים מ-2 עד מיליון, מהו המספר שעבורו היחס הוא הגדול ביותר?