נוסחת לז'נדר

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

$n!=\prod _{p\,\leq \,n}p^{a},\quad a=\sum _{k\,=\,1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor$

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

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

הוכחה

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

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

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

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

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

ובאופן כללי, יש ביניהם בדיוק $\left\lfloor {\frac {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+\cdots =47$

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

ניסוחים שקולים

סכום ספרות

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

הוכחה

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

${\displaystyle n=a_{r}p^{r}+a_{r-1}p^{r-1}+\cdots +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}+\cdots +a_{0}}{p^{k}}}\right\rfloor =\left\lfloor a_{r}p^{r-k}+\cdots +a_{k}+a_{k-1}p^{-1}+\cdots +a_{0}p^{-k}\right\rfloor =a_{r}p^{r-k}+\cdots +a_{k}$

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

${\begin{aligned}\sum _{k\,=\,1}^{\infty }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\sum _{k\,=\,1}^{\infty }(a_{r}p^{r-k}+\cdots +a_{k})\quad {\text{(1)}}\\=\sum _{i\,=\,1}^{r}a_{i}(1+p+\cdots +p^{i-1})\quad {\text{(2)}}\\=\sum _{i\,=\,1}^{r}a_{i}{\frac {p^{i}-1}{p-1}}\quad {\text{(3)}}\\={\frac {1}{p-1}}\left(\sum _{i\,=\,1}^{r}a_{i}p^{i}-\sum _{i\,=\,1}^{r}a_{i}\right)\quad {\phantom {\text{(0)}}}\\={\frac {(n-a_{0})-(S_{p}(n)-a_{0})}{p-1}}\quad {\phantom {\text{(0)}}}\\={\frac {n-S_{p}(n)}{p-1}}\quad {\phantom {\text{(0)}}}\end{aligned}}$

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

המעבר מ-(2) ל-(3) מתבצע על-ידי שימוש בנוסחה לסכום טור הנדסי.

מ.ש.ל.

גרסה לוגריתמית

קיימת לנוסחת לז'נדר גרסה שקולה אשר עושה שימוש בפונקציית הלוגריתם הטבעי $\ln$ ופונקציית פון מנגולד $\Lambda$.

פונקציית פון מנגולד מוגדרת כך שלכל מספר טבעי $n$:

$\Lambda (n):={\begin{cases}\ln p&{\text{if }}n=p^{k}{\text{, }}p{\text{ is prime, }}k\geq 1\\0&{\text{else}}\end{cases}}$

בגרסה זו, נוסחת לז'נדר מקבלת את הצורה:

$\ln(n!)=\sum _{m=1}^{n}{\Lambda (m)\left\lfloor {\frac {n}{m}}\right\rfloor }$

הוכחה

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

$\ln(n!)=\ln \left(\prod _{p\leq n}p^{a}\right)=\sum _{p\leq n}a_{p}\ln(p)=\sum _{p\leq n}\sum _{k\,=\,1}^{\infty }\ln p\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\sum _{p^{k}\leq n}\ln p\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =\sum _{m=1}^{n}{\Lambda (m)\left\lfloor {\frac {n}{m}}\right\rfloor }$

מ.ש.ל.

שימושים

מקדם בינומי ${\binom {n}{r}}={\frac {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)!$, כלומר ${\binom {n}{r}}={\frac {n!}{r!(n-r)!}}$ מספר שלם.

לפי נוסחת לז'נדר המעריך של החזקה הגבוהה ביותר של $p$ המחלקת את ${\binom {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)$, עובדה המשמשת בהוכחה האלמנטרית של פאול ארדש להשערת ברטראן.