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

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

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

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

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

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

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

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

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

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

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

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

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

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

נציג את ${\displaystyle n}$ בבסיס ${\displaystyle 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}$

כעת נשים לב כי

${\displaystyle \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}}$

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

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

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

${\displaystyle =\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}}\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}}}$

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

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

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

${\displaystyle \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 }$

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

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