הנס של המקדמים הבינומים

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

0. מבוא

המקדמים הבינומים $\binom{n}{k}$ הם מספרים שלמים. מצד אחד, זה ברור – הם סופרים, בהגדרה, בכמה דרכים ניתן לבחור $k$ איברים מתוך קבוצה בגודל $n$ (או בניסוח שקול: כמה תתי-קבוצות מגודל $k$ יש לקבוצה בגודל $n$ ).
מצד שני, זה נס שהם שלמים. למה זה נס? כי אפשר לתת נוסחה למקדמים הללו, ובמבט ראשון לא ברור בכלל מהנוסחה שהם שלמים. הנוסחה היא:

$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1) \cdots 1}$

למי שלא זוכר מהיכן מגיעה הנוסחה, אזכיר: אגף שמאל סופר תתי-קבוצות בגודל $k$ . אגף ימין סופר אותן באופן הלא-ישיר הבא: נסדר את כל איברי הקבוצה, $n$ במספר, בשורה. יש לכך $n!$ דרכים. את תת-הקבוצה נבנה ע"י כך שניקח את $k$ האיברים הימניים בשורה. הבעיה: יש "יתירות", אנחנו סופרים כל תת-קבוצה פעמים רבות. ספציפית, כל תת-קבוצה נספרת בדיוק $k! \times (n-k)!$ פעמים (אפשר "לבלגן" את $k$ האיברים הימניים ואת $(n-k)$ האיברים השמאליים), מכאן החלוקה. $\blacksquare$

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

חידה: הראו שמכפלה של 100 מספרי פיבונאצ'י עוקבים מתחלקת במכפלה של 100 מספרי פיבונאצ'י הראשונים, כלומר: $F_1 F_2 \cdots F_{100} \mid F_{n+1} F_{n+2} \cdots F_{n+100}$ .

(הערה: הסימון $a \mid b$ משמעו "המספר $a$ מחלק את המספר $b$ ". בנוסף, הקונבנציה היא $F_1=F_2=1$ .)

1. אז למה המקדמים הבינומים שלמים?

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

הוכחה 1 (סטנדרטית אך ארוכה)

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

אז לכל ראשוני $p$ , נספור כמה פעמים הוא מופיע במונה ( $n!$ ) ובכמה במכנה ( $k! (n-k)!$ ). לשם כך, נצטרך טענת עזר:

טענת עזר (נוסחת לז'נדר): מספר הפעמים ש- $n!$ מתחלק בראשוני $p$ הוא $\sum_{i=1}^{\infty} \lfloor \frac{n}{p^i} \rfloor$ . (זה סכום סופי – החל מ- $i> \log_p n$ כל המחוברים הם 0.) הוכחה: $n!$ הוא מכפלת $n$ המספרים הטבעיים הראשונים. כמה מהם מתחלקים ב- $p$ ? בדיוק $\lfloor \frac{n}{p} \rfloor$ . ובאופן כללי, כמה מהם מתחלקים ב- $p^i$ ? בדיוק $\lfloor \frac{n}{p^i} \rfloor$ . על כן, כמה מהם מתחלקים ב- $p^i$ אבל לא ב- $p^{i+1}$ ? $\lfloor \frac{n}{p^i} \rfloor -\lfloor \frac{n}{p^{i+1}} \rfloor$ .
מספר בין 1 ל- $n$ שמתחלק ב- $p$ $i$ פעמים בדיוק תורם $i$ לכמות הפעמים ש- $n!$ מתחלק ב- $p$ , ולכן מספר הפעמים ש- $n!$ מתחלק בראשוני $p$ הוא $\sum_{i=1}^{\infty} i(\lfloor \frac{n}{p^i} \rfloor - \lfloor \frac{n}{p^{i+1}} \rfloor) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i} \rfloor$ . $\blacksquare$

מהנוסחה וההבחנה הקודמת, מספיק להוכיח כי:

$\sum_{i=1}^{\infty} \lfloor \frac{n}{p^i} \rfloor \ge \sum_{i=1}^{\infty} \lfloor \frac{n-k}{p^i} \rfloor + \sum_{i=1}^{\infty} \lfloor \frac{k}{p^i} \rfloor$

מה שנובע מהתרגיל הבא, שלמעשה מוכיח יותר ממה שאנחנו צריכים – שהמחובר ה- $i$ בסכום באגף שמאל גדול/שווה מהמחובר ה- $i$ בסכום באגף ימין:

תרגיל 1: $\lfloor x+ y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$ לכל $x,y$ ממשיים. (רמז: פונקציית הערך השלם התחתון היא בעלת מחזור 1.)

$\blacksquare$

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

הוכחה 2 (זהות פסקל)

המקדמים הבינומים מקיימים רקורסיה קומבינטורית פשוטה, והיא: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ . זו הזהות שעומדת בבסיס משולש פסקל, ומשמעותה הקומבינטורית היא זו: את תתי-הקבוצות מגודל $k$ של הקבוצה $\{1,2,\cdots ,n\}$ אפשר לחלק לשני סוגים – כאלו שמכילות את האיבר $n$ (ואז נותר לבחור עוד $k-1$ איברים מתוך קבוצה בגודל $n-1$ כדי לקבל את הקבוצה המיוחלת מגודל $k$ ), וכאלו שלא מכילות את האיבר $n$ (ואז בעצם את $k$ האיברים נבחר מתוך קבוצה מגודל $n-1$ , הלא היא $\{1,2,\cdots,n-1\}$ ).
ההוכחה הזו לרקורסיה הייתה קומבינטורית, אבל אפשר גם לתת הוכחה אלגברית: אם ניקח את השיוויון $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ ונחלק את 2 האגפים שלו ב- $\binom{n-1}{k-1}/k$ , נקבל את השיוויון השקול $n=k+(n-k)$ , שהוא בבירור נכון.

למה הרקורסיה הזו מעניינת? כי היא מאפשר לנו להוכיח את שלמות המקדמים הבינומים באינדוקציה ישירה: עבור $n=0$ ועבור $k=0$ השלמות היא מיידית (בשני מקרים אלו המקדם הבינומי שווה 1). נמשיך באינדוקציה על $n$ (תחת הדרישה $n \ge k \ge 1$ ), כאשר צעד האינדוקציה נובע מזהות פסקל (סכום של 2 מספרים שלמים הוא שלם). $\blacksquare$

הערה: אם עובדים עם פונקציות יוצרות, אפשר לנסח את זהות פסקל בתור $(1+x)^n = (1+x)(1+x)^{n-1}$ , כאשר $(1+x)^n$ ידועה בתור הפונקציה היוצרת של $\{ \binom{n}{k} \}_{k=0}^{n}$ .

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

2. סדרות GCD

ננסה להכליל את ההוכחה הנ"ל באופן הבא – נניח ש- $a_1,a_2,a_3,\cdots$ סדרה של מספרים שלמים חיוביים. אפשר להגדיר לסדרה הזו מקדמים בינומים משלה, "המקדמים הבינומים של $\overline{a}$ ", באופן הבא:

$n!_a := a_1 a_2 \cdots a_n, 0!_a := 1$
$\binom{n}{k}_{a} := \frac{n!_a}{k!_a (n-k)!_a} = \frac{a_n a_{n-1} \cdots a_{n-k+1}}{a_k a_{k-1} \cdots a_1}$

כלומר, קודם הגדרנו את פונקציית העצרת המתאימה לסדרה $\{a_n\}_{n=1}^{\infty}$ , ולאחר מכן הגדרנו את המקדמים הבינומיים המתאימים לסדרה באמצעות זה שחיקינו את הנוסחת למקדמים הבינומים הרגילים.

כדי לראות שיש כאן איזשהו היגיון, נשים לב שאם נבחר את הסדרה להיות $\forall n: a_n:=n$ , מקבלים את פונקציית העצרת הרגילה ואת המקדמים הבינומים הרגילים.

עכשיו ננסה להבין אלו דרישות על $a_1,a_2,\cdots$ יבטיחו שהמקדמים הבינומים הללו יהיו שלמים. במבט ראשון, אולי שאלה מוזרה (אך מעניינת). אל דאגה, יהיו לה שימושים.

טקטיקה יחסית טבעית היא לנסות לחקות את ההוכחה לכך שהמקדמים הבינומים הרגילים הם שלמים, ולראות מה צריך לדרוש כדי שההוכחה תעבוד. קודם כל, יש את מקרי הקצה – $n=0$ ו- $k=0$ . כאשר $n=0$ המקדם הבינומי של הסדרה שווה 1 (לפי הקונבנציה ההגיונית $0!_a = 1$ – כמו שסכום ריק שווה 0, אז מכפלה ריקה שווה 1). כאשר $k=0$ מקבלים שבמונה ובמכנה רשום אותו דבר – $n!_a$ – ולכן המקדם שוב שלם (ושווה 1).

כעת מגיע צעד האינדוקציה (על $n$ ). אנחנו רוצים להסיק ש- $\binom{n}{k}_{a}$ שלם מתוך כך ש- $\binom{n-1}{k-1}_a, \binom{n-1}{k}_a$ שלמים. קודם השתמשנו בזהות פסקל. מי מבטיח לנו זהות פסקל כעת?… אף אחד, אבל אנחנו לא צריכים זהות – אנחנו רק צריכים ש- $\binom{n}{k}_{a}$ יהיה שווה לקומבינציה לינארית של $\binom{n-1}{k-1}_a, \binom{n-1}{k}_a$ עם מקדמים שלמים, או בכתיב מתמטי:

$(*) \binom{n}{k}_a \in Span_{\mathbb{Z}} \{\binom{n-1}{k-1}_a, \binom{n-1}{k}_a\}$

הערה: הכתיב $Span_{\mathbb{Z}} \{x,y\}$ הוא לא סטנדרטי, ומציין את אוסף כל הקומבינציות הלינאריות של $x,y$ עם מקדמים שלמים. למי שמכיר קצת אלגברה מופשטת, ברור שזהו האידאל הנוצר ע"י $x,y$ בחוג השלמים.

בשני האגפים של $(*)$ יש ביטויים דומים – אפשר לחלק את 2 האגפים ב- $\binom{n-1}{k-1}_a$ ולקבל דרישה שקולה וקומפקטית יותר:

$(*) \frac{a_n}{a_k} \in Span_{\mathbb{Z}} \{ 1, \frac{a_{n-k}}{a_k}\}$

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

$(*) a_n \in Span_{\mathbb{Z}} \{ a_k, a_{n-k} \}$

באגף ימין נמצאת קבוצת כל הצירופים הלינארים עם מקדמים שלמים של $a_k, a_{n-k}$ . ברור שכל מספר שנמצא שם מתחלק במחלק המשותף הגדול ביותר של $a_k, a_{n-k}$ (ידוע בתור ה-GCD – Greatest Common Divisor). משפט קלאסי-ובסיסי-אך-עמוק באלגברה (אלגוריתם אוקלידס) אומר שהמחלק המשותף הגדול ביותר של 2 מספרים הוא בהכרח קומבינציה לינארית שלהם עם מקדמים שלמים, ומכאן נובע שבאגף ימין יש את כל הכפולות של $\gcd(a_k , a_{n-k})$ , ורק אותן. לכן הדרישה הופכת ל:

$(**) \gcd(a_k, a_{n-k}) \mid a_n$

זו כבר דרישה יפה (לטעמי). בתור "Sanity Check", אפשר להציב את המקרה הידוע $a_n =n$ ולראות שדרישה זו הופכת ל- $\gcd(k,n-k) \mid n$ , שמתקיימת מכיוון שאגף שמאל מחלק את $k,n-k$ ולכן גם את סכומם $k + (n-k) = n$ .

מסתבר שעל אף שדרישה $(**)$ היא כבר יפה, יש דרישה מעט חזקה יותר (כלומר – דורשת יותר…) אבל נוחה בהרבה. הדרישה היא:

$\forall n, m: \gcd(a_n, a_m) = a_{\gcd(n,m)}$

לסדרה שתקיים דרישה זו נקרא "סדרת GCD". המשמעות הלא פורמלית היא ש"GCD בפנים שקול ל-GCD בחוץ", או לחילופין, "הסדרה מתחלפת עם פעולת ה-GCD" (סורי על הג'יבריש).
העובדה שהסדרה $a_n=n$ היא סדרת GCD, לדוגמא, נובעת מיידית מההגדרה – נוח מאוד (ודאו!). כעת נסביר מדוע הדרישה הזו אכן חזקה יותר, כלומר מדוע הטענה הבאה נכונה:

טענה: כל סדרת GCD מקיימת את דרישה $(**)$ , ובכתיב מתמטי:

$\forall n,m: \gcd(a_n, a_m) = a_{\gcd(n,m)} \implies \forall n,k: \gcd(a_k, a_{n-k}) \mid a_n$

הוכחה: אם $\{a_n\}_{n \ge 1}$ סדרת GCD אז $\gcd(a_k, a_{n-k}) = a_{\gcd(k,n-k)}$ . לכן נותר להסביר מדוע $a_{\gcd(k,n-k)} \mid a_n$ . נשים לב ש- $\gcd(k,n-k) \mid n$ (כבר ראינו עובדה זו), ולכן אם הייתה לנו טענת קסם כמו " $n \mid m \implies a_n \mid a_m$ ", יכלנו לסיים. העניין הוא שטענת הקסם הזו נכונה:

טענת קסם: אם $\{a_n\}_{n \ge 1}$ סדרת GCD אז $n \mid m \implies a_n \mid a_m$ . הסבר: נציב $m = n \cdot k$ בהגדרה של סדרת GCD, ונקבל שסדרת GCD מקיימת $\gcd( a_n, a_{nk}) = a_{\gcd(n,nk)} = a_n$ , כלומר: המספר $a_n$ מחלק את $a_{nk}$ . בקיצור, $n \mid m \implies a_n \mid a_m$ .

טענת הקסם סוגרת את הפינה החסרה. $\blacksquare$

לפני שנעבור לדוגמאות, נסכם מה קיבלנו: אם סדרת מספרים טבעיים $\{a_n\}_{n \ge 1}$ היא מה שנקרא "סדרת GCD", כלומר $\gcd(a_n, a_m) = a_{\gcd(n,m)}$ , אז המקדמים הבינומים המוכללים המתאימים לסדרה,

$\binom{n}{k}_{a} := \frac{n!_a}{k!_a (n-k)!_a} = \frac{a_n a_{n-1} \cdots a_{n-k+1}}{a_k a_{k-1} \cdots a_1}$

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

אם נתבונן רגע בהגדרה של המקדמים הבינומים המוכללים, נבין שמה שכתוב שם זה: מכפלה של $k$ איברים עוקבים מהסדרה, חלקי מכפלת $k$ האיברים הראשונים בסדרה. כלומר, עבור סדרה שהיא סדרת GCD מתקיים שמכפלה של $k$ איברים עוקבים מהסדרה תמיד מתחלקת במכפלת $k$ האיברים הראשונים בסדרה (בפרט – מכפלה של $k$ מספרים עוקבים תמיד תתחלק ב- $k!$ . בפרט, מכפלה של 2 מספרים עוקבים תהיה זוגית, מכפלה של שלושה מספרים עוקבים תתחלק ב-6 ומכפלה של 4 מספרים עוקבים תתחלק ב-24).

תרגיל 2:
א. הראו שדרישה $(**)$ גוררת ש- $d \mid n \implies a_d \mid a_n$ . (שימו לב שאת דרישה $(**)$ אפשר לנסח בתור: $\forall n,m: \gcd(a_n, a_m) \mid a_{n+m}$ .)
ב. הראו שדרישה $(**)$ לא גוררת ש- $a_n$ סדרת GCD.
ג. הראו שהדרישה שהמקדמים $\binom{n}{k}_{a}$ יהיו שלמים תמיד לא גוררת את דרישה $(**)$ . למעשה, יש דוגמאות מפורשות: $a_n = \binom{n+1}{2} = \frac{(n+1)n}{2}$ ("מספרים משולשיים") מקיימת ש- $\binom{n}{k}_{a}$ שווה $\frac{1}{k+1} \binom{n}{k} \binom{n+1}{k}$ שיוצא תמיד שלם, אבל דרישה $(**)$ לא מתקיימת. באופן כללי, הסדרה $a_n = \binom{n+c-1}{c}$ תעבוד לכל $c$ טבעי.

תרגיל 3: הראו שהדרישה $\forall n,m: \gcd(a_n, a_m) = a_{\gcd(n,m)}$ שקולה לדרישה (הכביכול חלשה יותר) הבאה: $\forall n,m : \gcd(a_n, a_m) = \gcd( a_n, a_{n+m} )$ .

תרגיל 4: נניח שכל המספרים בסדרה $\{a_n\}_{ n \ge1}$ שונים זה מזה. נניח בנוסף שהיא סדרת GCD. הוכיחו כי: $a_n \mid a_m \implies n \mid m$ .

תרגיל 5: תהי $\{ a_n \}_{n \ge 1}$ סדרה של מספרים טבעיים כך ש- $\forall n\neq m: \gcd( a_n, a_m) = \gcd(n,m)$ . הוכיחו כי $\forall n: a_n =n$ .

תרגיל 6:
תהי $\{a_n \}_{n\ge1}$ סדרת GCD.
א. הראו כי $\frac{a_n}{a_{\gcd(n,k)}} \gcd(\binom{n}{k}_{a}, \binom{n-1}{k-1}_{a}) = \binom{n}{k}_{a}$ ו- $\frac{a_{n-k+1}}{a_{\gcd(n+1,k)}} \gcd(\binom{n}{k}_{a}, \binom{n}{k-1}_{a}) = \binom{n}{k}_{a}$ .
מסקנה: $\binom{n}{k}_{a}$ מתחלק ב- $\frac{a_n}{a_{\gcd(n,k)}}$ וגם ב- $\frac{a_{n-k+1}}{a_{\gcd(n+1,k)}}$ .
מסקנה: המקדם הבינומי $\binom{n}{k}$ מתחלק ב- $\frac{n}{\gcd(n,k)}, \frac{n-k+1}{\gcd(n+1,k)}$ .
מסקנה: תחת ההנחה $a_1=1$ , מתקיים שמספר קטלן המוכלל, $C_n = \frac{\binom{2n}{n}_{a}}{a_{n+1}}$ , תמיד שלם.
ב. נניח שבנוסף, $\{a_n \}_{n\ge1}$ סדרה עולה. הראו כי $\gcd( \binom{n}{i}_{a}, \binom{n}{j}_{a})$ תמיד גדול מ-1, בהנחה הטבעית ש- $0<i,j<n$ .

תרגיל 7: תהי $\{a_n\}_{ n \ge1}$ סדרה של טבעיים המקיימת: $d\mid n \implies a_d \mid a_n$ . לכל חזקת ראשוני $p^k$ שמחלקת איזשהו איבר בסדרה, אפשר להסתכל על הקבוצה $A_{p^k} := \{ n: p^k \mid a_n\}$ (אוסף האינדקסים של איברים שמתחלקים בחזקה הנתונה). היא בפרט תכיל את כל הכפולות של האינדקס המינימלי $i$ כך ש- $p^k \mid a_i$ .
הוכיחו ש- $\{a_n\}_{ n \ge1}$ היא סדרת GCD אמ"מ לכל חזקת ראשוני $p^k$ שמחלקת איזשהו איבר בסדרה, הקבוצה $A_{p^k}$ שווה בדיוק לאוסף הכפולות של האינדקס $i$ המינימלי כך ש- $p^k \mid a_i$ .

3. דוגמאות לסדרות GCD

בפרק הקודם ראינו שדרישה מסוימת על סדרות של טבעיים גורמת לכך שאנחנו מקבלים מקדמים בינומים מוכללים מעניינים. נשאלת השאלה – האם יש סדרות מעניינות כאלה? האם יש סדרות GCD מעבר לסדרה הטריוויאלית $a_n =n$ ? התשובה היא "כן" רועם.

דוגמאות מהסוג הראשון – נוסחאות נסיגה לינאריות

א. $a_n =n$ – הדוגמא הסטנדרטית.

ב. $a_n = F_n$ (מספרי פיבונאצ'י). שנייה, מה? למה זה נכון? למה הסדרה המוגדרת ע"י $F_{n+2} = F_{n+1} +F_n, F_1=1,F_2=1$ מקיימת גם $\gcd(F_n, F_m) =F_{\gcd(n,m)}$ ? ובכן, מתרגיל 3 מספיק לבדוק ש- $\gcd(F_n, F_{n+m}) = \gcd(F_m, F_n)$ . נוודא זאת בשני צעדים.

צעד ראשון – המקרה $m=1$ , שבעצם דורש להראות שה-GCD של מספרי פיבונאצ'י עוקבים הוא 1. זה נכון באינדוקציה: $\gcd(F_{n+1},F_n) = \gcd(F_n+F_{n-1},F_n) = \gcd(F_{n-1},F_n)$ .
צעד שני ואחרון – נשתמש בזהות הבאה: $F_{n+m} = F_{n} F_{m+1} + F_{n-1}F_{m}$ (כאשר $m=1$ מקבלים את הרקורסיה של פיבונאצ'י), שאפשר להוכיח אותה במגוון דרכים (אינדוקציה, מהנוסחה המטריציוניות ו/או אלגברית של פיבונאצ'י, וכו'). מהזהות רואים שאם $d \mid F_n, F_m$ אז גם $d \mid F_{n+m}$ – כאן לא היינו צריכים את הצעד הראשון. כן צריך אותו בכיוון השני – אם $d \mid F_{n+m}, F_n$ נובע ש- $d \mid F_{n-1}F_m$ , ומכיוון ש- $\gcd(F_n, F_{n-1}) = 1$ נסיק ש- $d \mid F_m$ . זה מוכיח ש- $\gcd(F_{n+m},F_n) \mid \gcd(F_m,F_n) \mid \gcd(F_{n+m},F_n)$ , ולכן יש שיוויון $\gcd(F_{n+m},F_n) = \gcd(F_m, F_n)$ . $\blacksquare$

ג. $a_n = a^n-1$ , כאשר $a$ הוא מספר שלם (לשם הנוחות – גדול מ-1). שוב, מתרגיל 3, רק צריך לבדוק ש- $\gcd(a^{n+m}-1, a^n-1) = \gcd(a^n-1,a^m-1)$ . הפעם זה נובע מהזהות $a^{n+m} - 1 = a^m(a^n-1) + (a^m-1)$ , שמראה שכל מספר שמחלק את $a^n-1$ ואת $a^m-1$ מחלק גם את $a^{n+m}-1$ , ושכל מספר שמחלק את $a^{n+m}-1,a^n-1$ מחלק גם את $a^m-1$ . $\blacksquare$

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

$a_{n+2} = Aa_{n+1} + Ba_{n}$

עבור מספרי פיבונאצ'י זה ברור מההגדרה ( $A=B=1$ ). עבור הסדרה שלישית זה דורש קצת עבודה – $a_n = a^n-1$ מקיימת $a_{n+1} = a \cdot a_n + a-1$ (סדרת נסיגה לא לינארית מעומק 1) ולכן $a_{n+2}-a_{n+1} = a (a_{n+1} -a_n)$ , כלומר $a_{n+2} =(a+1) a_{n+1} -a \cdot a_n$ , ז"א אפשר לקחת $A=a+1,B=-a$ .
ומה בדבר הדוגמא הראשונה, הפשוטה מכולן? הסדרה $a_n = n$ מקיימת $a_{n+1} = a_n + 1$ , ולכן $a_{n+2} - a_{n+1} = a_{n+1} - a_n$ , כלומר: $a_{n+2} = 2a_{n+1} - a_n$ , ז"א אפשר לקחת $A=2, B=-1$ .

לכן נשמע שאפשר להכליל. אכן אפשר, באופן הבא:

ד. יהיו $A,B$ שני מספרים שלמים זרים (ז"א, עם GCD שווה 1). אם $\{ a_n \}_{n \ge 1}$ סדרת נסיגה הנתונה ע"י $a_{n+2} = A a_{n+1} + Ba_{n}$ ותנאי התחלה $a_2=A\cdot a_1$ אז היא סדרת GCD. הוכחה: ראשית, לשם הנוחות, נניח כי $a_1=1$ (אחרת, נחלק את כל איברי הסדרה הנתונה באיבר הראשון). כעת, נראה באינדוקציה שאיברי הסדרה זרים למספר $B$ (אשאיר זאת לכם). מעכשיו ההוכחה תזכיר את ההוכחות הקודמות – נראה באינדוקציה ישירה ש-GCD של 2 איברים עוקבים הוא 1 (גם את זה אשאיר לכם).
עכשיו מגיע הצעד האחרון, ששוב יסתמך על נוסחה. הנוסחה היא:

$a_{n+m} = a_{n} a_{m+1} + B a_{n-1}a_{m}$

(עבור $m=1$ מקבלים את נוסחת הנסיגה הרגילה.) בעזרת הנוסחה והצעד הקודם מראים שאכן $\gcd(a_{n+m}, a_n) = \gcd(a_n, a_m)$ – אשאיר זאת לכם. אבל איך מוכיחים את הנוסחה? ובכן, כרגיל – יש מגוון דרכים. אינדוקציה תעבוד, אבל אפשר להשתמש בנוסחה המפורשת ל- $a_n$ , שהיא: $a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ כאשר $\alpha,\beta$ שורשי המשוואה $x^2=Ax+B$ . (כאשר השורשים מתלכדים נוסחה זו לא מוגדרת היטב, צריך להשתמש ב- $a_n = n \alpha^{n-1}$ .) $\blacksquare$

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

כמו כן, גם הטענה הבאה נכונה תמיד: אם האיבר הראשון בסדרת ה-GCD הוא 1 אז GCD של איברים עוקבים בסדרה יהיה 1, כי $\gcd(a_n, a_{n+1}) = a_{\gcd(n,n+1)} = a_1=1$ .

הערה: הסדרה השנייה שראינו, $a^n-1$ , עלולה להיות מוכרת לחלקכם מעולם הפולינומים. ספציפית, סדרת הפולינומים $a_n = x^n-1 \in \mathbb{Q}[x]$ היא סדרה שמקיימת את התכונה $\gcd(a_n,a_m) = a_{\gcd(n,m)}$ כאשר זה GCD של פולינומים ולא של שלמים. גם על סדרת פיבונאצ'י אפשר לחשוב בתור סדרת GCD של פולינומים שהציבו בה איבר – הסדרה היא $a_{n+2} = xa_{n+1} +a_n, a_1=1,a_2=x$ (פולינומי פיבונאצ'י), ואם מציבים $x=1$ נקבל את מספרי פיבונאצ'י. לפעמים, אך לא תמיד, נוכל לקבל סדרת GCD של מספרים מתוך סדרת GCD של פולינומים ע"י הצבה $x= \text{some integer}$ . כמעט לא נתעמק בנושא זה בפוסט מעבר להערה זו.

הערה: הרבה פעמים עובדים עם הסדרה $a_n = \frac{q^n-1}{q-1}$ כאשר $q$ מציין לרוב חזקת ראשוני. היא קרובה מאוד לסדרה השנייה שראינו. המקדמים הבינומים המתאימים נקראים "מקדמים $q$ -נומים", וכאשר $q \to 1$ מקבלים את המקדמים הבינומים הרגילים. הרבה זהויות קומבינטוריות עם מקדמים בינומים רגילים ניתן להכליל לזהויות עם מקדמים $q$ -נומים, כאשר האינטרפרטציה הקומבינטורית מוחלפת באינטרפרטציה אלגברית.

דוגמאות מהסוג השני – רקורסיביות

הנה שתי דוגמאות לא טריוויאליות לסדרות GCD, שמתנהגות שונה לחלוטין מהדוגמאות הנ"ל:

תרגיל 8: יהי $f$ פולינום עם מקדמים שלמים. אזי סדרה שמוגדרת באופן רקורסיבי ע"י $a_{n+1} = f(a_n)$ עם תנאי התחלה $a_1=f(0)$ היא סדרת GCD.
הערה: שימו לב שדוגמאות א' ו-ג' מהסוג הראשון מוכלות בתרגיל 6.

תרגיל 9: תהי $\{ a_n \}_{n\ge 1}$ שמוגדרת באופן הרקורסיבי הבא: $a_1=1, a_{n+1} = \lfloor e (a_n!) \rfloor$ . הראו שהיא סדרת GCD.

4. יצירת סדרות GCD חדשות מישנות

יש לא מעט דרכים ליצר סדרות GCD חדשות מתוך קיימות. הנה כמה כאלו:

כפל בסקלר: אם $\{ a_n \}_{n\ge 1}$ סדרת GCD אז גם $\{ k\cdot a_n \}_{n \ge 1}$ סדרת GCD לכל $k \in \mathbb{N}$ . (תרגיל!)
העלאה בחזקה: אם $\{ a_n \}_{n\ge 1}$ סדרת GCD אז גם $\{ a_n^k \}_{n \ge 1}$ סדרת GCD לכל $k \in \mathbb{N}$ . (תרגיל!)
הרכבה: אם $\{a_n \}_{n \ge 1}, \{b_n\}_{n \ge 1}$ שתי סדרות GCD אז $\{ a_{b_n} \}_{n \ge 1}$ היא גם סדרת GCD. (תרגיל!)

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

הכפלה (תחת אילוצים): אם $\{a_n \}_{n \ge 1}, \{b_n\}_{n \ge 1}$ הן שתי סדרות GCD כך שקבוצת המחלקים הראשוניים של $\{ a_n \}_{n\ge 1}$ וקבוצת המחלקים הראשוניים של $\{b_n \}_{n \ge 1}$ הן קבוצות זרות, אז $\{ a_n \cdot b_n \}_{n \ge 1}$ היא גם סדרת GCD.

תרגיל 10: הראו שללא האילוץ שהוספנו, מכפלה איבר-איבר של שתי סדרות GCD לאו דווקא יוצאת סדרת GCD.

כעת, מרמור: סדרות GCD לא סגורות לכפל איבר-איבר, אבל הן באות לעזור לנו להוכיח תכונה שכן סגורה לכפל – התכונה שהמקדמים הבינומים $\binom{n}{k}_{a}$ יוצאים שלמים. הרי אם $\{ a_n \}_{n \ge 1}, \{b_n\}_{n \ge 1}$ הן שתי סדרות כך שהמקדמים הבינומים שלהן יוצאים שלמים, אז גם המקדמים הבינומים של $\{ a_n \cdot b_n \}_{n \ge 1}$ יוצאים שלמים. זה מתסכל, מוזר, ומחשיד. מסתבר שתכונת ה-GCD היא לא התכונה הנכונה להסתכל עליה! בפרק הבא נבין מהי התכונה הנכונה.

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

דוגמא: דוגמא זו שונה קצת מהדוגמאות הקודמות, ונעבוד עם פולינומים מעל שדה סופי במקום עם מספרים. אם $p$ הוא מספר ראשוני אז הסדרה $a_n = x^{p^{n}}-x \mod p$ (פולינומים ב- $\mathbb{F}_{p}[x]$ ) היא הרכבה של 2 סדרות GCD, ספציפית – $x^{n+1}-x$ (סדרה של פולינומים) ו- $p^n-1$ (סדרה של מספרים). ההרכבה הזו היא פולינום ששדה הפיצול שלו הוא $\mathbb{F}_{p^n}$ (זו הדרך הכי קלה להראות קיום ויחידות של שדה זה!), ואפשר להראות (לא מיידי) שהיא שווה למכפלת כל הפולינומים המתוקנים ב- $\mathbb{F}_{p}[x]$ ממעלה המחלקת את $n$ . בהמשך נראה איך אפשר לעשות פעולות אלגבריות על מכפלה זו בכדי לקבל את מכפלת כל הפולינומים המתוקנים ב- $\mathbb{F}_{p}[x]$ ממעלה בדיוק $n$ .

5. החלק הפרימיטיבי של סדרת GCD

נתחיל בלדבר על מושג שמסתבר שהוא יותר חלש מסדרת GCD.
סדרה $\{a_n \}_{n \ge 1}$ של מספרים טבעיים תיקרא "סדרה מתפרקת", אם קיימת סדרה $\{ b_n\}_{n\ge 1}$ של מספרים טבעיים כך ש- $\forall n: a_n = \prod_{d \mid n} b_d$ . לסדרה $\{b_n\}_{n\ge 1}$ נקרא "החלק הפרימיטיבי של $\{ a_n\}_{n\ge 1}$ ".

למה סדרות מתפרקות הן סדרות מעניינות? ראשית, קל לראות שהן מקיימות את התכונה $n \mid m \implies a_n \mid a_m$ , שראינו שהיא שימושית ומתקיימת ע"י סדרות GCD. בנוסף, ואולי מעט מפתיע – המקדמים הבינומים שלהן שלמים, על אף שהן לא בהכרח סדרות GCD! ההוכחה לכך לא תוכל להסתמך על "זהות פסקל" מפרק 2, אבל למעשה תהיה פשוטה יותר:

טענה: תהי $\{a_n \}_{n \ge 1}$ סדרת מתפרקת עם חלק פרימיטיבי $\{ b_n\}_{n\ge 1}$ . מתקיים שהמקדמים הבינומים $\binom{n}{k}_{a}$ תמיד שלמים. הוכחה: נציב את השיוויון $a_n = \prod_{d \mid n} b_d$ בהגדרה של המקדמים הבינומים, ונקבל:

$\binom{n}{k}_{a} = \frac{\prod_{i=1}^n \prod_{d \mid i} b_d}{\prod_{i=1}^{n-k} \prod_{d \mid i} b_d \prod_{i=1}^{k} \prod_{d \mid i} b_d}$

במונה ובמכנה מופיעים מכפלות של $b_d$ -ים. נראה שלכל $d$ , כמות ה- $b_d$ -ים במונה היא לפחות כמו במכנה.
כמה פעמים $b_d$ ספציפי מופיע במכנה? ככמות המספרים ב- $\{1,2,\cdots,k\}$ וב- $\{ 1,2,\cdots ,n-k\}$ שמתחלקים ב- $d$ , כלומר: $\lfloor \frac{k}{d} \rfloor + \lfloor \frac{n-k}{d} \rfloor$ . ובמונה? $\lfloor \frac{n}{d} \rfloor$ . לפי תרגיל 1, מתקיים שאכן במונה יש לפחות אותה כמות $b_d$ -ים כמו במכנה, ומכאן נובע שהמקדמים שלמים. $\blacksquare$

בנוסף, הן סגורות לכפל איבר-איבר, שזה דבר נהדר.
נשאלת השאלה: מה הקשר בין סדרות מתפרקות לסדרות GCD? ובכן, כל סדרת GCD היא סדרה מתפרקת – אבל לא להיפך.

טענה: תהי $\{ a_n\}_{n\ge 1}$ סדרת GCD. קיימת סדרה $\{ b_n \}_{n \ge 1}$ יחידה של מספרים טבעיים, כך ש- $a_n = \prod_{d \mid n} b_d$ לכל $n$ .
הוכחה: נתחיל ביחידות – נניח שאנחנו רוצים למצוא $\{b_n \}_{n\ge 1}$ כזו. ע"י הצבה של $n=1$ מקבלים $b_1 = a_1$ , ובהינתן $b_1,b_2, \cdots, b_{n-1}$ אפשר לחשב את $b_n$ ע"י $b_n = \frac{a_n}{\prod_{d \mid n, d\neq n} b_d}$ . זה מראה שהסדרה יחידה, נותר לוודא שהיא סדרה של מספרים שלמים (תרגיל).

יש כמה דרכים להראות שלמות, אבל כולן משתמשות בתרגיל 7, שאומר משהו עמוק על הפירוק לראשוניים של סדרות GCD.
אינדוקציה תעבוד, אבל רק אם נוכיח באינדוקציה משהו חזק יותר, ספציפית: $\prod_{d \mid n, d \neq n} b_d = \text{lcm}_{d \mid n, d \neq n} a_d$ . אחרי שתוכיחו זאת (לא טריוויאלי), ינבע ש-

$b_n = \frac{a_n}{\prod_{d \mid n, d\neq n} b_d} =\gcd_{d \mid n, d \neq n} \frac{a_n}{a_d} \in \mathbb{Z}$

זו לא באמת הייתה הוכחה מלאה. כעת אתן 2 הוכחות נוספות, "טובות" יותר, כי הן יתנו יותר מידע. ההוכחה הראשונה תתבסס על זה שאפשר לתת נוסחה מפורשת ל- $b_n$ , שממנה ינבע שהמספר שלם. בשביל זה נגדיר מושג חדש:

נאמר שלאיבר ה- $n$ -י של הסדרה המקורית, $a_n$ , יש "קפיצה של $p^k$ ", אם החזקה של $p$ המופיעה ב- $a_n$ גבוהה ב- $k$ בדיוק מהחזקה המקסימלית של $p$ המופיעה בכל המספרים הקודמים, $\{ a_i \}_{i<n}$ . דוגמא: אם $a_3$ מתחלק ב- $p^3$ אבל $a_2$ מתחלק ב- $p$ ו- $a_1$ לא מתחלק ב- $p$ בכלל, אז נאמר של- $a_3$ יש קפיצה ב- $p^2$ .
מה הנוסחה ל- $b_n$ ? מכפלת כל הקפיצות של $a_n$ ! אם נוכיח זאת, ינבע מייד ש- $b_n$ שלם.
(זה גם מסביר חלקית את השם "חלק פרימיטיבי" – אם ל- $b_n$ יש קפיצה ב- $p$ , אז $a_n$ זה האיבר הראשון בסדרה שמתחלק ב- $p$ , ובמקרה כזה באמת נהוג לקרוא ל- $p$ "גורם פרימיטיבי של $a_n$ ".)
אשאיר את ההוכחה לכם – בהינתן הניחוש ותרגיל 7 זה תרגיל סביר.

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

היפוך מביוס זה שם לטריק שמאפשר לקבל מהמשוואות $\forall n: a_n = \prod_{d \mid n} b_d$ ישר את הנוסחה ל- $b_n$ , ע"י הכלה-הדחה (כפל וחלוקה של משוואות מתאימות). ספציפית, הנוסחה שמתקבלת היא:

$\forall n: b_n = \prod_{d \mid n} a_d^{\mu(n/d)}$

כאשר $\mu$ היא פונקצית מביוס. במקום לתת לכם את הנוסחה לפונקציית מביוס, אגיד להם מה הפונקציה צריכה לקיים. אם נציב את הנוסחה הנ"ל במשוואות $a_n = \prod_{d \mid n} b_d$ , מקבלים שהפונקציה צריכה לקיים את התכונה הבאה, שאקרא לה "התכונה היסודית של מביוס":

$\sum_{d \mid n} \mu(d) = 1_{n=1}$

כלומר $\mu(1)=1$ (כדי שתמיד $a_n$ יופיע ב- $b_n$ עם חזקה 1), ו- $\sum_{d \mid n} \mu(d) = 0$ לכל $n>1$ . אנחנו לא צריכים את הנוסחה המפורשת למביוס, אלא רק את הידיעה שאת אוסף האילוצים הזו מקיימת פונקציה שמקבלת ערכים שלמים.

כדי להראות ש- $b_n$ שלם, מספיק להראות שכל ראשוני שמחלק את $b_n$ מופיע מספר אי-שלילי של פעמים בנוסחה. כלומר, $v_p(b_n) \ge 0$ כאשר $v_p$ הפונקציה שסופרת כמה פעמים מספר נתון מתחלק ב- $p$ .

נסמן ב- $c_i$ את האינדקס של האיבר הראשון בסדרה שמתחלק ב- $p^i$ . כמה פעמים איבר כללי $a_n$ מתחלק ב- $p$ ? בדיוק $\sum_{i \ge 1} 1_{c_i \mid n}$ (כאן השתמשתי בתרגיל 7). כמה פעמים $b_n$ מתחלק ב- $p$ ?

$v_p(b_n) = \sum_{d \mid n} v_p(a_{\frac{n}{d}}) \mu(d) = \sum_{d \mid n} (\sum_{i \ge 1} 1_{c_i \mid n/d}) \mu(d) = \sum_{i \ge 1} (\sum_{d \mid n} 1_{c_i \mid n/d} \mu(d)) =\sum_{i\ge 1\text{ such that }c_i \mid n} \sum_{d \mid \frac{n}{c_i}} \mu(d) = \sum_{i\text{ such that }c_i \mid n} 1_{\frac{n}{c_i}=1} = \sum_{i \ge 1} 1_{c_i =n}$

וסכום זה בטוח אי-שלילי (השתמשנו בדרך בתכונה היסודית של פונקציית מביוס).
אם נסמן סכום זה ב- $s$ , נשים לב של- $a_n$ יש קפיצה של $p^s$ , כמו שהזכרנו בהוכחה הקודמת. $\blacksquare$

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

אז כל סדרת GCD היא סדרה מתפרקת. בפרט, כל סדרה מפרק 3 היא סדרה מתפרקת. בואו נמצא את הפירוק הזה:

פירוק דוגמא א': נסתכל על סדרת ה-GCD הטריוויאלית, $a_n=n$ . איך נראה הפירוק שלה? כל אחת מההוכחות של הטענה האחרונה מאפשרת להגיע לנוסחה של החלק הפרימטיבי שלה. הוא יוצא:

$b_n = \begin{cases} p & n=p^k \\ 1 & n\neq p^k \end{cases}$

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

אגב, חלקכם יכירו את הפירוק הזה מתורת המספרים האנליטית, שם גרסה חיבורית שלו ידועה בתור הזהות $\ln n = (\Lambda * 1)(n)$ כאשר $\Lambda$ היא פונקציית Von Mangoldt, ו- $*$ זו קונבולוציית דיריכלה.

פירוק דוגמא ג': נסתכל על הסדרה $a_n =a^n-1$ כאשר $a$ מספר טבעי גדול מ-1. למי שמכיר פולינומים ציקלוטומים, ברור מהו החלק הפרימיטיבי של $a_n$ : הוא $b_n= \Phi_n(a)$ , כאשר $\Phi_n$ הוא הפולינום הציקלוטומי ה- $n$ . למי שלא זוכר, זה הפולינום המתוקן ששורשיו הם בדיוק שורשי היחידה הפרימיטיביים מסדר $n$ , כלומר $\Phi_n(x) := \prod_{1 \le i \le n, \gcd(i,n) = 1} (x-\omega_n^i), \omega_n:=e^{2\pi i/n}$ .

פירוק דוגמא ב': אנחנו מוכנים למספרי פיבונאצ'י. ראינו שמספרי פיבונאצ'י $F_n$ הם סדרת GCD. אם נשתמש בנוסחה $F_n = \frac{\phi^n - \overline{\phi}^n}{\phi-\overline{\phi}}$ , כאשר $\phi, \overline{\phi}$ שורשי המשוואה $x^2=x+1$ . הנוסחה עם היפוך מביוס מאפשרת לנו לקבל ביטוי לחלק הפרימיטיבי של סדרת פיבונאצ'י, שדומה לביטוי מהדוגמא הקודמת. אפשר להביעו בצורה הבאה: $b_n = \prod_{1\le i \le n, \gcd(i,n)=1} (\phi-\omega_n^i \overline{\phi})$ לכל $n>1$ , ועבור $n=1$ פשוט $b_1=1$ .
הפולינומים $\Phi_n(x,y) = \prod_{1\le i \le n, \gcd(i,n)=1} (x-\omega_n y)$ ידועים בתור "הפולינומים הציקלוטומים ההומוגנים".

דוגמא אחרונה היא זו:

פירוק הדוגמא המוזרה מפרק 4: הסדרה $x^{p^n}-x \mod p$ היא סדרת GCD של פולינומים ששווה למכפלת כל הפולינומים האי-פריקים ממעלה המחלקת את $n$ . קל לראות שהחלק הפרימיטיבי שלה שווה למכפלת כל הפולינומים האי-פריקים ממעלה בדיוק $n$ , ושהנוסחה יוצאת $\prod_{d \mid n} (x^{p^d}-x)^{\mu(n/d)}$ . המעלה של היצור הזה היא $\sum_{d \mid n} p^d \mu(n/d)$ . אם נחלק ב- $n$ , נקבל את מספר הפולינומים האי-פריקים ממעלה $n$ ב- $\mathbb{F}_{p}[x]$ . מגניב… ואפשר לקבל עוד עובדות מעניינות אם נתאמץ.

תרגיל 11: הכלילו את תרגיל 6 למקרה ש- $\{ a_n \}_{n \ge 1}$ סדרה מתפרקת (יתכן שצריך לעשות שינויים קלים). למעשה, אפשר להכליל אותו למקרה כללי יותר – תרגיל 6 נכון, תחת שינויים קלים, אם ההנחה היחידה היא שהמקדמים הבינומים של הסדרה הטבעית $\{ a_n \}_{n \ge 1}$ יוצאים שלמים.

תרגיל 12: יהיו $p,q$ שני מספרים ראשוניים שונים. הראו שאם $\{ a_n \}_{n \ge 1}$ סדרת GCD אז הסדרה $\{ b_n=\frac{a_{np} a_{nq}}{a_n}\}_{n\ge 1}$ מקיימת $d \mid n \implies b_d \mid b_n$ .

6. בסיס לסדרות GCD

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

$g^{(N,b)}_n = \begin{cases} b & N \mid n \\ 1 & N \nmid n \end{cases}$

כאשר $b,N$ הם פרמטרים טבעיים (הסדרה הקבועה מתקבלת ע"י $b=1$ ).

אפשר לוודא בנקל שזו תמיד סדרת GCD. נקרא לסדרות מהסוג הזה "סדרות בסיסיות". כעת נסתכל על מכפלות שלהן.
אם $\{ a_n \}_{n \ge 1}$ סדרת GCD, עם חלק פרימיטיבי $\{ b_n \}_{n \ge 1}$ , מתקיים (ישירות מההגדרה) ש- $\forall n: a_n= \prod_{N \ge 1} g^{(N,b_N)}_n$ . כלומר, $a_n$ היא מכפלה של סדרות בסיסיות. המכפלה עצמה אינסופית, אך כל חישוב דורש מספר סופי של הכפלות.
בנוסף, כל מכפלה מהצורה $\prod_{N \ge 1} g^{(N,b_N)}$ נותנת סדרה שונה של מספרים טבעיים (שוב, המכפלה עצמה אינסופית אך בכל חישוב כמעט כל המספרים הם 1). אין סדרה שמתקבלת פעמיים.

נשאלת השאלה: מה התנאים על $\{b_N \}_{N \ge1}$ כך שהמכפלה $\prod_{N \ge 1} g^{(N,b_N)}$ תצא סדרת GCD? באופן שקול – איזה אילוצים מקיימות סדרות פרימיטיביות (=החלקים הפרימיטיבים של סדרות GCD)? התרגיל הבא עונה על כך:

תרגיל 13: התנאי הוא שאם $m,n$ זוג מספרים שאף אחד מהם לא מחלק את האחר, אז $\gcd(b_n, b_m)=1$ . תנאי זה מספיק והכרחי.

נובע מהתרגיל: יש התאמה חח"ע ועל בין סדרות GCD לסדרות של טבעיים $\{ b_n\}_{n\ge 1}$ המקיימות $n \nmid m \wedge m \nmid n \implies \gcd(b_n,b_m)=1$ . סדרות אלו, כמו שנאמר קודם, הן בדיוק החלק הפרימיטיבי של סדרות ה-GCD. המעבר מסדרת GCD לחלק הפרימיטיבי נעשה ע"י היפוך מביוס כפלי, ומהמעבר מהחלק פרימיטיבי חזרה לסדרת GCD הוא ע"י $\forall n: a_n= \prod_{N \ge 1} g^{(N,b_N)}_n$ .

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

7. הקשר למשפט זיגמונדי וקרמייקל

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

בהינתן סדרה $\{a_n \}_{n \ge 1}$ של מספרים טבעיים, אפשר להתעניין בגורמים הראשונים של איבריה. שאלה שצצה לפעמים היא זו: האם ל- $a_n$ יש גורם ראשוני שאין לאף אחד מהאיברים שלפניו, $\{a_i\}_{i<n}$ ? אם יש כזה גורם ראשוני, נקרא לו "גורם ראשוני פרימיטיבי של הסדרה".
אם לכל $n$ התשובה על השאלה הזו חיובית החל מאיזשהו $n$ , אנחנו בעצם מקבלים שלסדרה $\{ a_n \}_{n \ge 1}$ יש אינסוף מחלקים ראשוניים שונים, וזו עוד הוכחה לאינסופיות הראשוניים. (אם כי מסורבלת מעט.)

ב-1886 הוכיח מתמטיקאי בשם Bang שלסדרה $a_n=2^n-1$ כמעט תמיד יש גורם ראשוני פרימיטיבי (יוצאי הדופן הם $n=1,6$ ). אם נפרש זאת בשפה של תורת החבורות, זה אומר שעבור $n \neq 1,6$ קיים ראשוני $p$ כך שהסדר של $2$ בחבורה הכפלית של המספרים מודולו $p$ הוא בדיוק $n$ .
ב-1892 הוכיח מתמטיקאי בשם Zsigmondy שלסדרה $a_n=a^n-b^n$ כמעט תמיד יש גורם ראשוני פרימיטיבי (אפשר לקרוא על יוצאי הדופן כאן).
ב-1913 הוכיח מתמטיקאי בשם Carmichael שלהרבה סדרות נסיגה מסדר 2 (דוגמא ד' מפרק 3) יש גורם ראשוני פרימיטיבי אם $n>12$ . סדרת פיבונאצ'י כלולה בין סדרות אלו.
ב-2002 הוכיחו שלושה מתמטיקאים שהתוצאה של Carmichael נכונה לכל סדרה מהסוג שנמצא בדוגמא ד' בפרק 3, בהנחה ש- $n>30$ . (תוצאה דומה הייתה ידועה קודם, פריצת הדרך הייתה להראות שהחסם לא תלוי בסדרה ואפשר לקחת אותו להיות 30, "קבוע אבסולוטי").

אוקיי, איך מוכיחים דבר כזה? כל ההוכחות מתחילות בהבחנה הבאה:

הבחנה: אם $\{a_n \}_{n\ge1}$ היא סדרת GCD, אז $p$ הוא גורם ראשוני פרימיטיבי שלה אמ"מ הוא גורם ראשוני פרימיטיבי של החלק הפרימיטיבי שלה, $\{b_n\}_{n \ge 1}$ .

בהינתן ההבחנה, ההוכחה הולכת כך (תיאור לא פורמלי):

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

נדגים זאת עבור $a_n = a^n-1, a>2$ . שאר המקרים לא שונים מהותית.

המחלקים האפשריים של $b_n$ , לא כולל גורמים פרימיטיבים, הם רק גורמים של $n$ , והם יופיעו בריבוי 1 לכל היותר (קשור למה שידוע בתור "Exponent Lifting"). למעשה, עם קצת מאמץ, אפשר להראות שמלבד גורמים פרימטיביים, יש בדיוק 2 אפשרויות: הגורם הטריוויאלי 1, או הגורם הראשוני הכי גדול של $n$ בריבוי 1.
אם נסמן ב- $q$ את הגורם הראשוני הכי גדול של $n$ , אפשר להראות: $b_n \ge a^{q-2}$ .
נניח בשלילה שאין ל- $b_n$ גורם ראשוני פרימיטיבי. אז משתי הטענות הנ"ל נקבל ש- $q \ge b_n \ge a^{q-2}$ . נובע: או ש- $q=2$ או $q=3,a\le 3$ . צריך לבדוק מקרים אלו פרטנית.

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

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

הגורמים שמחלקים את $b_n$ , מלבד גורמים ראשוניים פרימיטיבים, הם מחלקים של $n$ , והריבוי שלהם הוא לכל היותר 1. (זאת בהנחה ש- $n \neq 2,6$ .)
מתקיים ש- $b_n > \frac{2}{5} (1.5)^{\phi(n)}$ .
אם נניח בשלילה שאין ל- $b_n$ גורם ראשוני פרימיטיבי, אז משתי הטענות הנ"ל נקבל ש- $\prod_{p \mid n} p \ge b_n > \frac{2}{5} (1.5)^{\phi(n)}$ לכל $n \neq 2,6$ . יש רק מספר מועט של מקרים בהם אי-שיוויון זה יכול להתקיים, וצריך לבדוק אותם פרטנית.

גם על הוכחה זו אפשר לקרוא במסמך הזה (עמוד אחרון).

8. דברי סיום

אפשר לסכם את רוב מה שעשינו בדיאגרמה הבאה:

בפרק 2 ראינו שבעצם יש עוד מחלקה – אוסף הסדרות $\{ a_n \}_{n \ge 1}$ כך ש- $\gcd(a_n, a_m) \mid a_{n+m}$ . מה מיקומה בדיאגרמה? בדיוק המקום של הסדרות המתפרקות (שורה 3) – היא מוכלת בשתי הקבוצות התחתונות ומכילה את סדרות ה-GCD. עם זאת, היא לא מוכלת ולא מכילה את כל הסדרות המתפרקות. היא גם לא סגורה לכפל איבר-איבר.

תרגיל 14 (שאלה פתוחה): אילו עוד תנאים חלשים יותר מסדרות GCD אפשר לייצר כך שהמקדמים הבינומים המתאימים יצאו שלמים? כרגע יש שניים: סדרות מתפרקות, וסדרות המקיימות $\gcd(a_n, a_m) \mid a_{n+m}$ .
אשמח לשמוע עוד הצעות!

לגבי טרמינולוגיה: חלק מהטרמינולוגיה כאן לא סטנדרטית. בגדול, לסדרת GCD קוראים לרוב "Strong Divisibility Sequence", אך נתקלתי גם במונחים "GCD Sequence" ו-"GCD-morphic Sequence". לסדרה המקיימת $d \mid n \implies a_d \mid a_n$ קוראים "Divisibility Sequence". לחלק הפרימיטיבי של סדרת GCD אכן קוראים "Primitive Part".

לגבי ביבליוגרפיה: יש כמה חבר'ה שחקרו את הנושא ורוב התוצאות שהוכחתי לקוחות ממאמרים שלהם. מדובר ב-Morgan Ward, H. W. Gould ו-M. Dziemiańczuk, W. Bajguz. רוב התרגילים נלקחו מפורומים שעוסקים באוליפיאדות מתמטיות.

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

שבת שלום,
אופיר