נוסחת לז'נדר

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

$n!=\prod _{p\leq n}{p^{\sum _{k=1}^{\infty }{\lfloor {n/p^{k}}\rfloor }}}$

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

הנוסחה נקראת על שם אדריאן-מארי לז'נדר שהיה הראשון לחקור אותה.

הוכחה

$n!$ (עצרת) הוא מכפלת המספרים מ-1 עד n ($n!=n(n-1)(n-2)\dots (n-(n-2))(n-(n-1))=n\cdot (n-1)\dots 2\cdot 1$). לכן המעריך של החזקה הגבוהה ביותר של ראשוני $p$ המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של p המחלקות כל אחד מהמספרים מ-1 עד n.

לכל ראשוני $p$, אנחנו יודעים כי $p$ מחלק בדיוק $\left\lfloor {\tfrac {n}{p}}\right\rfloor$ מספרים מ-1 עד n שכן כפולותיו הן: $p,2p,3p,\ldots ,(\left\lfloor {\tfrac {n}{p}}\right\rfloor p)$.

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

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

דוגמה

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

$\sum _{k=1}^{\infty }\left\lfloor {\frac {199}{5^{k}}}\right\rfloor =39+7+1+0+0+\ldots =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}+\ldots +a_{1}p+a_{0}\quad ;\quad a_{r},\ldots ,a_{0}<p$

כעת נשים לב כי:

$\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\left\lfloor {\frac {a_{r}p^{r}+\ldots +a_{0}}{p^{k}}}\right\rfloor =\left\lfloor a_{r}p^{r-k}+\ldots +a_{k}+a_{k-1}p^{-1}\ldots +a_{0}p^{-k}\right\rfloor =a_{r}p^{r-k}+\ldots +a_{k}$

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

$\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\sum _{k=1}^{\infty }(a_{r}p^{r-k}+\ldots +a_{k})=$

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

$=\sum _{i=1}^{r}{a_{i}(1+p+\ldots +p^{i-1})}=\sum _{i=1}^{r}{a_{i}\left({\frac {p^{i}-1}{p-1}}\right)}={\frac {1}{p-1}}\left(\sum _{i=1}^{r}{a_{i}p^{i}}-\sum _{i=1}^{r}{a_{i}}\right)={\frac {(n-a_{0})-(S_{p}(n)-a_{0})}{p-1}}={\frac {n-S_{p}(n)}{p-1}}$

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

שימושים

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

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

$\sum _{k=1}^{\infty }\left\lfloor {\frac {r}{p^{k}}}\right\rfloor +\sum _{k=1}^{\infty }\left\lfloor {\frac {n-r}{p^{k}}}\right\rfloor \leq \sum _{k=1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor$

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

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