חידת אוילר - הפתרון

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

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

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

1. אם \( a,b \) זרים, אז \( \varphi(ab)=\varphi(a)\cdot\varphi(b) \). כלומר, פונקצית אוילר של מכפלת שני מספרים זרים, שווה למכפלות פונקצית אוילר שלהם.
2. אם \( p \) הוא ראשוני, אז \( \varphi(p^k)=p^k-p^{k-1} \)

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

כלומר, אם \( n=p_1^{k_1}\cdots p_t^{k_t} \) אז

\( \varphi\left(n\right)=\varphi\left(p_{1}^{k_{1}}\cdots p_{t}^{k_{t}}\right)=\varphi\left(p_{1}^{k_{1}}\right)\cdots\varphi\left(p_{t}^{k_{t}}\right)=\left(p_{1}^{k_{1}}-p_{1}^{k_{1}-1}\right)\cdots\left(p_{t}^{k_{t}}-p_{t}^{k_{t}-1}\right) \)

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

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

\( \varphi\left(n\right)=\left(p_{1}^{k_{1}}-p_{1}^{k_{1}-1}\right)\cdots\left(p_{t}^{k_{t}}-p_{t}^{k_{t}-1}\right)=p_{1}^{k_{1}}\cdots p_{t}^{k_{t}}\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{t}}\right)=n\cdot\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{t}}\right) \)

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

\( \varphi\left(n\right)=n\cdot\prod_{p|n}\left(1-\frac{1}{p}\right) \)

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

כדאי לשים לב שה”תיקון” תמיד יהיה מספר רציונלי קטן מ-1, שכן הוא מכפלה של איברים מהצורה “אחד פחות משהו”, כשהמשהו הוא קטן יותר ככל שהראשוני שיוצר את האיבר גדול יותר. מכאן גם מגיעים בזריזות לפתרון החידה מהפוסט הקודם. מהו היחס \( \frac{n}{\varphi(n)} \)? אם משתמשים בנוסחה, רואים שהוא \( \frac{1}{\prod_{p|n}\left(1-\frac{1}{p}\right)} \). אנחנו רוצים לדעת מתי הערך הזה הוא מקסימלי, כלומר מתי \( \prod_{p|n}\left(1-\frac{1}{p}\right) \) הוא מינימלי.

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

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

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

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

נותר לי רק להסביר איך מוכיחים את שתי התכונות של פונקצית אוילר שעליהן התבססתי בבניית הנוסחה. נתחיל דווקא מהשנייה:  \( \varphi(p^k)=p^k-p^{k-1} \). הוכחת הנוסחה הזו מתבססת על קומבינטוריקה פשוטה. אנו רוצים לדעת כמה מספרים זרים ל-\( p^k \) יש בתחום \( 1,\dots\,p^k \). התחום כולו מכיל \( p^k \) מספרים, ולכן טכניקת ספירה הגיונית היא לספור כמה מספרים בתחום דווקא לא זרים ל-\( p^k \) ולחסר מסך כל המספרים שבתחום. אם כן, כל מה שנשאר לנו להראות הוא שיש בתחום הזה \( p^{k-1} \) מספרים שאינם זרים ל-\( p^k \).

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

גם את הספירה הזו קל לבצע עם התאמה חח”ע ועל - במקרה הזה, בין התחום \( 1,\dots,p^{k-1} \) כולו ובין המספרים שמתחלקים ב-\( p \) בתחום הגדול. ההתאמה פשוטה: בהינתן איבר מתוך \( 1,\dots,p^{k-1} \) נכפול אותו ב-\( p \), ונקבל איבר ששייך לתחום הגדול ומתחלק ב-\( p \). קל להראות שההתאמה היא חד חד ערכית - אם כפלנו שני מספרים ב-\( p \) והגענו לאותה תוצאה, אלו היו אותם מספרים; זה צמצום פשוט. קל גם להראות שההתאמה היא על, שכן אם יש לנו מספר בתחום הגדול שמתחלק ב-\( p \), פשוט נחלק אותו ב-\( p \) ובהכרח נקבל איבר בתחום הקטן - כלומר מקור של האיבר בתחום הגדול.

אם כן, גודל התחום \( 1,\dots,p^{k-1} \) הוא כגודל קבוצת המספרים בתחום הגדול שמתחלקים ב-\( p \), ולכן יש בדיוק \( p^{k-1} \) מספרים כאלו וגמרנו.

טענת הכפליות היא מורכבת קצת יותר. בהינתן \( n,m \) זרים, אנחנו רוצים להראות שלכל זוג מספרים \( a,b \) כך ש-\( a \) זר ל-\( n \) וקטן ממנו, ו-\( b \) זר ל-\( m \) וקטן ממנו, ניתן להתאים בצורה חד חד ערכית ועל מספר שזר למכפלה \( nm \) וקטן ממנה. טבעי לחשוב שהמספר הזה יהיה \( ab \); אלא שהעתקה כזו אינה חד חד ערכית. למשל, אם \( n=5 \) ואילו \( m=7 \), אז נקבל את המספר 2 גם עבור \( a=2,b=1 \) וגם עבור \( a=1,b=2 \). יש מספרים אחרים שזרים למכפלה 35, כמו למשל 31, שאין סיכוי לקבל כמכפלה (הרי 31 הוא ראשוני). צריך אם כן התחכמות נוספת כאן. ההתחכמות מתבססת על משפט חשוב בתורת המספרים האלמנטרית - “משפט השאריות הסיני”. אציג כאן גרסה פשוטה מאוד של המשפט, שהיא כל מה שצריך; אולי בהמשך אתאר את הגרסאות הכלליות יותר.

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

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

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