הצגת המקור של הדף "נוסחת לז'נדר"

ב[[תורת המספרים]], '''נוסחת לז'נדר''' (על שם ה[[מתמטיקאי]] ה[[צרפתים|צרפתי]] [[אדריאן-מארי לז'נדר]]; נקראת גם '''נוסחת דה פוליניאק''' על שם [[אלפונס דה פוליניאק]]) קובעת את ה[[פירוק לגורמים של מספר שלם|פירוק לגורמים]] [[מספר ראשוני|ראשוניים]] של <math>n!</math>, כאשר הסימן "<math>!</math>" מסמן את פעולת ה[[עצרת (מתמטיקה)|עצרת]]:
:<math>n!=\prod_{p\,\le\,n}p^a,\quad a=\sum_{k\,=\,1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor</math>
כאשר <math>p</math> [[מספר ראשוני]] ו-<math>\lfloor{x}\rfloor</math> היא [[פונקציית הערך השלם]] ([[עיגול (אריתמטיקה)|עיגול]] כלפי מטה).

בניסוח שקול, הנוסחה קובעת שהמעריך של ה[[חזקה (מתמטיקה)|חזקה]] הגבוהה ביותר של ראשוני <math>p</math> המחלקת את <math>n!</math> הוא <math>\sum_{k\,=\,1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor</math>. ה[[סכום]] האינסופי לכאורה הוא למעשה סכום סופי, שכן החל משלב מסוים כל איברי הסכום מתאפסים משום של-<math>p^k>n</math> מתקיים <math>\left\lfloor\frac{n}{p^k}\right\rfloor=0</math>.

==הוכחה==
"<math>n</math> עצרת" הוא מכפלת המספרים מ-1 עד <math>n</math>:
:<math>n!=n(n-1)(n-2)\cdots3\cdot2\cdot1</math>
לכן המעריך של החזקה הגבוהה ביותר של ראשוני <math>p</math> המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של <math>p</math> המחלקות כל אחד מהמספרים מ-1 עד <math>n</math>. 

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

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

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

==דוגמה==
נמצא כמה [[אפס (מספר)|אפסים]] מופיעים בסוף [[השיטה העשרונית|הכתיב העשרוני]] של המספר <math>199!</math>. מספר האפסים שווה למעריך של החזקה הגבוהה ביותר של 10 המחלקת את <math>199!</math>. הפירוק לגורמים של חזקות של 10 הוא <math>10^m=2^m\cdot5^m</math>. לכן המעריך המבוקש יהיה הקטן מבין המעריכים של החזקות הגבוהות ביותר של הראשוניים 2 ו-5 המחלקות את <math>199!</math>. ברור כי המעריך הגבוה יותר מבין השניים הוא זה של 2 (שכן הוא מחלק יותר מספרים בין 1 ל-199) ולכן מספיק למצוא את המעריך של 5. לפי הנוסחה המעריך הוא:
:<math>\sum_{k\,=\,1}^\infty\left\lfloor\frac{199}{5^k}\right\rfloor=39+7+1+0+0+\cdots=47</math>
מכאן שהמספר <math>199!</math> מסתיים ב-47 אפסים.

==ניסוח שקול==
נסמן ב-<math>S_p(n)</math> את סכום הספרות של <math>n</math> ב[[בסיס (אריתמטיקה)|בסיס]] <math>p</math>. ניסוח שקול לנוסחת לז'נדר קובע שהמעריך של החזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>n!</math> הוא <math>\frac{n-S_p(n)}{p-1}</math>.

===הוכחה===
נציג את <math>n</math> בבסיס <math>p</math>:
:<math>n=a_rp^r+a_{r-1}p^{r-1}+\cdots+a_1p+a_0\quad;\quad a_r,\ldots,a_0<p</math>
כעת נשים לב כי
:<math>\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</math>
זאת מכיוון ש-<math>a_{k-1}p^{-1}+\cdots+a_0p^{-k}<1</math>. מכאן לפי נוסחת לז'נדר המעריך של חזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>n!</math> הוא:
:<math>\sum_{k\,=\,1}^\infty\left\lfloor\frac{n}{p^k}\right\rfloor=\sum_{k\,=\,1}^\infty(a_rp^{r-k}+\cdots+a_k)=</math>
נבחין כי בטור האחרון לכל <math>1\le i\le r</math>, המקדם <math>a_i</math> מופיע פעם אחת בדיוק כמקדם של כל אחד מבין <math>1,p,\ldots,p^{i-1}</math>. לכן נוכל לסדר מחדש את הטור האחרון בצורה:
:<math>=\sum_{i\,=\,1}^ra_i(1+p+\cdots+p^{i-1})=\sum_{i\,=\,1}^ra_i\frac{p^i-1}{p-1}=\frac{1}{p-1}\left(\sum_{i\,=\,1}^ra_ip^i-\sum_{i\,=\,1}^ra_i\right)=\frac{(n-a_0)-(S_p(n)-a_0)}{p-1}=\frac{n-S_p(n)}{p-1}</math>
במעבר הראשון עשינו שימוש בנוסחה לסכום [[טור (מתמטיקה)#טור הנדסי|טור הנדסי]].

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

פונקציית הערך השלם מקיימת את האי-שוויון ה[[טריוויאלי (מתמטיקה)|טריוויאלי]] <math>\lfloor a\rfloor+\lfloor b\rfloor\le\lfloor a+b\rfloor</math>. לכן מתקיים:
:<math>\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</math>
לפי נוסחת לז'נדר אגף ימין הוא המעריך של החזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>n!</math>, בעוד אגף שמאל הוא המעריך של החזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>r!(n-r)!</math>. מהאי-שוויון אנו מסיקים שלכל חזקת ראשוני בפירוק של <math>r!(n-r)!</math> לגורמים, כפולה שלו מופיעה בפירוק של <math>n!</math>, ולכן <math>n!</math> מתחלק ב-<math>r!(n-r)!</math>, כלומר <math>\binom{n}{r}=\frac{n!}{r!(n-r)!}</math> מספר שלם.

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

{{מיון רגיל:לז'נדר, זהות}}

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