נוסחת לז'נדר

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

$ n!=\prod _{p\leq n}p^{\left(\sum \limits _{k=1}^{\infty }\left\lfloor {\dfrac {n}{p^{k}}}\right\rfloor \right)} $

כאשר $ 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 $ . לכן המעריך של החזקה הגבוהה ביותר של ראשוני $ p $ המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של $ p $ המחלקות כל אחד מהמספרים מ-1 עד $ n $ . כל ראשוני $ p $ מחלק בדיוק $ \left\lfloor {\tfrac {n}{p}}\right\rfloor $ מספרים מ-1 עד $ n $ (שכן כפולותיו הן $ p,2p,3p,\ldots ,\left\lfloor {\tfrac {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! $ הוא $ \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 $ :

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

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

$ {=\sum _{i=1}^{r}a_{i}(1+p+\cdots +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) $ , עובדה המשמשת בהוכחה האלמנטרית של ארדש להשערת ברטראן.