פולינומים ציקלוטומים ומשפט זיגמונדי

0. הקדמה

היום נתעסק הרבה בפולינומים, ובעיקר בסוג מסויים של פולינומים שנקראים "פולינומים ציקלוטומים". נסביר איך 'ממציאים' אותם, ונראה שהם מופיעים באופן טבעי בתורת המספרים. בקצרה, הם הפולינומים שמופיעים בפירוק של x^n-1 לגורמים אי-פריקים (לפולינומים עם מקדמים שלמים שאי-אפשר לפרק עוד).

נציג שימושים שלהם בפיתרון משוואות דיופנטיות, בחישובים טריגונומטריים ועוד.

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

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

1. מוטיבציה והגדרה

בבית הספר אנחנו לומדים בעל-פה את הפירוק של a^2-b^2, a^3 \pm b^3:

a^2-b^2=(a-b)(a+b)

a^3\pm b^3 = (a \pm b)(a^2 \mp ab + b^2)

אפשר לעשות זאת לביטויים דומים ממעלות גבוהות יותר:

a^4-b^4 = (a^2-b^2)(a^2+b^2)=(a-b)(a+b)(a^2+b^2)

a^5-b^5 = (a-b)(a^4 + a^3 b + a^2 b^2 + ab^3 + b^4)

a^6-b^6 = (a^3-b^3)(a^3+b^3) = (a^2-b^2)(a^4-a^2b^2+b^4)=(a-b)(a+b)(a^2-ab+b^2)(a^2+ab+b^2)

תקציר מנהלים למה שהולך לקרות בפרק זה: אנחנו נראה שהפירוק של a^n-b^n נובע מהפירוק של x^n-1.
לכל n, בפירוק של x^n-1 יופיעו רק פולינומים עם מקדמים שלמים, וביניהם יופיע פולינום שלא הופיע בפירוק של הפולינומים הקודמים, \{ x^ i - 1 \} _{i<n}. פולינום זה נקרא "הפולינום הציקלוטומי ה-n-י" ומסומן ב-\phi_n. לדוגמא: \phi_1(x) = x-1, \phi_2(x) = x+1.

נוכיח את ההגדרה הבאה ונסביר למה היא טבעית: \phi_n(x) = \frac{x^n-1}{\text{LCM}_{d|n, d \neq n} (x^d-1)}.
בנוסף, נוכיח את הנוסחה הרקורסיבית הנוחה הבאה: \prod_{d|n} \phi_{d}(x) = x^n-1.

תופעות

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

א. בפירוק מופיעים רק פולינומים הומוגנים, משמע – פולינומים שכל המונומים בהם הם מאותה מעלה. לדוגמא, ב-a^2-ab+b^2 יש שלושה מונומים ושלושתם ממעלה 2.

ב. בפירוק מופיעים רק פולינומים במקדמים שלמים. לדוגמא, לא מופיע יצור כמו a+\frac{b}{2}.

התופעה הראשונה היא מקרה פרטי של עובדה כללית יותר – פולינום הומוגני מתפרק לפולינומים הומוגנים. זה תרגיל נחמד שאשאיר לכם.

לפני שנסביר את התופעה שנייה, נדבר על הומוגניזציה ודה-הומוגניזציה. אלו 2 תהליכים הפוכים זה לזה, שהופכים פולינום ב-n משתנים לפולינום הומוגני ב-n+1 משתנים, ולהיפך.

הומוגניזציה:

f(x_1, \cdots, x_n) \mapsto x_0^{d} f(\frac{x_1}{x_0}, \cdots, \frac{x_n}{x_0})

כאשר d היא מעלת f.

דה-הומוגניזציה:

f(x_0, \cdots, x_n) \to f(1, x_1, \cdots, x_n)

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

h(f\cdot g) = h(f) \cdot h(g) , dh(f \cdot g) = dh(f) \cdot dh(g)

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

אם נפעיל זאת במקרה שלנו, נקבל שהפירוק של a^n-b^n נובע ישירות מהפירוק של x^n-1. זה נחמד, כי יותר קל להתעסק עם פולינומים במשתנה אחד מאשר עם שניים.

הלמה של גאוס

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

למה (גאוס): יהיו f,g פולינומים עם מקדמים שלמים. נניח שהמחלק המשותף המקסימלי של המקדמים של f הוא 1, וכך נניח גם לגבי g (פולינומים כאלו נקראים "פרימיטיבים"). אזי גם f \cdot g פרימיטיבי.

לפני ההוכחה, נציג מסקנה שאתם תוכיחו:

מסקנה 1: נגדיר את הפונקציה \text{cont}(f) להיות המחלק המשותף המקסימלי של מקדמי f. הפונקציה הנ"ל היא כפלית.

הוכחת הלמה: נניח בשלילה שלמקדמים של f \cdot g יש מחלק משותף גדול מ-1. בפרט, יש ראשוני p שמחלק את כל המקדמים של המכפלה. כלומר, אם נטיל את הפולינומים מודולו p, נקבל שהמכפלה היא 0: \overline{f} \cdot \overline{g} = 0, כאשר השיוויון הוא ב-\mathbb{Z}/p\mathbb{Z}[x], שהוא תחום שלמות. על כן, אחד מהפולינומים \overline{f}, \overline{g} הוא 0 בתחום זה, כלומר בלי הגבלת הכלליות כל המקדמים של f מתחלקים ב-p, סתירה. \blacksquare

כעת נראה למה הלמה רלוונטית לנו:

מסקנה 2: נניח שפולינום פרימיטיבי f מעל השלמים מתפרק למכפלה של 2 פולינומים עם מקדמים רציונלים, g,h. קיים c רציונלי (שונה מ-0) כך ש-c\cdot g, \frac{h}{c} בעלי מקדמים שלמים.

בפרט, x^n-1 פרימיטיבי (כי הוא מתוקן) ולכן כל פירוק שלו לפולינומים עם מקדמים רציונליים אפשר "לתקן" לפירוק עם פולינומים עם מקדמים שלמים.

הוכחת מסקנה 2: נתחיל מהפירוק f = g \cdot h. נכתוב: g =c_1 g_1, h= c_2 h_1, כאשר g_1,h_1 פולינומים פרימיטיבים עם מקדמים שלמים ו-c_1, c_2 רציונליים. נניח ש-c_1 c_2 = \frac{x}{y}.  נקבל:

g_1 h_1 x = f y

נפעיל את הפונקציה \text{cont} על שני האגפים ונקבל x = y, כלומר g_1 h_1 = f ו-c_1 c_2 = 1. לכן המסקנה הוכחה עם c = c_2. \blacksquare

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

מסקנה 3: נניח ש-f,g פולינומים בעלי מקדמים שלמים ופרימיטיבים. נניח ש-f מחלק את g ב-\mathbb{Q}[x]. אז הוא בעצם מחלק אותו ב-\mathbb{Z}[x], והמנה היא פולינום פרימיטיבי.

חזרות

אפשר לראות שיש חזרות של פולינומים בין הפירוקים השונים. לדוגמא, x-1 מופיע בפירוק של x^n-1 תמיד, ו-x+1 מופיע בפירוק כאשר n זוגי. מה ההסבר לכך? ההסבר נובע מהשיוויון הבא שאקרא לו "נוסחת ה-gcd":

\gcd(x^n - 1, x^m-1) = x^{gcd(n,m)} -1

שיוויון זה הוא גם שיוויון בפולינומים, אבל גם שיוויון במספרים (כלומר הוא נכון גם כש-x שלם, אבל גם כש-x משתנה). בואו נראה את נכונותו – נניח ש-n \ge m ונתחיל להפעיל את אלגוריתם אוקלידס:

x^n-1 - (x^m-1) = x^n-x^m = x^m(x^{n-m} - 1) \implies \gcd(x^n-1,x^m-1) = \gcd(x^m (x^{n-m} - 1), x^m-1) = \gcd(x^{n-m}-1, x^{m}-1)

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

מכאן מקבלים שבפירוקים של x^n-1, x^m-1 יופיעו כל הגורמים של x^{gcd(n,m)-1}. למעשה, אלה יהיו כל הגורמים המשותפים בין שני הפירוקים.

הגדרה, סוף כל סוף

נראה שלכל n יש פולינום 'מיוחד' שמחלק את x^n-1 אבל לא את הפולינומים הקודמים לו, שהם \{ x^i - 1\}_{i=1}^{n-1}. פולינום זה יקרא 'הפולינום הציקלוטומי ה-n-י', ויסומן \phi_n. אז איך מגדירים אותו פורמלית? כך:

\phi_n(x) = \frac{x^n-1}{\text{LCM}_{d|n, d\neq n} (x^d-1)}

בואו נבין למה. ראשית, פעולת ה-LCM (מכפלה משותפת מינימלית) מוגדרת היטב, כי \mathbb{Q}[x] הוא חוג ראשי ויש בו פריקות יחידה של פולינומים.

אנחנו באמת רוצים לחלק ב-LCM הזה, כי אמרנו שאנחנו רוצים פולינום שלא מחלק את x^i-1 עבור i<n. אבל לכאורה יש 2 בעיות:

1. למה אני מחלק רק פעם אחת ב-LCM? לדוגמא, אם אקח את הפולינום x^2(x+1) וארצה לקחת גורם שלו שלא מתחלק ב-x, אז לא מספיק לי לחלק אותו פעם אחת ב-x כי אקבל פולינום שעדיין מתחלק ב-x. מה שאני צריך לעשות כדי שהוא יהיה זר ל-x זה לחלק אותו פעמיים ב-x. למה במקרה שלנו מספיק לחלק פעם אחת? פשוט בגלל שבפירוק של x^n-1 אין גורמים כפולים. איך רואים זאת? עובדה ידועה (שתופיע בתרגיל בהמשך) היא שלפולינום יש גורם כפול אמ"מ הוא לא זר לנגזרת שלו. במקרה שלנו, הנגזרת היא nx^{n-1} והיא זרה ל-x^n-1. לכן אין פולינום שמחלק את x^n-1 פעמיים.

2. למה ב-LCM מופיעים רק הפולינומים x^d-1 כאשר d|n, d\neq n? מה עם d-ים שלא מחלקים את n? ההסבר הוא כזה: אם p(x) הוא איזשהו גורם שמחלק גם את x^n-1 אבל גם את x^i - 1 (כאשר i<n), אז מנוסחת ה-\gcd הוא מחלק גם את x^{\gcd(i,n)}-1, שזה פולינום מהצורה x^d-1 כאשר d|n, d<n ואנחנו אכן דואגים להיפטר ממנו.

תרגיל 1 (נגזרות וגורמים כפולים): נניח שפולינום p מתחלק בפולינום q^2. הראו ש-p' מתחלק ב-q, ובפרט, \gcd(p,p') מתחלק ב-q. הסיקו שפולינום מתחלק באיזשהו גורם פעמיים אם ורק אם הנגזרת שלו לא זרה לו.

תרגיל 2 (הגדרה אלטרנטיבית): הראו שב-LCM מספיק לקחת מחלקים מהצורה \frac{n}{p} עבור ראשוניים p|n, כלומר: \phi_n(x) = \frac{x^n-1}{\text{LCM}_{p|n} (x^{n/p} - 1) }. יתרה מכן, אפשר לתת הגדרה דומה עם \gcd:

\phi_n(x) = \gcd_{d|n} \frac{x^n-1}{x^d-1} = \gcd_{p|n} \frac{x^n-1}{x^{n/p}-1}

כעת ננסה לפשט את ההגדרה המסובכת שקיבלנו.

טענה:

\forall n \ge 1: x^n-1 = \prod_{d|n} \phi_{d}(x)

ובנוסף, \phi_n זר לכל הקודמים לו, קרי: זר לפולינומים \phi_1, \cdots, \phi_{n-1}. (זה שקול לכך ש-\{ \phi_{d}(x) \}_{d\ge 1} זרים בזוגות.)

הוכחה: ההוכחה היא באינדוקציה ישירה. עבור n=1 זה ברור. כעת נניח שזה נכון לכל המחלקים של n ונראה שזה מתקיים גם ל-n:

\text{LCM} (x^{d}-1)_{d|n,d\neq n}=\text{LCM} (\phi_{i})_{i|d|n, d \neq n}=\text{LCM} (\phi_{d})|_{d|n,d\neq n}=\prod_{d|n,d\neq n}\phi_{d}

(השיוויון האחרון נבע מהזרות.) כעת נכפיל את 2 האגפים ב-\phi_n ואגף שמאל נהיה x^n-1 לפי ההגדרה המקורית, כלומר קיבלנו x^n-1 = \prod_{d|n} \phi_d(x) כמו שרצינו.

כעת נראה גם את הזרות. יהי k קטן מ-n. הפולינומים \phi_n, \phi_k מחלקים את x^n-1, x^k-1 בהתאמה, שראינו שה-gcd שלהם הוא x^{\gcd(k,n)} - 1. (הערה: בפרט, נובע שאם \phi_n, \phi_k אינם זרים אזי \gcd(k,n) > 1.)

כאמור, ה-\gcd של הפולינומים מחלק את x^{\gcd(n,k)} -1, שהוא מכפלת \phi_d עבור d| \gcd(n,k) (מהנחת האינדוקציה), אבל \phi_k זר לכל אלו – אלא אם הוא מופיע שם בעצמו (שוב מהנחת האינדוקציה), כלומר אם במקרה (n,k) = k. במקרה זה, k|n וזוג הפולינומים \phi_n, \phi_k זרים מההגדרה המקורית של \phi_n: בהגדרה המקורית יש שבר שבמכנה שלו יש מכפלה גדולה שכוללת את \phi_k (כי k|n), כלומר דואגים שהם יהיו זרים. \blacksquare

בעצם קיבלנו הגדרה חדשה ורקורסיבית, והיא:

\prod_{d|n} \phi_d(x) =x^n-1

(יש שמתחילים בהגדרה זו.) להגדרה זו יתרונות רבים, לדוגמא – ישר רואים שהפולינומים זרים בזוגות, כי \phi_{a} \cdot \phi_{b} | x^{ab} -1 והפולינום x^{ab}-1 נטול גורמים כפולים.

כעת נציין 3 עובדות חשובות על פולינומים ציקלוטומים.

1. הפולינומים הציקלוטומים הם פולינומים (ולא פונקציות רציונליות ממש, לדוגמא) – נובע מההגדרה הראשונה.

2. הפולינומים הציקלוטומים הם בעלי מקדמים שלמים – אפשר לראות זאת מההגדרה הראשונה, הם מוגדרים בתור מנה של 2 פולינומים מתוקנים עם מקדמים שלמים, ומהלמה של גאוס המנה היא גם בעלת מקדמים שלמים.

3. הפולינומים הציקלוטומים הם אי-פריקים, כלומר הנוסחה x^n-1 = \prod_{d|n} \phi_d(x) מהווה את הפירוק המלא של x^n-1 מעל השלמים – זו עובדה מעניינת ולא טריוויאלית שנטפל בה רק בהמשך.

תרגיל 3 (מבוסס על USAMO 2008, שאלה 1): יהי n \ge 1. בנו מפורשות סדרת מספרים טבעיים זרים בזוגות \{ a_1, \cdots, a_n \} כך שכל המכפלות a_1, a_1a_2, \cdots, a_1 a_2 \cdots a_n הן מהצורה \phi_{3}(x)=x^{2}+x+1 עבור איזשהו x שלם.

תרגיל 4 – קשה מאוד (IMC 2010, יום שני, שאלה 5): תהי f פונקציה מהממשיים לממשיים. נניח ש-f מתאפסת זהותית על איזשהו קטע פתוח. בנוסף, נתון שלכל ראשוני p, הפונקציה הבאה מתאפסת על כל הישר הממשי:

\sum_{k=0}^{p-1} f(x + \frac{k}{p})

הראו ש-f מתאפסת על כל הישר. (רמז: הגדירו את אוסף הפולינומים הבא – J_{n} = \{ \sum a_i t^i | \sum a_i f(x + \frac{i}{n}) \equiv 0 \}. הראו שהוא מכיל את \phi_n(t).)

2. מקרים פרטיים, נוסחאות מפורשות והגדרות חדשות

נחשב כמה משפחות של פולינומים ציקלוטומים בידיים. תוך כדי החישוב נשים לב לתבניות חוזרות שלבסוף נכליל.

בכל החישובים נצטרך את \phi_1: \phi_1(x) = x-1.

עבור p ראשוני:

\phi_p(x) = \frac{x^p-1}{\phi_1(x)} = \frac{x^p-1}{x-1} = 1+x+\cdots + x^{p-1}

באופן כללי יותר, עבור חזקת ראשוני p^k:

\phi_{p^k}(x) = \frac{\phi_{1}(x) \phi_{p}(x) \cdots \phi_{p^{k-1}}(x)\phi_{p^k}(x)}{\phi_{1}(x) \phi_{p}(x) \cdots \phi_{p^{k-1}}(x)} = \frac{x^{p^k}-1}{x^{p^{k-1}} - 1} = 1 + x^{p^{k-1}}+x^{2p^{k-1}} + \cdots + x^{(p-1)p^{k-1}} = \phi_{p}(x^{p^{k-1}})

וכעת, מקרה של מכפלת ראשוניים שונים, p \cdot q:

\phi_{pq}(x) = \frac{x^{pq}-1}{\phi_{p}(x)\phi_{q}(x)\phi_{1}(x)} = \frac{(x^{pq}-1)(x-1)}{(x^p-1)(x^q-1)}

וכבר יותר קשה לכתוב את המקדמים במפורש. עבור שלושה ראשוניים, p \cdot q \cdot r, יש מכפלה דומה:

\phi_{pqr}(x) = \frac{x^{pqr}-1}{\phi_{pq}(x)\phi_{qr}(x)\phi_{rp}(x)\phi_{p}(x)\phi_{q}(x)\phi_{r}(x)\phi_{1}(x)} = \frac{(x^{pqr}-1)(x^p-1)(x^q-1)(x^r-1)}{(x^{pq}-1)(x^{qr}-1)(x^{rp}-1)(x-1)}

בשלב זה אנחנו מוכנים לקבל דרך ישירה ונוחה לחישוב פולינומים ציקלוטומיים – היפוך מביוס! היפוך מביוס הוא שם מפוצץ למקרה פרטי של הכלה-הדחה. נתון לנו ש-x^n-1 = \prod_{d|n} \phi_d(x) לכל n, ואנחנו נרצה לכפול ולחלק משיוויונות אלו עד שנבודד את \phi_m(x) באגף ימין ונציגו כמכפלה ומנה של ביטויים מהצורה x^d-1 באגף שמאל. אני לא אפתח כאן את התורה (הלא-מסובכת) של היפוך מביוס, אבל אתם יכולים לקרוא עליה במסמך שפרסמתי כאן על פונקציות אריתמטיות, או בבלוג של גדי.

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

\phi_{n}(x) = \prod_{d|n} (x^d-1)^{\mu(\frac{n}{d})}

כאשר \mu היא פונקציית מביוס. ביטוי זה ל-\phi_n מאפשר לנו לקבל עוד הוכחה לכך ש-\phi_n פולינומים עם מקדמים שלמים, ואף לחשב את שורשיהם: המכפלה הנ"ל מראה ש-\phi_n הוא מנה של פולינומים מתוקנים עם מקדמים שלמים. אנחנו מקבלים איזושהי פונקציה רציונלית. אנחנו יודעים איך x^n-1 מתפרק – זו המכפלה \prod_{0 \le i <n } (x-w_n^i) כאשר w_n = e^{\frac{2\pi i}{n}}. לכן אפשר לחשב את הפירוק של \phi_n:

\phi_{n}(x) = \prod_{d|n} (x^{d}-1)^{\mu(n/d)}=\prod_{d|n,0\le i<d}(x-w_{d}^{i})^{\mu(n/d)}=\prod_{k=0}^{n-1}(x-w_{n}^{k})^{\sum_{d|(k,n)}\mu(d)}=\prod_{(k,n)=1}(x-w_{n}^{k})

כאשר השתמשנו בתכונה המגדירה של פונקציית מביוס, \sum_{d|n} \mu(d) = \delta_{n,1}.

קיבלנו של-\phi_n אין קטבים, רק אפסים מסדר 1, כלומר הפונקציה הרציונלית הזו היא פולינום, ששורשיו הם שורשי היחידה מסדר n בדיוק. זה מקור השם "ציקלוטומי" – שורש יחידה חיים על מעגל היחידה, "ציקלוס" (cycle).

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

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

1. \phi_n(x) = \frac{x^n-1}{\text{LCM}_{d|n} (x^d-1)}

2. x^n-1 = \prod_{d|n} \phi_{d}(x)

3. \phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}

4. \phi_n(x)=\prod_{1 \le i \le n, (i,n)=1} (x-w_n^i)

כבר שמנו לב שאת \phi_{p^k} אפשר להביע כהרכבה של \phi_{p} עם x^{p^{k-1}}. נכליל זאת:

אם p | n אז \phi_{np^k} שווה ל-\phi_{n}(x^{p^k}). אחרת, אם p \nmid n, נקבל \phi_{np^k}(x) = \frac{\phi_{n}(x^{p^k})}{\phi_{n}(x^{p^{k-1}})}.

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

אם מפעילים תכונה זו כמה פעמים, מקבלים שכל פולינום ציקלוטומי אפשר להביע כהרכבה של פולינום ציקלוטומי מהצורה \phi_{p_1 \cdots p_r}(x) (כאשר p_i ראשוניים שונים) עם מונום x^m. במפורש,

\phi_{\prod p_i^{a_i}} (x) = \phi_{\prod p_i}(x^{\prod p_i ^{a_i -1}})

תרגילים

תרגיל 1: הראו ש-\phi_{n} (x^m) = \prod_{d|m, (d,n)=1 } \phi_{\frac{nm}{d}}(x). בפרט, \phi_{n} (x^m) אי-פריק אמ"מ כל ראשוני שמחלק את m מחלק את n, ובמקרה זה הפולינום שווה ל-\phi_{nm}(x).

תרגיל 2: הראו ש-|\phi_n(2)| > 1 עבור n>1. הסיקו מכך ומהתרגיל הקודם שאם 4^n + 2^n + 1 ראשוני אז n חזקה של 3.

תרגיל 3: הראו שהמקדמים של \phi_{pq}(x) = \sum a_k x^k (כאשר p,q ראשוניים שונים) יכולים להיות רק \pm 1, 0.

למעשה, אם נבחר r,s אי-שליליים כך ש-(p-1)(q-1) = rp+sq (תמיד קיימים כאלו),

a_k = \begin{cases} 1 & k=ip+qj, (i,j) \in [0,r] \times [0,s] \\ -1 & k+pq=ip+qj, (i,j) \in [r+1,q-1] \times [s+1, p-1] \\ 0 & \text{Otherwise} \end{cases}

3. תכונות בסיסיות ומקדמים

1. מעלה: המעלה של \phi_n היא \phi(n).
דרך אחת לראות זאת היא באמצעות ההגדרה של השורשים – יש \phi(n) שלמים בין 0 ל-n-1 שזרים ל-n, וכל שלם כזה מתאים לשורש יחידה שונה מסדר n בדיוק. לחילופין, אפשר להשתמש בהגדרה \prod_{d|n} \phi_d(x) = x^n-1 באופן הבא: נחשב את המעלה של 2 האגפים ונקבל \sum_{d|n} \deg\phi_{d}=n. ידוע ש-\sum_{d|n} \phi(d) = n, ולכן חיסור של 2 השיוויונות ואינדוקציה על n מראה ש-\deg \phi_n = \phi(n).

2. מקדם מוביל: הפולינומים מתוקנים (נובע מכמעט כל ההגדרות).

3. מקדמים שלמים: ראינו זאת בכמה דרכים, רובן עירבו את הלמה של גאוס. דרך נוספת היא זו: מההגדרה בעזרת היפוך מביוס, ברור שהמקדמים רציונליים (מנה של 2 פולינומים ב-\mathbb{Q}[x]). בנוסף, המקדמים הם שלמים אלגבריים – הם פולינומים סימטריים אלמנטרים בשורשי הפולינום, ושורשים אלו הם שלמים אלגברים בתור שורשי יחידה (כי שורש יחידה מסדר n מתאפס ע"י הפולינום x^n-1, שהוא בעל מקדמים שלמים ומתוקן).
כדי לסיים, ניזכר בעובדה הבאה (שהיא תרגיל נחמד אם אתם לא מכירים): המספרים הרציונליים היחידים שהם גם שלמים אלגבריים הם המספרים השלמים.

4. ערך באפס (מקדם חופשי): בעזרת ההגדרה עם היפוך מביוס מקבלים:

\begin{cases} \phi_{1}(0) = -1 & \text{if } n = 1 \\ \phi_{n}(0) = 1 & \text{if } n > 1 \end{cases}

עוד דרך לחשב זאת היא לשים לב שהמקדם החופשי הוא מכפלת שורשי היחידה הפרימיטיביים כפול (-1)^{\phi(n)}, ולהשתמש באינבולוציה w \to w^{-1} על שורשי היחידה.

5. ערך ב-1 (סכום מקדמים):

\begin{cases} \phi_{1}(1) = 0 & \text{if } n = 1 \\ \phi_{p^k}(1) = p & \text{if } n = p^k \\ \phi_{n}(1) = 1 & \text{otherwise} \end{cases}

הסבר: עבור n=1 זה נובע מההגדרה. בשאר המקרים, ניקח את ההגדרה \prod_{d|n} \phi_d(x) = x^n-1, נחלק ב-x-1 ונציב x=1:

\prod_{1 < d |n} \phi_{d}(1) = n

מקבלים מהיפוך מביוס את השיוויון \phi_n(1) = \prod_{d|n} d^{\mu(n/d)} עבור n>1.
עבור n=p^k (חזקת ראשוני) האיברים הלא-טריוויאלים במכפלה מתאימים ל-d= n, n/p ומקבלים: \phi_n(1) = \frac{n}{n/p} = p.
אפשר להראות שבשאר המקרים הערך הוא 1, כלומר \sum_{d|n} \ln d \cdot \mu(\frac{n}{d}) = 0 (ודאו זאת). זה קשור לפונקציית Von Mangoldt שמופיעה בתורת המספרים האנליטית.

6. ערך במינוס 1: חישובים דומים לסעיף הקודם מראים:

\begin{cases} \phi_{1}(-1) = -2 & \text{if } n=1 \\ \phi_{n}(-1) = 1 & \text{if } n>1 \text{ is odd} \\ \phi_{n}(-1) = \phi_{n/2}(1) & \text{if } n \text{ is even} \end{cases}

7. סימטריה: עבור n>1, יש סימטריה במקדמי הפולינומים, כלומר \phi_{n}(x)=x^{\phi(n)}\phi_{n}(x^{-1}). שיוויון זה נובע מכך שבשני האגפים יש פולינומים מתוקנים עם אותם שורשים עם אותו ריבוי.

מעניין לציין שעובדה פשוטה זו תשמש אותנו בהמשך כשנוכיח שיש אינסוף ראשוניים מהצורה -1 \mod n! היא תאפשר לנו לכתוב את \phi_{n} (x) x^{-\frac{\phi(n)}{2}} כפולינום עם מקדמים שלמים ב-x+\frac{1}{x}, אל תחמיצו.

8. נגזרת באפס (מקדם של x^1): עבור n=1 מתקיים \phi_n'(0) = 1. באופן כללי, עבור n>1, מתקיים \phi_{n}'(0)=-\mu(n).
הסבר: ניקח את הזהות \prod_{d|n} \phi_d(x) =x^n-1 ונגזור אותה לוגריתמית (נחליף את השיוויון f=g ב-\frac{f'}{f} = \frac{g'}{g}). המוטיבציה לכך היא שפעולה זו הופכת כפל לחיבור (\frac{(fg)'}{fg} = \frac{f'}{f}+\frac{g'}{g}) ויותר קל לעבוד איתה מאשר סתם לקחת נגזרת, ואכן מקבלים סכום נחמד שננסה לעשות לו היפוך:

\sum_{d|n}\frac{\phi_{d}'}{\phi_{d}}=\frac{nx^{n-1}}{x^{n}-1}

אכן אפשר לעשות היפוך מביוס ולקבל:

\frac{\phi_{n}'}{\phi_{n}}=\sum_{d|n}\mu(\frac{n}{d})\frac{dx^{d-1}}{x^{d}-1}

נותר להציב x=0 ולשים לב שרק למחובר של d=1 יש תרומה שאולי אינה אפסית. \blacksquare
מעניין לשים לב שמסימטריה, המקדם שחישבנו שווה (עד כדי סימן) למקדם של x^{n-1}, ששווה למינוס סכום השורשים של הפולינום, כלומר למינוס סכום שורשי היחידה הפרימיטיבים. מגניב.

תרגילים

תרגיל 1 (ערכי מקדמים):

כבר ראינו שהמקדמים של \phi_{p}, \phi_{pq} הם רק \{-1 ,0, 1\}. למעשה, כל הפולינומים הציקלוטומיים עד \phi_{104} מקיימים תכונה זו. אך אל תתנו לראיות האמפיריות להשלות אתכם – כל מספר שלם יכול להופיע כמקדם של פולינום ציקלוטומי! למעשה ל-\phi_{105} יש מקדם -2. הבנייה הסטנדרטית תינתן בתרגיל הזה.

א. הראו שלכל מספר טבעי t \ge 3, קיימת סדרת ראשוניים אי-זוגיים עולה p_1 < \cdots < p_t כך ש-p_1 + p_2 > p_t. (רמז: הניחו בשלילה שהטענה לא נכונה, והראו שבקטע [2^k, 2^{k+1}] יש פחות מ-t ראשוניים, לכל k. הגיעו לסתירה בעזרת העובדה שכמות הראשוניים עד x היא \Omega( \frac{x}{\ln x}).)

ב. לכל t טבעי אי-זוגי, הסתכלו על הפולינום \phi_{p_1 \cdot p_2 \cdots p_t}. השתמשו בנוסחה עם היפוך מביוס והראו שמודולו x^{p_t + 1} הפולינום שווה ל-(1+x+\cdots + x^{p_t}) (1-x^{p_1} - x^{p_2} - \cdots - x^{p_t}). בפרט, המקדמים של x^{p_t-2}, x^{p_t} הם -t+2, -t+1. באופן זה הצלחנו לייצר מקדמים שליליים.

ג. כדי לדאוג למקדמים החיוביים, השתמשו בזהות \phi_{2p_1 \cdots p_t}(x) = \phi_{p_1 \cdots p_t}(-x).

תרגיל 2 (רקורסיה למקדמים): אפשר למצוא נוסחה רקורסיבית למקדמים של \phi_n(x) = \sum_{k} a_n(k) x^k. הנוסחה היא:

a_n(k) = \frac{-1}{k} \sum_{i=0}^{k-1} a_n(i) s_n(k-i)

כאשר s_n(i) = \mu (\frac{n}{(n,i)} ) \frac{\phi(n) }{\phi( \frac{n}{(n,i)})}. השלימו את הפרטים בהוכחות הבאות:

1. דרך א': נחזור לנוסחה שקיבלנו מהנגזרת הלוגריתמית, \sum_{d|n} \frac{\phi_d'}{\phi_d} = \frac{nx^{n-1}}{x^n-1}. נגזור אותה עוד k-1 פעמים ונציב x=0.

2. דרך ב': נסמן S_n(i) = \sum_{i=1,\cdots,n,(i,n)=1} w_n^i. אלו סכומי רמנוג'אן – סכום החזקות ה-i-יות של שורשי \phi_n. אפשר לחשב אותם בעזרת היפוך מביוס, כמו בתרגיל על פונקציות אריתמטיות שפרסמתי כאן, ולקבל S_n(i) = s_n(i).
באופן כללי, עבור פולינום p(x) = \sum a_k x^k יש קשר הדוק בין סכומי חזקות שורשים של פולינום למקדמי פולינום, קשר שנתון ע"י זהויות ניוטון:

a_k = \frac{-1}{k} \sum_{i=0}^{k-1} a_i S_{k-i}

כאשר S_i הן סכום החזקות ה-i-יות של שורשי p. נפעיל קשר זה על הפולינומים הציקלוטומים ונקבל את הרקורסיה שהבטחנו.

תרגיל 3 (טריגונומטריה): אפשר לעשות חישובים טריגונומטריים לא טריוויאלים בעזרת פולינומים ציקלוטומים.

א. יהי n>1 מספר טבעי שאינו חזקת ראשוני. הראו ש-\prod_{1 \le k < n, (k,n) = 1} \sin \frac{k \pi}{n} = 2^{-\phi(n)}. (רמז: השתמשו ב-\phi_n(1) ובכך ש-1-w_n^k = -2i \sin \frac{k \pi}{n} e^{k \pi i /n}.)

ב. כעת הניחו ש-n=p^a>2 חזקת ראשוני, והראו שהמכפלה הנ"ל יוצאת p2^{-\phi(n)}.

ג. יהי n>1 מספר טבעי אי-זוגי. הראו ש-\prod_{1 \le k < n, (k,n) = 1} \cos \frac{k \pi}{n} = (-1)^{\phi(n)/2} 2^{-\phi(n)}. (רמז: השתמשו ב-\phi_n(-1) ובכך ש-1+w_n^k = 2 \cos \frac{k \pi}{n} e^{k \pi i /n}.)

4. תכונות אריתמטיות

גורמים של פולינומים ציקלוטומים

בחלק זה ננסה להבין איך נראים הגורמים הראשוניים של \phi_n(a). ספוילר: הם מהצורה 1 \mod n, חוץ אולי מיוצא דופן אחד, שהוא המחלק הראשוני המקסימלי של n. לדוגמא, עבור n=4, נקבל שהגורמים של \phi_4(a) = a^2+1 הם מהצורה 1 \mod 4, או 2. ועכשיו לפרטים:

אם p מחלק את \phi_n(a), אז בפרט הוא מחלק את a^n-1. במילים אחרות, הסדר של a מודולו p מחלק את n. נסמן את הסדר ב-\text{ord}_{p}(a).

אם הסדר הוא בדיוק n, קורה דבר מגניב: בגלל שמהמשפט הקטן של פרמה ידוע שהסדר מחלק את p-1, מקבלים: n| p-1, כלומר p = 1 \mod n, כמו שרצינו.

אחרת, ניקח גורם ראשוני q שמחלק את \frac{n}{\text{ord}_{p}(a)}. המספר \frac{n}{q} מתחלק בסדר, כלומר a^{n/q} = 1 \mod p.

מצד שני, בגלל ש-\phi_n(x) | \frac{x^n-1}{x^{n/q}-1} = 1 + x^{n/q} + x^{2n/q} + \cdots + x^{(q-1)n/q} ו-p | \phi_n(a) נקבל ש:

1 + a^{n/q} + a^{2n/q} + \cdots + a^{(q-1)n/q} = 0 \mod p

נשתמש בשיוויון a^{n/q} = 1 \mod p ונקבל q = 0 \mod p, כלומר p=q. נובע ש-\frac{n}{\text{ord}_{p}(a)} שווה לחזקת p, כלומר הסדר הוא מהצורה \frac{n}{p^{a}} עבור a \ge 1.
כמו קודם, ממשפט פרמה הקטן, הסדר מחלק את p-1, מה שמראה ש-n | (p-1)p^a. זה מראה ש-p הוא הגורם הראשוני המקסימלי של n. \blacksquare

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

מקרה פרטי של משפט דיריכלה

נראה שימוש יפהפה לתובנה שלנו לגבי מחלקים של פולינומים ציקלוטומים.

משפט: יהי n \ge 2 טבעי. יש אינסוף ראשוניים מהצורה 1 \mod n.

הוכחה: נתחיל בלייצר ראשוני אחד כזה: נגדיר את הפולינום g(x) = \phi_n(nx). עבור x שלם גדול מספיק, הפולינום הזה מקבל ערך גדול מ-1, ובפרט יש לו לפחות גורם ראשוני אחד, p.

מהאיפיון של הגורמים של \phi_n, נובע ש-p \equiv 1 \mod n או ש-p מחלק את n.
נראה שהאפשרות השנייה מובילה לסתירה: \phi_n(nx) \equiv \phi_n(0) = 1 \mod p, כאשר אגף שמאל אמור להתחלק ב-p.

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

נניח שיצרתי r ראשונים כאלו: p_1, \cdots, p_r. אסמן את המכפלה שלהם ב-N. בדומה לשלב הקודם, ניקח גורם ראשוני של \phi_n(nNx) עבור x גדול מספיק. הגורם בהכרח זר ל-n, וגם ל-N (שוב שימוש בכך ש-\phi_n(0) = 1), כלומר זה ראשוני מהצורה 1 \mod n ששונה מהראשוניים שהשגנו עד כה. נסמן אותו ב-p_{r+1} ונמשיך. \blacksquare

לכל מי שתוהה – אי-אפשר להכליל רעיון זה למשפט דיריכלה, שבפרט גורס שיש אינסוף ראשוניים מהצורה a \mod b לכל a,b זרים. מה שכן, הטריק הזה עובד תחת האילוץ הנוסף a^2 = 1 \mod b. זו דרישה חזקה, אבל לדוגמא עבור b=24, כל המספרים הזרים ל-b שווים ל-1 מודולו b כשמעלים אותם בריבוע – אז אפשר לקבל את דיריכלה מודולו 24. אפשר לקרוא על כך כאן (זהירות, תורת המספרים האלגברית לפניכם). בתרגילים אתן עוד מקרה פרטי מעניין במיוחד.

גורמים משותפים של פולינומים ציקלוטומים

יהיו \phi_a, \phi_b פולינומים ציקלוטומים שונים. יש להם שורשים שונים ולכן בפרט הם זרים. מתוך אלגוריתם אוקלידס המוכלל ב-\mathbb{Q}[x], אנחנו מקבלים שקיימים זוג פולינומים p,q עם מקדמים רציונלים כך ש:

\phi_a(x) p(x) + \phi_b(x) q(x) = 1

אם נכפיל את 2 האגפים במספר טבעי מתאים, נוכל להחליף את p,q בפולינומים עם מקדמים שלמים ואת 1 במספר טבעי כלשהו d(a,b). מכאן ינבע שלכל מספר שלם n, המחלק המשותף המקסימלי של \phi_a(n), \phi_b(n) יחלק את d(a,b) – בלי תלות ב-n!

מעניין לחשב את המספר הזה. מסתבר שלרוב הוא 1, ובשאר המקרים הוא חזקה של ראשוני. לדוגמא, הפולינומים \phi_{3}(x) = x^2+x+1, \phi_{4}(x) =x^2+1 תמיד יקבלו ערכים זרים, אבל \phi_{4}(x), \phi_{8}(x) = x^4+1 יכולים להתחלק סימולטנית ב-2.

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

טענה: אם \phi_a(n), \phi_b(n) מתחלקים בגורם ראשוני p, ו-b>a, אז \frac{b}{a} הוא חזקה של p.
בפרט, זה אומר ש-p נקבע ביחידות, כלומר: \gcd( \phi_a(n), \phi_b(n)) הוא חזקה של p!

הוכחה: יהי p גורם ראשוני של \gcd( \phi_a(n), \phi_b(n)) כאשר b \ge a.

נכתוב a= A \cdot p^{a'}, b = B \cdot p^{b'} כך ש-A,B לא מתחלקים ב-p. ניזכר שמודולו p מתקיים:

p \nmid m \implies \phi_{mp^k}(x) = \frac{\phi_{m}(x^{p^k})}{\phi_{m}(x^{p^{k-1}})} \equiv \phi_{m}(x)^{\phi(p^k)} \mod p

(בגלל ש-f(x^p)=f(x)^p \mod p.) נובע ש-\phi_{A}(n), \phi_{B}(n) מתחלקים ב-p. אם A\neq B, מקבלים של-x^{AB} - 1 יש שורש כפול מודולו p (כי הוא מתחלק ב-\phi_A \cdot \phi_B), והוא n. כדי שלפולינום זה יהיה שורש כפול, דרוש ש-AB יתחלק ב-p (קריטריון הנגזרת), סתירה. על כן A=B, מה שגורר \frac{b}{a} חזקה של p. \blacksquare

תרגילים

תרגיל 1 (Lifting The Exponent): יהי a מספר שלם גדול מ-1 בערך מוחלט, יהי p ראשוני שלא מחלק את a ויהי r הסדר של a מודולו p.

נסמן ב-v_p(x) את הריבוי של p בפירוק של x. הראו כי עבור p\neq 2:

v_p (a^{n}-1 ) = \begin{cases} v_p( a^{r}-1 ) + v_p( \frac{n}{r} ) & r|n \\ 0 & r \nmid n \end{cases}

ובמקרה הזוגי:

v_2 ( a^{n}-1 ) =\begin{cases} v_2(a-1) & 2 \nmid n \\ v_2 ( a^2 - 1 ) + v_2 ( \frac{n}{2}) & 2|n \end{cases}

תרגיל 2 (ראשוניים מהצורה -1 \mod n): יהי n \ge 2 טבעי. השלימו את הפרטים בהוכחה הבאה:

א. כדי להוכיח שיש אינסוף ראשוניים מהצורה -1 \mod n, מספיק להראות זאת עבור n > 6.

ב. הראו שאפשר לכתוב את \phi_n(x) x^{-\phi(n)/2} כפולינום מתוקן עם מקדמים שלמים ב-x+\frac{1}{x}. נסמן פולינום זה ב-\psi_{n}(x).

ג. הראו שאם \psi_{n}(x) בעל שורש a \in \mathbb{F}_{p}, אז או ש-p|2n, או ש-p \equiv \pm 1 \mod n. (רמז: מצאו b \in \mathbb{F}_{p^2} כך ש-b+\frac{1}{b} = a. פרקו לשני מקרים, לפי b \in \mathbb{F}_{p} או לאו.)

ד. הראו שקיימים a,b,c רציונליים כך ש-h_n(x) = c \cdot \psi_n(ax+b) מקיים את 3 התכונות הבאות: מקדם מוביל חיובי, מקדמים שלמים, ומקדם חופשי מינוס 1.

ה. נסמן ב-N את מכפלת המכנים של a,b,c. הראו שאם p מחלק את h_n(x), אז p | 2N או p \equiv \pm 1 \mod n.

ו. חקו את ההוכחה עבור ראשוניים מהצורה +1 \mod n: נייצר ראשוני מהצורה -1 \mod n ע"י כך שניקח גורם ראשוני מתאים של h_n(2Nx) עבור x גדול מספיק: בזכות התנאי h_n(0) = -1, מתקיים h_n(2Nx) = -1 \mod n והגורמים זרים ל-2N. לכן הם חייבים להיות מהצורה p \equiv \pm 1 \mod n. הם לא יכולים להיות כולם מהצורה 1 \mod n (אחרת h_n(2Nx) \equiv 1 \mod n), לכן לפחות אחד מהם מתאים לנו – אותו ניקח!

איך נמשיך? נניח שיצרנו את הראשונים המתאימים p_1, \cdots, p_r. נסמן את מכפלתם ב-M, ונסתכל על h_n(2N M x) עבור x גדול מספיק כך שהביטוי יהיה גדול מ-1. הגורמים הראשוניים שלו זרים ל-2N ולכן הם מהצורה \pm 1 \mod n. מהשיקול הקודם לפחות אחד מהם הוא -1 \mod n, ובזכות זה שדחפנו את M לתוך h, דאגנו לכך שהוא יהיה שונה מ-p_1, \cdots, p_{r}. נסמנו p_{r+1} ונמשיך.

(אם אבדתם בפרטים, הנה דוגמא: כדי להראות שיש אינסוף ראשוניים מהצורה -1 \mod 8, אפשר להשתמש בפולינום h_8(x) = 2x^2-1: הגורמים של h_8(2x) הם מהצורה \pm -1 \mod 8 (לדוגמא, מתוך (\frac{2}{p} ) = (-1)^{\frac{p^2-1}{8}}.) בנוסף, לא יתכן שכולם מהצורה 1 \mod 8 פשוט כי h_8(2x) \equiv -1 \mod 8.)

תרגיל 3 (רזולטנטות):

א. כמו שהזכרנו קודם, עבור 2 פולינומים מתוקנים זרים f,g \in \mathbb{Z}[x], קיים שלם שונה מאפס באידאל (f,g) \subseteq \mathbb{Z}[x]. את השלם הקטן ביותר קשה לחשב, אבל יש קבוע מעניין אחר שהוא כפולה שלו, שנקרא רזולטנטה. כדי להגדיר אותו, נסמן ב-\{ r_i \}_{i=1}^{\deg f}, \{ s_ j \}_{j=1}^{\deg g} את השורשים של f,g (בסגור האלגברי), עם ריבוי. הרזולטנטה מוגדרת כך:

\text{Res}(f,g) = \prod_{1\le i \le \deg f, 1\le j \le \deg g} (r_i - s_j)

ב. הראו שהרזולטנטה שווה ל-\prod_{i=1}^{\deg f} g(r_i) = \prod_{j=1}^{\deg g} f(s_j). הגדרה זו טובה גם כאשר f,g לא מתוקנים (להבדיל מההגדרה הקודמת).

ג. הראו שהרזולטנטה היא מספר שלם שנמצא באידאל (f,g).

ד. הראו שלשני פולינומים יש שורש משותף מודולו ראשוני p אמ"מ p מחלק את הרזולטנטה שלהם.

ד. (קשה) נניח כי a >b\ge 1. הראו כי:

\text{Res}(\phi_a, \phi_b) = \begin{cases} 1 & a/b \text{ is not a prime power} \\ p^{\phi(b)} & a/b \text{ is a power of } p \end{cases}

ה. מושג קשור מאוד הוא הדיסקרימיננטה של פולינום. הדיסקרימיננטה מוגדרת בתור הרזולטנטה של פולינום והנגזרת שלו. הוכיחו שהיא מקיימת את התכונה הבאה – ל-f יש שורש כפול מודולו p אמ"מ p מחלק את הדיסקרימיננטה.

ו. (קשה) הראו שהדיסקרימיננטה של פולינום ציקלוטומי \phi_n היא (-1)^{\phi(n)/2 } \frac{n^{\phi(n)} }{ \prod_{p|n} p^{\phi(n)/(p-1)} }.

תרגיל 4 (מתוך IMO Shortlist, 2006): הוכיחו שלמשוואה הדיופנטית הבאה אין פתרונות בשלמים:

\frac{x^7 - 1}{x-1} = y^5-1

הכלילו את העובדה הזו למשוואה הבאה:

\frac{x^7 - 1}{x-1} = y^p-1

כאשר p ראשוני מהצורה 2 \mod 3.

תרגיל 5: יהי n מספר טבעי. הראו שסכום המחלקים שלו הוא חזקה של 2 אם ורק אם הוא מכפלה של ראשוני מרסן שונים (ראשוניים מהצורה 2^ k -1).

תרגיל 6 (חיזוק של שאלה מ-IMO Shortlist 2002): יהיו p_1, \cdots, p_n ראשוניים שונים גדולים מ-3. הראו של-2^{p_1 \cdots p_n} + 1 יש לפחות 2^{2^{n-1}} מחלקים.
(רמז: מספיק למצוא 2^{n-1} גורמים זרים של המספר. השתמשו בזהות 2^{p_1 \cdots p_n} + 1 = \prod_{d | p_1 \cdots p_n} \phi_{2d}(2).)
(הערה: בשאלה המקורית החסם היה 4^n, שקטן/שווה מהחסם החדש עבור n \ge 4.)

5. אי-פריקות וקצת אלגברה

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

השדה הציקלוטומי ה-n

הפולינום המינימלי של \omega_n חייב לחלק את \phi_n. בפרט, השורשים הצמודים של \omega_n יכולים להיות רק שורשי יחידה פרימיטיבים אחרים (מסדר n).

\mathbb{Q}(\omega_n) הוא השדה הקטן ביותר המכיל את שורש היחידה ה-n-י. הוא מכיל את חזקותיו של \omega_n, כלומר את שאר שורשי היחידה הפרימיטיבים מסדר n, כלומר זה שדה פיצול של הפולינום המינימלי של w_n ועל כן זו הרחבה נורמלית. בנוסף, זו הרחבה ספרבילית (כי אנחנו עובדים מעל מציין 0). נובע שזו הרחבה גלואה. נשאלת השאלה: מהי חבורת הגלואה?

ראשית, הגודל שלה תלוי במימד ההרחבה שתלוי במעלת הפולינום המינימלי.

שנית, כל איבר בחבורה נקבע לפי הפעולה שלו על שורש היחידה ה-n-י, שחייב ללכת לשורש יחידה פרימיטיבי מסדר n: אם \sigma \in \text{Gal} לוקחת את w_n ל-w_n^i (כאשר i זר ל-n) אז w_n^j הולך ל-w_n^{ij}. לכן אפשר לזהות את \sigma עם האיבר i ב-(\mathbb{Z} / n \mathbb{Z})^{\times}, ובאופן זה מתקבל שיכון של חבורת גלואה ב-(\mathbb{Z} / n \mathbb{Z})^{\times}.

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

הוכחת אי-פריקות

עכשיו, כשהבנו את ההשלכות של אי-הפריקות, נוכיח אותה. נשים לב ש-\phi_{1}, \phi_{2} אי-פריקים כי הם פולינומים ממעלה 1.

המקרה הראשוני

המקרה המוכר והשימושי מכולם הוא המקרה של n=p ראשוני:

\phi_p(x) = \frac{x^p-1}{x-1}= 1 + x + \cdots + x^{p-1}

פולינום זה אי-פריק אמ"מ \phi_p(x+1) = \frac{(1+x)^p-1}{(1+x)-1} = \sum_{i=1}^{p} \binom{p}{i} x^{i-1} אי-פריק.

נניח בשלילה שקיים לפולינום הנ"ל פירוק f(x) g(x) מעל הרציונלים כאשר \deg f, \deg g>0. מהלמה של גאוס, אפשר להניח שהפולינומים בעלי מקדמים שלמים, ולמעשה מתוקנים (כי הפולינום הציקלוטומי מתוקן). אפשר להטיל את הפירוק מודולו p, ולקבל פירוק של \phi_p(x+1) ב-\mathbb{Z}/p\mathbb{Z}[x]:

\phi_p(x+1) = \frac{(1+x)^p-1}{(1+x)-1} \equiv \frac{1+x^p - 1}{x} = x^{p-1} \mod p

(השתמשנו בכך ש-f(x)^p \equiv f(x^p) \mod p.) בגלל שהפולינום מנוון מודולו p, בהכרח מתקיים \overline{f} = x^i, \overline{g} = x^j, i+j=p-1. נובע שהמקדמים החופשיים של f,g מתחלקים ב-p. בפרט, המכפלה f\cdot g בעלת מקדם חופשי שמתחלק פעמיים ב-p. מצד שני, המכפלה שווה ל-x^{p-1} + \binom{p}{p-1} x^{p-2} + \cdots + \binom{p}{2} x + \binom{p}{1}, והמקדם החופשי שלה הוא p, סתירה. \blacksquare

(הערה: הגרסה הכללית של טיעון זה נקראת 'קריטריון איזנשטיין'.)

המקרה של חזקת ראשוני

המקרה הטבעי הבא הוא המקרי של \phi_{p^k}. הטיעון יהיה דומה – נסתכל על הזזה של הפולינום, המקדמים שלו יתחלקו ב-p, אבל המקדם החופשי יתחלק רק פעם אחת ב-p:

\phi_{p^k}(x+1) = \sum_{i=0}^{p-1} (x+1)^{p^{k-1}i} = \sum_{i=0}^{p-1} \sum_{j=0}^{p^{k-1} i} x^j \binom{p^{k-1} i}{j}

המקדם החופשי הוא \sum_{i=0}^{p-1} \binom{p^{k-1} i}{0} = p, כמו שרצינו.

שאר המקדמים מתחלקים ב-p גם כן. כדי להראות זאת, אפשר להשתמש במשפט לוקאס, אבל אפשר שוב להשתמש בשיוויון f(x^p) = f(x)^p שנכון כשעובדים עם פונקציות רציונליות ב-\mathbb{Z}/p\mathbb{Z}[X]:

\phi_{p^k}(x+1) = \frac{(x+1)^{p^k} - 1}{(x+1)^{p^{k-1}} - 1} \equiv \frac{x^{p^k} + 1-1}{x^{p^{k-1}} + 1-1} = x^{p^ k - p^{k-1}} \mod p

ומסיימים את ההוכחה כמו קודם.

המקרה הכללי

יש אינספור הוכחות מעניינות למקרה הכללי. נציג 2 הוכחות שונות מאוד.

הוכחה 1: יהי m(x) הפולינום המינימלי של w_n, שבפרט מחלק את \phi_n(x). שורשיו הם שורשי יחידה פרימיטיביים מסדר n (לאו דווקא כולם).

נראה שאם z הוא שורש של m, אז לכל p ראשוני שלא מחלק את n מתקיים ששורש היחידה הפרימיטיבי z^p הוא שורש של m(x). זה יספיק, כי שורש יחידה פרימיטיבי כללי מסדר n מתקבל מ-w_n ע"י העלאתו בחזקות של מספרים ראשוניים זרים ל-n. כך נראה של-m יש לפחות \phi(n) שורשים, ולכן הוא שווה ל-\phi_n (משיקולי מעלות).

יהי z שורש של m(x) ו-p \nmid n. נניח בשלילה ש-m(z^p) \neq 0. נסמן g(x) = \frac{x^n - 1}{m(x)}. בגלל ש-z^p שורש של x^n-1 נובע ש-g(z^p) = 0.

בגלל ש-p \nmid n, לפולינום x^n-1 אין שורשים כפולים מודולו p (כי לנגזרת שלו אין שורשים), ובפרט m,g זרים כשמטילים אותם מודולו p. מצד שני, אם נחשוב על \mathbb{Z} / p\mathbb{Z} בתור \mathbb{Z}[z]/(1-z), נקבל ש-\overline{z} שורש של m אבל גם של g (כי \overline{g}(\overline{z})^p = \overline{g}(\overline{z^p}) = 0), סתירה.

הוכחה 2 (מתקדמת): יהי m הפולינום המינימלי של w_n. כמו שראינו, ההרחבה \mathbb{Q}(w_n) / \mathbb{Q} היא הרחבת גלואה ואנחנו מעוניינים להראות שמעלתה \deg m שווה \phi(n).

נשאל את השאלה הבאה: אלו ראשוניים p מתפצלים בהרחבה (כלומר מתי האידאל (p) הוא מכפלה של \deg m אידאלים עם ריבוי 1)? בדיוק הראשוניים עבורם m(x) מתפצל לגורמים לינאריים מודולו p (עד כדי כמות סופית של ראשוניים 'רעים' שמחלקים את הדיסקרימיננטה). מתי קורה התפצלות זו? כשיש שורש יחידה מסדר n ב-\mathbb{Z} / p \mathbb{Z}. החבורה הכפלית של הסדרה היא ציקלית ומסדר p-1, לכן נדרש: p \equiv 1 \mod n. ממשפט דיריכלה שהזכרנו מקודם, יש אינסוף ראשוניים שמקיימים זאת, ויתרה מכך – צפיפותם בתוך הראשוניים (במובן מוגדר היטב שנקרא 'צפיפות דיריכלה') היא \frac{1}{\phi(n)}.

מצד שני, מקרה פרטי של משפט פרובניוס (שבתורו הוא מקרה פרטי של משפט צ'בוטרב) גורס כי צפיפות הראשוניים שמתפצלים בהרחבה הוא 1 חלקי מעלת ההרחבה, כלומר \frac{1}{\deg m}. על כן \deg m = \phi(n). \blacksquare

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

תרגילים

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

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

תרגיל 3: נסתכל על האידאל (p) בחוג השלמים \mathbb{Z}[w_p]. הראו שהפירוק של אידאל זה לאידאלים ראשוניים הוא (1-w_p)^{p-1}. (רמז: הציבו x=1 ב-\phi_p(x).) במילים אחרות, (p) מסועף לחלוטין.

תרגיל 4: מצאו את כל רביעיות המספרים השלמים (a,b,m,n) כך ש-m,n \ge 1 ו-x^n+ax+b | x^m + ax+b.

תרגיל 5: תהי \theta כפולה רציונלית של \pi.

א. הראו שאם \sin \theta הוא מספר רציונלי, אז הוא שווה לאחד המספרים 0, \pm 1, \pm \frac{1}{2}. כנ"ל עם \cos \theta.

ב. הראו שאם \tan \theta רציונלי אז הוא שווה לאחד המספרים 0, \pm 1.

תרגיל 6: יהיו f,g שתי פונקציות מ-\mathbb{Z} / n \mathbb{Z} לשלמים. נניח שהקונבולוציה של f,g מתאפסת, כלומר: \forall k: \sum_{i+j=k} f(i)g(j) = 0. הראו שהקונבולוציה של f(x) עם g(xm) גם מתאפסת, כאשר m \in (\mathbb{Z} / n \mathbb{Z} )^{\times}.

תרגיל 7 (הדדיות ריבועית): השלימו את הפרטים הבאים בהוכחה של הדדיות ריבועית.

א. יהי p ראשוני אי-זוגי. השתמשו בשיוויון p = \phi_{p}(1) כדי להסיק ש-(-1)^{\frac{p-1}{2}} p הוא ריבוע ב-\mathbb{Q}(w_p) (זה השלב הקריטי).
נסמן את השורש שלו ב-\tau, ונסמן ב-p* את (-1)^{\frac{p-1}{2}} p.

ב. יהי q ראשוני אי-זוגי אחר. נסמן ב-\sigma_{q} את אוטומורפיזם גלואה ששולח את w_p ל-w_{p}^{q}. הוא יכול לשלוח את \tau רק לעצמו או למינוס שלו, כי \tau^2 \in \mathbb{Q}.

ג. ממבנה חבורת גלואה ומהמשפט הבסיסי של תורת גלואה, \sigma_{q} מקבע את \tau אמ"מ \sigma_{q} ריבוע בחבורת גלואה, כלומר אמ"מ q ריבוע מודולו p. בסימונים: \sigma_{q} \tau = (\frac{q}{p}) \tau.

ד. הראו שיש אידאל ראשוני Q ב-\mathbb{Z}[w_p] שמכיל את q. מודולו Q מתקיים:

\sigma_{q} \tau = \tau^q \mod Q

ה. הראו את השיוויונות הבאים וסיימו את ההוכחה:

(\frac{p*}{q}) \equiv (p*)^{\frac{q-1}{2}} = \tau^{q-1} \equiv ( \frac{q}{p} ) \mod Q

תרגיל 8: הראו שהפולינום המינימלי של \cos(\frac{2\pi}{n}) הוא ממעלה \frac{\phi(n)}{2} כאשר n>2. האם תוכלו למצוא לו רקורסיה? פיתרון אפשר למצוא כאן.

6. התפרקות מעל שדות סופיים

אפשר להטיל את הפולינומים הציקלוטומיים מודולו p, ולשאול איך הם מתפרקים ב-\mathbb{F}_{p}[X], או אפילו ב-\mathbb{F}_{q}[X] כאשר q חזקה של p.
(הערה טכנית: כל השיוויונות שאכתוב בפרק זה הם מודולו p, גם כשאני לא מציין במפורש שאני עובד מודולו p.)

הבחנה

אם p | n, אז ראינו כי \phi_{n}(x) = \phi_{\frac{n}{p}}(x^{p}). מודולו p זה נהיה \phi_{\frac{n}{p}}(x)^{p}. נחזור על תהליך זה מספר פעמים, עד שנוציא מ-n את חזקת p שמחלקת אותו.

נובע שכדי להבין את הפירוק של \phi_n מודולו p, אפשר להניח p \nmid n.

מקרים פרטיים

נמשיך בשלושה מקרים פרטיים:

1. \phi_3(x) = x^2+x+1: מההבחנה הנ"ל, אנחנו יודעים שבמציין 3 תהיה התנהגות שונה, ואכן זה המקרה: \phi_3(x) \equiv (x-1)^2.
נמשיך עם p \neq 3. הפולינום מתפרק אמ"מ x^3-1 מתפרק לגמרי ("מתפצל"). בגלל שכל איברי \mathbb{F}_{q} (מלבד 0) מקיימים x^{q-1} = 1, ההתפרקות שקולה ל-x^3 - 1 | x^{q-1} - 1, תנאי ששקול ל-q \equiv 1 \mod 3.

כאשר המציין אינו 2, מעניין לשים לב ש-\phi_3(x) = (x+\frac{1}{2})^2 + \frac{3}{4}. כלומר הפולינום מתפרק אמ"מ -3 שארית ריבועית. בעצם הוכחנו מקרה פרטי של הדדיות ריבועית: \left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right).

2. \phi_4(x) = x^2+1: במציין 2 אנחנו מצפים להתנהגות שונה: x^2 + 1 \equiv (x+1)^2. בשאר המקרים, הפולינום מתפרק אמ"מ יש שורש למינוס 1, כלומר איבר מסדר 4 בחבורה הכפלית של השדה. בגלל שהחבורה ציקלית, זה שקול לכך ש-q \equiv 1 \mod 4. בעצם הוכחנו ש-\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}.

3. \phi_{8}(x) = x^4+1: פולינום זה מגניב במיוחד – הוא אי-פריק מעל השלמים בתור פולינום ציקלוטומי, אבל מייד נראה שהוא מתפרק מודולו כל ראשוני. עבור p=2 זה ברור – x^4+1 \equiv (x+1)^4.
בשאר המקרים, נניח בשלילה \phi_8 אי-פריק ב-\mathbb{F}_{p}. נובע שכדי שהפולינום יתפצל צריך לעבור להרחבה מסדר 4.
מצד שני, מספיקה הרחבה מסדר 2: בשדה \mathbb{F}_{p^2} יש התפצלות של הפולינום, כי יש שם שורש יחידה מסדר 8 (כי 8 | p^2 -1 לכל p אי-זוגי). סתירה.

כמובן שיש גם דרך סיזיפית לראות זאת – לפרק למקרים:

אם p \equiv 1 \mod 4, יש שורש למינוס 1, נסמנו i. אפשר לפרק את הפולינום כך: (x^2 + i)(x^2 - i). אם בנוסף p \equiv 1 \mod 8, יש התפצלות לגורמים לינאריים.

אם p \equiv 3 \mod 4, אין שורש למינוס 1, ולכן אחד מבין +2, -2 הוא ריבוע, ולכן אחד מהפירוקים הבאים מתקיים ב-\mathbb{F}_{p}: (x^2+\sqrt{2} x+1)(x^2 - \sqrt{2}x+1), (x^2+\sqrt{-2}x-1)(x^2 -\sqrt{-2} x-1). \blacksquare

המקרה הכללי

עד כאן דוגמאות. בואו נדבר על המקרה הכללי. נסתכל על \phi_{n}(x) ב-\mathbb{F}_{q} כאשר q = p^k, p \nmid n. לפולינום אין גורמים כפולים – הוא מחלק את x^n-1, שאין לו גורם משותף עם נגזרתו (בזכות הדרישה p \nmid n).

נניח שהפולינום מתפרק ב-\mathbb{F}_{q} למכפלה של פולינומים מתוקנים אי-פריקים f_1 \cdot f_2 \cdot \cdots \cdot f_r. כל אחד מהם הוא פולינום מינימלי של שורש יחידה פרימיטיבי אחר מסדר n, ולכן יש להם אותה מעלה: כל ההרחבות שנוצרות ע"י הוספת השורש הזה הן שקולות (כי הרחבה שמכילה שורש אחד מכילה את כל השאר ע"י העלאה בחזקה) ולכן יש להן אותה מעלה, נסמנה d.

מהי המעלה הזו? זה כמו לשאול מהו ה-d המינימלי עבורו יש ב-\mathbb{F}_{q^d} איבר מסדר n, כלומר n | q^d - 1, כלומר d הוא הסדר של q מודולו n.

לסיכום: \phi_n מתפרק למכפלה של \frac{\phi(n)}{\text{ord}_{n}(q)} פולינומים אי-פריקים ממעלה \text{ord}_{n}(q).

7. מספר שימושים קלאסיים ומודרניים

משפט Wedderburn

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

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

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

הוכחה: יהי R תחום שלמות סופי עם יחידה. ראשית נראה שהוא חוג חילוק.

יהי a \in R שאינו 0. נגדיר ההעתקה מהתחום לעצמו: f_a: x \mapsto ax. היא חח"ע, כי היא מעל תחום שלמות. בגלל שהוא סופי, ההעתקה היא גם על, בפרט קיים מקור ל-1, כלומר x כך ש-ax = 1. זה אומר של-a יש הופכי מימין ואפשר גם לראות שזה הופכי משמאל.
במילים אחרות, R הוא חוג חילוק. נותר להראות חילופיות.

ראשית, נגדיר את המרכז של החוג, Z, להיות אוסף האיברים שמתחלפים בכפל עם כל איברי החוג. זה תת-חוג חילופי שמכיל את 0 ו-1, וקל לראות שהוא גם סגור להופכי. במילים אחרות, זה שדה, והוא סופי. נסמן את גודלו ב-q.

החוג שלנו הוא מרחב וקטורי מעל המרכז, ולכן גודלו הוא q^n עבור איזשהו n. מטרתנו להראות ש-n=1.

נרצה להציג את R^{\times} = R \setminus {0} כאיחוד של מחלקות צמידות. מחלקת צמידות של איבר s היא הקבוצה A_s = \{ x^{-1} s x | x \neq 0 \}. היא מכילה את s, וגודלה 1 אמ"מ s במרכז Z. ניתן לראות שזוג מחלקות חייבות להיות או שוות או זרות, דבר שנובע מכך שאלו מחלקות שקילות לפי היחס הבא: s \sim s' \leftrightarrow s' \in A_{s}.

מה הגודל של מחלקת צמידות? שאלה טובה. ניקח איבר x^{-1}sx \in A_s, ונראה בכמה דרכים שונות הוא יכול להתקבל, כלומר עבור כמה y \in R^{\times} מתקיים x^{-1}sx= y^{-1}sy. בתקווה, כמות ה-y הזו לא תהיה תלויה ב-x. אכן כך הדבר:

x^{-1}sx = y^{-1}sy \leftrightarrow (yx^{-1})s = s(yx^{-1})

הדרישה היא ש-yx^{-1} יתחלף עם s. אם נסמן ב-C_{s} את אוסף האיברים שמתחלפים עם 0, אז yx^{-1} נמצא בקבוצה זו אמ"מ y \in C_{s}^{\times}, כלומר יש |C_s| - 1 אפשרויות. נשים לב ש-C_s מרחב וקטורי מעל המרכז ולכן גודלו מהצורה q^{n_s}. אנחנו מקבלים ש-

|A_s| = \frac{|R^{\times}|}{|C_s^{\times}|} = \frac{q^n-1}{q^{n_s} - 1}

בפרט, מתקיים n_s | n.

כאמור, אמרתי שאני רוצה לפרק את הקבוצה R^{\times} למחלקות צמידות. כל איבר נמצא באיזושהי מחלקת צמידות, המחלקות הללו זרות, ולגודל שלהן יש מבנה שחישבנו. לכן, מתקיים:

|R^{\times}| = |Z^{\times}| + \sum_{s \in S} |A_s|

כאשר המחובר |Z^{\times}| מתאים למחלקות בגודל 1, והסכום האחרון מתאים למחלקות שמכילות יותר מאיבר 1. מתקבלת המשוואה הדיופנטית הבאה:

q^n - 1 = q-1 + \sum_{s \in S} \frac{q^n-1}{q^{n_s} - 1}

נשים לב ש-\phi_n(q) מחלק את אגף שמאל, אבל גם את הסכום באגף ימין, כי \phi_n(x) | \frac{x^n-1}{x^d-1} לכל d|n, d < n. על כן,

\phi_n(q) | q-1

אי-שיוויון המשולש מראה ש-|q-w| > q-1 לכל שורש יחידה w שונה מ-1, ולכן אם n>1 מתקיים אז |\phi_n(q)| > q-1. על כן, בהכרח n=1. \blacksquare

קובית Sicherman

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

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

איך מגיעים לכך ומה הקשר לפולינומים ציקלוטומיים? מאוד פשוט. נסתכל על הפונקציה יוצרת של הקוביה הסטנדרטית: p(x) = x+ x^2 + \cdots + x^6 = x \frac{x^6-1}{x-1} = x \phi_{2}(x) \phi_{3} (x) \phi_{6}(x). אם נסמן ב-f(x),g(x) את הפונקציות היוצרות של הקוביות האחרות (אם ערכיה של קוביה הם a_1, \cdots ,a _6 אז הפונקציה יוצרת היא \sum_{i=1}^{6} x^{a_i}), אז אנחנו בעצם דורשים את התקיימות המשוואה הבאה:

f(x) g(x) = p(x)^2 = x^2 \phi_{2}(x)^2 \phi_{3}(x)^{2} \phi_{6}(x)^2

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

f= x \phi_2(x) \phi_3(x), g= x\phi_2(x)\phi_3(x) \phi_6(x)^2

ומתוך המונומים של f,g משחזרים את ערכי הקוביות.

אפשר לחקור את הבעיה עם יותר משתי קוביות, או יותר מ-6 פאות, ראו במאמר כאן.

חלוקות

את התוצאות הבאות אתן לכם להוכיח:

1. נסמן ב-f_m(n) את כמות החלוקות של n למספרים טבעיים שזרים ל-m. נסמן ב-r את מספר הגורמים הראשוניים השונים של m. מתקיים:

\sum_{n \ge 0} f_m(n) z^n = \prod_{n \ge 1} \phi_m(z^n)^{(-1)^{r-1}}

2. נסמן ב-q_{m}^{E}(n), q_{m}^{O}(n) את כמות החלוקות של n למספרים טבעיים זוגיים/אי-זוגיים בהתאמה שזרים ל-m. כמו מקודם, נסמן ב-r את מספר הגורמים הראשוניים השונים של m. מתקיים:

\sum_{n \ge 0} (q_{m}^{E}(n) - q_{m}^{O}(n) ) z^n= \prod_{n \ge 1} \phi_m(z^n)^{(-1)^{r}}

8. נוסחאות גאוס-לוקאס

נתחיל בשאלה.

שאלה (USAMO 2007, שאלה 5): הראו ש-7^{7^n} + 1 הוא מכפלה של לפחות 2n+3 ראשוניים, לאו דווקא שונים (לכל n \ge 0).

הוכחה: עבור n=0 זה נכון, כי 8 מתחלק בשלושה ראשוניים. ההוכחה ממשיכה באינדוקציה – מספיק להראות שהמנה הבאה אינה מספר ראשוני:

\frac{7^{7^{n+1}} + 1}{7^{7^n} + 1}

נסמן x =7^{7^n}. המנה נראית עכשיו כך: \frac{x^7+1}{x+1} = x^6-x^5+x^4-x^3+x^2-x+1 = \phi_{14}(x). "במקרה" הפולינום הציקלוטומי הזה ניתן לכתיבה באופן הבא:

\phi_{14}(x) = \phi_{7}(-x)= (x^3+3x^2+3x+1)^2 - 7x(x^2+x+1)^2

זה לא הפרש ריבועים, אבל זה קרוב. למעשה, בגלל ש-x הוא חזקה אי-זוגית של 7, אז 7x הוא ריבוע והמנה \phi_{7}(-x) היא אכן הפרש ריבועים. הפרש ריבועים a^2-b^2 לרוב אינו ראשוני בגלל שהוא מתפרק באופן הבא: (a-b)(a+b). מספיק לוודא שבמקרה שלנו |a\pm b| > 1, וסיימנו. זאת אשאיר לכם. \blacksquare

הפיתרון הזה נחמד והכל, אבל לא ברור מאיפה הוא בא והאם הוא ניתן להכללה? מסתבר שכן:

טענה: ל-p^{p^n}+1 יש לפחות 2n+2 גורמים כאשר p \equiv 3 \mod 4 ראשוני.

הוכחה חלקית: עבור n=0 הטענה נכונה. בשביל להשלים את האינדוקציה, צריך להראות ש-\phi_p(-p^{p^n}) לא ראשוני. אם יהיה לנו מזל כמו קודם, יהיה לנו פירוק מהצורה הבאה:

\phi_p(-x) = R(x)^2 - pxS^{2}(x)

כאשר R,S בעלי מקדמים שלמים. נציב x= -p^{p^n} ונקבל הפרש ריבועים. צריך לוודא שההפרש לא מנוון. \blacksquare

בפועל, באמת יש פירוק כזה וזה לא סתם מזל. למעשה, יש 2 פירוקים מפורסמים, הראשון נקרא על שם גאוס והשני על שם לוקאס. עבור n אי-זוגי נטול ריבועים,

\exists R,S \in \mathbb{Z}[x]: 4\cdot\phi_{n}(x) = R(x)^{2}-(-1)^{\frac{n-1}{2}}n S(x)^{2}

\exists R,S \in \mathbb{Z}[x] : \phi_{n}(x) = R(x)^{2}-(-1)^{\frac{n-1}{2} } n x S(x)^{2}

הנוסחה שניצלנו קודם היא נוסחת לוקאס עבור n = p מהצורה p \equiv 3 \mod 4.

הוכחת (חלקית) של הנוסחאות

אז איך מוכיחים אותן? זה לא כ"כ קל, ונובע משיקולים של תורת גלואה. אוכיח את הנוסחה הראשונה, נוסחת גאוס, במקרה ש-n ראשוני.

ניזכר בפרטים מההוכחה של הדדיות ריבועית בעזרת פולינומים ציקלוטומים (פרק 5, שאלה 7): השדה \mathbb{Q}(\sqrt{n (-1)^{\frac{n-1}{2}}}) הוא תת-שדה ריבועי של \mathbb{Q}(w_n) – נובע מכך ש-n (-1)^{\frac{n-1}{2}} ריבוע בשדה, דבר שרואים ע"י מניפולציות על הזהות n = \phi_n(1) = \prod_{i=1}^{n-1} (1- w_n^i). למעשה, תת-שדה ריבועי זה הוא שדה השבת של תת-חבורה מאינדקס 2 של חבורת גלואה, תת-חבורת הריבועים: \{ a \in (\mathbb{Z}/n\mathbb{Z})^{\times} | (\frac{a}{n}) = 1\}. נסמן תת-חבורה זו ב-G'.

הפולינום p(x) = \prod_{(a,n)=1, (\frac{a}{n}) = 1} (x-w_n^a) אינווריאנטי ל-G', מה שאומר שהוא פולינום עם מקדמים ב-\mathbb{Q}(\sqrt{n (-1)^{\frac{n-1}{2}}}). המקדמים שלו הם שלמים אלגברים, לכן צריך לחשב את השלמים האלגברים ב-\mathbb{Q}(\sqrt{n (-1)^{\frac{n-1}{2}}}): חישוב קצר מראה שהם יוצרים את החוג \mathbb{Z}[\frac{1+\sqrt{n (-1)^{\frac{n-1}{2}}}}{2}]. לכן אפשר לכתוב:

p(x) = \frac{R(x) + \sqrt{n(-1)^{\frac{n-1}{2}} } S(x)}{2}

כאשר R,S \in \mathbb{Z}[x] (הם מוגדרים ביחידות). נפעיל על 2 האגפים את ההצמדה (האוטומורפיזם הלא-טריוויאלי היחיד של \mathbb{Q}(\sqrt{n(-1)^{\frac{n-1}{2}}}) מעל \mathbb{Q}) ונכפול את 2 המשוואות, ונקבל:

\phi_n(x) = \frac{R(x)^2 - n(-1)^{\frac{n-1}{2}}S^2(x)}{4}

כאשר n לאו דווקא ראשוני, ההוכחה נראית אותו דבר, אבל יותר קשה להראות את הטענה הראשונה, כלומר ש-\mathbb{Q}(\sqrt{n (-1)^{\frac{n-1}{2}}}) הוא תת-שדה ריבועי של \mathbb{Q}(w_n). עוד שינוי קטן הוא שסימן לג'נדר הופך לסימן יעקובי (שעובד גם למודולוסים לא ראשוניים). \blacksquare

תרגיל 1 (קשה): הוכח ש-\frac{p^p-1}{p-1} אינו ראשוני כאשר p \equiv 1 \mod 4 ראשוני.

תרגיל 2 (קשה): הוכיחו את נוסחת לוקאס.

9. משפט זיגמונדי

נחזור לסוגיית הגורמים של \phi_n(a). ראינו בתחילת פרק 4 שהגורמים הם ראשוניים p כך שהסדר של a מודולו p הוא בדיוק n, חוץ אולי מיוצא דופן אחד, שהוא הגורם הראשוני המקסימלי של n. כל ראשוני שאינו הראשוני יוצא הדופן נקרא "ראשוני זיגמונדי" (Zsigmondy).

נסמן את הגורם הראשוני המקסימלי של n ב-q. נובע ש-\phi_n(a) הוא מכפלה של ראשוניי זיגמונדי (לאו דווקא שונים), וחזקה של q. מסתבר שאפשר להגיד משהו מעניין על הריבוי של q:

טענת עזר: חוץ מהמקרה n = q =2, הריבוי של q הוא לכל היותר 1. הוכחה: נניח שהריבוי חיובי. בפרק 4 ראינו שהסדר של a מודולו q מחלק את \frac{n}{q}, כלומר q| a^{n/q}-1.

בגלל ש-\phi_n(a) | \frac{a^n-1}{a^{n/q}-1}, מספיק להראות שהריבוי של q ב-\frac{a^n-1}{a^{n/q}-1} הוא בדיוק 1:

\frac{a^n-1}{a^{n/q}-1} = \frac{(a^{n/q}-1+1)^{q}-1}{a^{n/q}-1} = \sum_{i=1}^{q} (a^{n/q}-1)^{i-1} \binom{q}{i} = q + (a^{n/q}-1)\binom{q}{2} \mod {q^2}

(האיבר השלישי והילך מתחלקים ב-q^2.) אם q>2, אז \binom{q}{2} מתחלק ב-q, ולכן גם הביטוי (a^{n/q}-1)\binom{q}{2} מת מודולו q^2, וקיבלנו את מבוקשנו כי \frac{a^n-1}{a^{n/q}-1} \equiv q \mod {q^2}.

אם q=2, אז n = 2^k. אם n \ge 2, כלומר k >1, מתקיים:

\phi_{n}(a) = \phi_{2^k}(a) = a^{2^{k-1}} + 1

אם הביטוי הזה מתחלק ב-2 אז הוא שווה 2 מודולו 4 ולכן מתחלק בדיוק פעם אחת ב-2. \blacksquare.

אנחנו מוכנים לנסח את משפט זיגמונדי:

משפט זיגמונדי: יהיו a,n טבעיים גדולים מ-1. חוץ ממספר מקרים שיפורטו עוד רגע, קיים ראשוני q שמחלק את a^n-1 ולא מחלק את \{ a^i -1 \}_{i < n} (מה שנקרא, "ראשוני זיגמונדי ביחס ל-(a,n)"). המקרים הבעייתים הם:

1. n=2, a=2^s -1 , s \ge 2

2. n=6, a=2

הוכחה:

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

נניח n=2, כלומר \phi_n(a) = a+1. מהטענה הקודמת, גורם ראשוני של \phi_n(a) הוא בהכרח הגורם הראשוני המקסימלי של n, כלומר 2. נובע ש-a+1 חזקה של 2, וזה היוצא דופן הראשון של משפט זיגמונדי.

נניח n>2. מטענת העזר, \phi_n(a) = q כאשר q הוא הגורם הראשוני המקסימלי של n. השיקולים שיובילו לסתירה הם שיקולים אנליטיים – q קטן מידי לעומת \phi_n(a), חוץ ממקרה אחד.

אם q=2, נובע ש-n=2^s חזקה של 2. לכן 2 =q = \phi_n(a) = a^{2^{s-1}} + 1, כלומר a=1, סתירה. לכן q \ge 3. נכתוב n=q^i r, q \nmid r. מתקיים:

q = \phi_n(a) = \frac{ \phi_{r}(a^{q^i}) }{ \phi_{r} (a^{q^{i-1}} ) } = \frac{\prod_{j=1}^{\phi(r)} (a^{q^i} - w_r^j)}{\prod_{j=1}^{\phi(r)} (a^{q^{i-1}} - w_r^j)}> ( \frac{a^{q^i}-1}{a^{q^{i-1}} + 1} )^{\phi(r)} \ge \frac{a^{q^i}-1}{a^{q^{i-1}}-1} \ge a^{q^{i-1}(q-2)} \ge 2^{q-2}

אי-השיוויון q > 2^{q-2} גורר q=2,3. הנחנו q \ge 3, לכן q = 3. כשנציב q=3 בשרשרת אי-השיוויונות הנ"ל נקבל 3 > a^{3^{i-1}}, כלומר a=2 ו-i=1.

בגלל ש-q לא ראשוני זיגמונדי, הסדר של a מודולו q=3 הוא \frac{n}{q} (ראו תחילת פרק 4), ומהמשפט הקטן של פרמה: \frac{n}{q} | q-1. בגלל ש-q=3 מקבלים: n|6. הנחנו n \ge 3, לכן צריך לבדוק רק n=3,6.

אם n=3, אז \phi_{n}(a) = 2^2 + 2 + 1 = 7, ו-7 הוא ראשוני זיגמונדי, סתירה.

אם n=6, אז \phi_{n}(a) = 2^2-2+1 = 3, ואכן – אין ראשוני זיגמונדי ביחס ל-(a,n) = (2,6), זה המקרה יוצא הדופן השני של משפט זיגמונדי. \blacksquare

ניסוח אלטרנטיבי: יהיו a,n מספרי טבעיים גדולים מ-1. למספר a^n-1 יש גורם ראשוני שלא מחלק את המספרים \{ a^d - 1 \}_{d <n}, חוץ מבשני מקרים שתוארו בניסוח המקורי.

למשפט יש הרבה הכללות טבעיות, שלא נוכיח אבל נזכיר.

הכללה ראשונה: יהיו a>b > 1 מספרים טבעיים זרים, ו-n \ge 2. למספר a^n -b^n יש גורם ראשוני שלא מחלק את המספרים \{ a^d - b^d \}_{d <n}, חוץ מבשני מקרים: (a,b,n)=(2,1,6) ו-(a,b,n)=(a,2^k-a,2).

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

יש עוד הכללה מגניבה במיוחד ששמה לב לעניין הבא: t_n= a^n-b^n היא לא סדרה שרירותית – מדובר בסדרת נסיגה מסדר 2, עם פולינום אופייני (x-a)(x-b), כלומר t_{n+2} = (a+b)t_{n+1} - ab t_{n}.
הכללה שנייה: נגדיר את סדרת הנסיגה t_0=0,t_1 = 1,t_{n+2} = Lt_{n+1} - Mt_n. היא נתונה ע"י \frac{a^n - b^n}{a-b} כאשר a,b הפתרונות של x^2=Lx-M. נניח שהם ממשיים, כלומר L^2 > 4M. בנוסף, נניח ש-(L,M)=1.

אז לכל n יש גורם ראשוני שמחלק את t_n אבל לא מחלק את \{ t_d \}_{d<n}, חוץ אולי מהמקרים הבאים:

1. n \in \{ 1,2,6 \}

2. n=12, L=1 , M=-1

מה זה המקרה השני המוזר הזה? מדובר בסדרת פיבונאצ'י!  משפט זיגמונדי עבור סדרת פיבונאצ'י אומר שלכל מספר פיבונאצ'י יש מספר ראשוני שמחלק אותו אבל לא את הקודמים, חוץ מ-F_1 = 1, F_2 = 1, F_6 = 8, F_{12} = 144.

הוכחה (סקיצה): השלב הראשון הוא להגדיר פולינומים ציקלוטומים הומוגנים: \phi_n(x,y) = \prod_{1 \le i \le n, (i,n)=1} (x - w_n^i y) עבור n \ge 2, ו-\phi_1(x,y) = 1 (זו כמעט הומוגניזציה של הפולינומים הציקלוטומים). מתקיים: t_n = \prod_{d|n} \phi_d(a,b), ו-\phi_n(a,b) מספרים שלמים. זה כבר מגניב ונותן פירוק של (בין השאר) מספרי פיבונאצ'י.

בדומה למה שהראנו בפרק 4, אפשר להוכיח את העובדה הבאה: נניח n \neq 1,2,6. אם p ראשוני שמחלק את t_n אבל הוא לא מחלק פרימיטיבי שלו (כלומר, מחלק את \phi_n(a,b) אבל גם את אחד הערכים הציקלוטומים הקודמים), אז p|n והריבוי של p ב-\phi_n(a,b) הוא בדיוק 1.

נניח ש-n \neq 1,2,6. נובע שאם n= \prod p_i^{a_i}, ול-t_n אין גורם ראשוני פרימיטיבי, אז \phi_n(a,b) | \prod p_i. אפשר להראות ש-t_n מינימלי כאשר (L,M) \in \{ (1,-1),(3,2) \}, ואז משתמשים בשיקולים אנליטיים כדי להראות שבשני המקרים הללו לא יתכן ש-|\phi_n(a,b)| \le \prod_{p|n} p, חוץ מהמקרה n=12, (L,M)=(1,-1) (בו יש שיוויון). פרטים מלאים אפשר למצוא כאן. \blacksquare

אציין הכללה שלישית: גם הסדרה a^n+b^n מקיימת את התופעה של זיגמונדי (כאשר a>b \ge 1), חוץ מהמקרה (a,b,n)=(2,1,3).

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

תרגילים

תרגיל 1: יהיו p,q שני ראשוניים אי-זוגיים שונים. הראו של-2^{pq}-1 יש לפחות 3 גורמים ראשוניים שונים.

תרגיל 2: פתרו את המשוואה הבאה, כאשר p ראשוני: p^x - y^p = 1. ומה עם y^n - p^x = 1?

תרגיל 3: פתרו את המשוואה הבאה במספרים טבעיים: (a+1)^m = 1+a^n.

תרגיל 4 (ישראל-הונגריה 2006, יום ראשון, שאלה 1): נניח שיש פיתרון למשוואה x^n + y^n = p^k, כאשר n אי-זוגי גדול מ-1, p ראשוני אי-זוגי ו-x,y טבעיים. הוכיחו ש-n חזקה של p.

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

ברכות על ה-IOI ובהצלחה ב-IMO,

אופיר

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה כללי. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

3 תגובות על פולינומים ציקלוטומים ומשפט זיגמונדי

  1. פינגבאק: הנס של המקדמים הבינומים | One and One

  2. יוסי כהן הגיב:

    איך אני מדפיס את המאמר?

    • Ofir Gorodetsky הגיב:

      שלום יוסי,

      הוספתי היום אפשרות הדפסה לכל הפוסטים. עכשיו בסוף כל פוסט מופיעה השורה "Share this:", עם מספר כפתורים מתחתיה. בשביל להדפיס לחץ על "הדפסה".

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s