נוסחת לז'נדר

בתורת המספרים, **נוסחת לז'נדר** (על שם המתמטיקאי הצרפתי אדריאן-מארי לז'נדר; נקראת גם **נוסחת דה פוליניאק** על שם אלפונס דה פוליניאק) קובעת את הפירוק לגורמים ראשוניים של n!, כאשר הסימן "!" מסמן את פעולת העצרת:
:n!=\prod_{p\,\le\,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)\cdots3\cdot2\cdot1
לכן המעריך של החזקה הגבוהה ביותר של ראשוני 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\cdot5^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:
:n=a_rp^r+a_{r-1}p^{r-1}+\cdots+a_1p+a_0\quad;\quad a_r,\ldots,a_0
כעת נשים לב כי
:\left\lfloor\frac{n}{p^k}\right\rfloor=\left\lfloor\frac{a_rp^r+\cdots+a_0}{p^k}\right\rfloor=\left\lfloor a_rp^{r-k}+ \cdots+a_k+a_{k-1}p^{-1}+\cdots+a_0p^{-k}\right\rfloor=a_rp^{r-k}+\cdots+a_k
זאת מכיוון ש-a_{k-1}p^{-1}+\cdots+a_0p^{-k}. מכאן לפי נוסחת לז'נדר המעריך של חזקה הגבוהה ביותר של p המחלקת את n! הוא:
:\begin{aligned}
\sum_{k\,=\,1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor=\sum_{k\,=\,1}^\infty(a_rp^{r-k}+\cdots+a_k)\quad\text{(1)}\\
=\sum_{i\,=\,1}^ra_i(1+p+\cdots+p^{i-1}) \quad \text{(2)}\\
=\sum_{i\,=\,1}^ra_i\frac{p^i-1}{p-1} \quad \text{(3)}\\
=\frac{1}{p-1}\left(\sum_{i\,=\,1}^ra_ip^i-\sum_{i\,=\,1}^ra_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\le i\le 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\ge 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\le n}p^a\right)=\sum_{p\le n}a_p\ln(p)=\sum_{p\le n}\sum_{k\,=\,1}^\infty\ln p\left\lfloor\frac{n}{p^k}\right\rfloor=\sum_{p^k\le 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\le\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\le\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), עובדה המשמשת בהוכחה האלמנטרית של פאול ארדש להשערת ברטראן.

קטגוריה:משפטים בתורת המספרים
קטגוריה:מספרים ראשוניים
קטגוריה:זהויות במתמטיקה