השערת להמר

חרגול עומד על שעון בשעה \({12}\), ומתחיל לקפוץ, בדילוגים של מספרים שלמים. אם יקפוץ כל פעם שעה אחת, הוא יגיע כמובן לכל השעות השלמות. אם יקפוץ בדילוגים של \({2}\), הוא יגיע רק לשעות הזוגיות. שאלה: אילו דילוגים יבטיחו שיגיע לכל סימוני השעות השלמות?

ניקח לדוגמה דילוג של 5. עקבו ובדקו אם אני צודק: הוא יגיע על פי סדר לשעות \({5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7}\) ואז יחזור לשעה \({12}\) (שהיא בעצם \({0}\)). כלומר – בדילוגים של 5 אכן יעבור על פני כל השעות השלמות.

גם דילוגים של 7 טובים (זה בעצם לדלג 5, רק בכיוון ההפוך), וגם \({11}\) (שזה לדלג 1, נגד כיוון השעון). אלו המספרים היחידים – \({1, 5, 7, 11}\). מה משותף להם? אלה הם המספרים הקטנים מ-\({12}\) וזרים ל-\({12}\), שפירושו שאין להם ול-\({12}\) מחלק משותף גדול מ-\({1}\). מתברר שלמספרים הקטנים ממספר נתון וזרים לו יש תפקיד מיוחד. הם מעניינים. כדי לדבר עליהם, נצטרך כמה הגדרות.

הגדרה. נאמר שמספר טבעי (כלומר מספר שלם לא שלילי) \({d}\) מחלק את המספר הטבעי \({n}\) אם קיים מספר \({m}\) כך ש-\({n=md}\). אם \({d}\) מחלק את \({n}\) נרשום \({d|n}\). אם לא, נסמן \({d\not | \ n}\).

למשל, \({5|15}\) אבל \({5\not | \ 13}\) . נזכיר שמספר ראשוני הוא מספר טבעי הגדול מ-\({1}\) שמחלקיו היחידים הם \({1}\) והוא עצמו. שישה המספרים הראשוניים הראשונים הם \({2, 3, 5, 7, 11, 13}\). מספר שאיננו ראשוני נקרא פריק.

הגדרה. נאמר כי לשני מספרים טבעיים \({m}\) ו- \({n}\) יש מחלק משותף גדול מ-\({1}\) אם קיים \({d\neq1}\) כך ש-\({d|n}\) ו-\({d|m}\) . אם אין \({d}\) כזה אומרים ש-\({m}\) ו-\({n}\) זרים.

המתמטיקאי הגדול של המאה ה-\({18}\), לאונרד אוילר \({(1707 – 1783)}\) גילה שיש משמעות מיוחדת למספר המספרים הטבעיים הזרים ל-\({n}\) וקטנים ממנו. הוא סימן את המספר הזה ב-\({\varphi(n)}\). כיום קוראים למספר הזה “פונקציית אוילר”, למשל, ראינו ש-\({\varphi(12)=4}\) , משום שהמספרים הקטנים מ-\({12}\) וזרים לו הם \({1, 5, 7}\) ו-\({11}\). הנה כמה ערכים נוספים: \({\varphi(2)=1}\), \({\varphi(3)=2}\), \({\varphi(4)=2}\) (כי המספרים הקטנים מ-4 וזרים לו הם 1 ו-3) \({\varphi(5)=4}\) , \({\varphi(6)=2}\), \({\varphi(7)=6}\). (שימו לב כי \({\varphi(5)=\varphi(12)=4}\) האם יש לכם עוד דוגמאות כאלה?)

עובדה פשוטה אם \({p}\) הוא מספר ראשוני, אז כל המספרים הקטנים ממנו זרים לו, ולכן \({\varphi(p)=p-1}\) . ומה בדבר פונקציית אוילר של מכפלת שני ראשוניים? נסו דוגמאות והיווכחו: לכל שני מספרים ראשוניים \({p}\) ו – \({q}\) מתקיים \({\varphi(pq)=(p-1)(q-1)}\) (האם תוכלו למצוא את \({\varphi(33)}\)? \({\varphi(35)}\)?) האם תוכלו למצוא שני מספרים \({m}\) ו-\({n}\) שעבורם \({\varphi(mn)\neq \varphi(m)\varphi(n)}\) האם תוכלו לנחש לאילו מספרים \({m}\) ו-\({n}\) כן מתקיים שוויון?

קל לראות שאם \({n}\) איננו מספר שאיננו ראשוני אז \({\varphi(n)\neq n-1}\). המתמטיקאי האמריקני דיק להמר (\({1905 – 1991}\) – להמר היה גם מחלוצי מדעי המחשב) שיער משהו חזק יותר.

השערת להמר \({(1932)}\) אם \({n}\) אינו ראשוני אז \({\varphi(n) \not | \   n-1}\).

שמונים שנים עברו מאז פרסם להמר את השערתו, וההתקדמות בהשערה מעטה. במאמר שבו הציג להמר את השערתו הוא ציין גם שקיימים שמונה מספרים טבעיים פריקים \({n}\) כך ש- \({\varphi(n)| n+1}\) .(האם תוכלו למצוא כמה כאלה? שימו לב למשל ש-\({15}\) הוא כזה). ההשערה כיום גורסת שאין יותר כאלה.

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

1. רעיון שהתחיל איתו כבר להמר(באותו מאמר ששיער את ההשערה, ראה[1]): ניסיון להראות שאם קיימים \({n}\)-ים כאלה אזי מספר הגורמים הראשוניים שלהם הוא גדול יחסית (התוצאה האחרונה מדברת על \({14}\) גורמים ראשוניים לפחות) .

2. רעיון של קרל פומרנץ([2]) מעין הכללה: מציאת חסם עליון למספר ה- \({n}\) ים הקטנים מ-\({x}\) כך ש-\({\varphi(n)|n-a}\) ל- \({a}\) כלשהו (בהשערה המקורית \({a=1}\)) התוצאה העדכנית מדברת על כך שיש לכל היותר \({\sqrt(x)}\) (בערך) כאלה.

1. D. H. Lehmer, On Euler’s totient function, Bull. Amer. Math. Soc., 38 (1932), 745-751.
2. C. Pomerance, On the congruences \({\sigma(n)\equiv a (mod n)}\) and \({n\equiv a (mod \varphi(n))}\), Acta Arith. 26 (1975), 265–272.
3. Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed. springer, New York 2004.

3 תגובות על השערת להמר

  • מאת koch‏:

    מאמר מצויין… תיקון קטן – בפירוט על פונקציית אוילר, כשn=12 המספרים הקטנים מ12 וזרים לו הם 1,5,7 ו-11 לא 12.

  • מאת admin‏:

    כמובן. תוקן. תודה רבה!