נוסחת לז'נדר

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

$n!=\prod _{p\le n}{p}^a,a=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$

כאשר $p$ מספר ראשוני ו-$\lfloor x\rfloor$ היא פונקציית הערך השלם (עיגול כלפי מטה).

בניסוח שקול, הנוסחה קובעת שהמעריך של החזקה הגבוהה ביותר של ראשוני $p$ המחלקת את $n!$ הוא $\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$. הסכום האינסופי לכאורה הוא למעשה סכום סופי, שכן החל משלב מסוים כל איברי הסכום מתאפסים משום של-$p^k>n$ מתקיים $\lfloor \frac{n}{p^k}\rfloor =0$.

הוכחה

"$n$ עצרת" הוא מכפלת המספרים מ-1 עד $n$:

$n!=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1$

לכן המעריך של החזקה הגבוהה ביותר של ראשוני $p$ המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של $p$ המחלקות כל אחד מהמספרים מ-1 עד $n$.

לכל ראשוני $p$, אנחנו יודעים כי $p$ מחלק בדיוק $\lfloor \frac{n}{p}\rfloor$ מספרים מ-1 עד $n$ שכן כפולותיו הן $p,2p,3p,\dots ,\lfloor \frac{n}{p}\rfloor p$.

ביניהם $\lfloor \frac{n}{p^2}\rfloor$ מספרים שמתחלקים אפילו ב-$p^2$, ולכן יש לספור אותם פעם נוספת.

ובאופן כללי, יש ביניהם בדיוק $\lfloor \frac{n}{p^k}\rfloor$ המתחלקים ב-$p^k$, ויש לספור אותם שוב. נסכום את כל המקרים יחדיו ונקבל שהמעריך של החזקה הגבוהה ביותר של $p$ המחלקת את $n!$ הוא $V_p(n!)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$.

דוגמה

נמצא כמה אפסים מופיעים בסוף הכתיב העשרוני של המספר $199!$. מספר האפסים שווה למעריך של החזקה הגבוהה ביותר של 10 המחלקת את $199!$. הפירוק לגורמים של חזקות של 10 הוא $10^m=2^m\cdot 5^m$. לכן המעריך המבוקש יהיה הקטן מבין המעריכים של החזקות הגבוהות ביותר של הראשוניים 2 ו-5 המחלקות את $199!$. ברור כי המעריך הגבוה יותר מבין השניים הוא זה של 2 (שכן הוא מחלק יותר מספרים בין 1 ל-199) ולכן מספיק למצוא את המעריך של 5. לפי הנוסחה המעריך הוא:

$\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{199}{5^k}\rfloor =39+7+1+0+0+\cdots =47$

מכאן שהמספר $199!$ מסתיים ב-47 אפסים.

ניסוח שקול

נסמן ב-$S_p(n)$ את סכום הספרות של $n$ בבסיס $p$. ניסוח שקול לנוסחת לז'נדר קובע שהמעריך של החזקה הגבוהה ביותר של $p$ המחלקת את $n!$ הוא $\frac{n-S_p(n)}{p-1}$.

הוכחה

נציג את $n$ בבסיס $p$:

$n=a_r{p}^r+a_{r-1}{p}^{r-1}+\cdots +a_{1}p+a_0;a_r,\dots ,a_0<p$

כעת נשים לב כי

$\lfloor \frac{n}{p^k}\rfloor =\lfloor \frac{a_r{p}^r+\cdots +a_0}{p^k}\rfloor =\lfloor a_r{p}^{r-k}+\cdots +a_k+a_{k-1}{p}^{-1}+\cdots +a_0{p}^{-k}\rfloor =a_r{p}^{r-k}+\cdots +a_k$

זאת מכיוון ש-$a_{k-1}{p}^{-1}+\cdots +a_0{p}^{-k}<1$. מכאן לפי נוסחת לז'נדר המעריך של חזקה הגבוהה ביותר של $p$ המחלקת את $n!$ הוא:

$\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor =\sum _{k=1}^{\mathrm{\infty }}(a_r{p}^{r-k}+\cdots +a_k)=$

נבחין כי בטור האחרון לכל $1\le i\le r$, המקדם $a_i$ מופיע פעם אחת בדיוק כמקדם של כל אחד מבין $1,p,\dots ,p^{i-1}$. לכן נוכל לסדר מחדש את הטור האחרון בצורה:

$=\sum _{i=1}^r{a}_i(1+p+\cdots +p^{i-1})=\sum _{i=1}^r{a}_i\frac{p^i-1}{p-1}=\frac{1}{p-1}(\sum _{i=1}^r{a}_i{p}^i-\sum _{i=1}^r{a}_i)=\frac{(n-a_0)-(S_p(n)-a_0)}{p-1}=\frac{n-S_p(n)}{p-1}$

במעבר הראשון עשינו שימוש בנוסחה לסכום טור הנדסי.

שימושים

מקדם בינומי $(\genfrac{}{}{0ex}{}{n}{r})=\frac{n!}{r!(n-r)!}$ שווה למספר התת-קבוצות מגודל $r$ שיש לקבוצה בגודל $n$. מכאן שהוא בהכרח מספר שלם. עם זאת, זוהי הוכחה קומבינטורית לטענה, ואילו נוסחת לז'נדר מספקת הוכחה אלמנטרית לטענה (כזו המסתמכת רק על תכונות מספרים).

פונקציית הערך השלם מקיימת את האי-שוויון הטריוויאלי $\lfloor a\rfloor +\lfloor b\rfloor \le \lfloor a+b\rfloor$. לכן מתקיים:

$\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{r}{p^k}\rfloor +\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n-r}{p^k}\rfloor \le \sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$

לפי נוסחת לז'נדר אגף ימין הוא המעריך של החזקה הגבוהה ביותר של $p$ המחלקת את $n!$, בעוד אגף שמאל הוא המעריך של החזקה הגבוהה ביותר של $p$ המחלקת את $r!(n-r)!$. מהאי-שוויון אנו מסיקים שלכל חזקת ראשוני בפירוק של $r!(n-r)!$ לגורמים, כפולה שלו מופיעה בפירוק של $n!$, ולכן $n!$ מתחלק ב-$r!(n-r)!$, כלומר $(\genfrac{}{}{0ex}{}{n}{r})=\frac{n!}{r!(n-r)!}$ מספר שלם.

לפי נוסחת לז'נדר המעריך של החזקה הגבוהה ביותר של $p$ המחלקת את $(\genfrac{}{}{0ex}{}{2n}{n})$ הוא $\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$, עובדה המשמשת בהוכחה האלמנטרית של פאול ארדש להשערת ברטראן.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

נוסחת לז'נדר38199520Q23041626