נוסחת לז'נדר

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

n!=pnp(k=1npk)

כאשר p ראשוני ו-x פונקציית הערך השלם (עיגול כלפי מטה).

בניסוח שקול, הנוסחה קובעת שהמעריך של החזקה הגבוהה ביותר של ראשוני p המחלקת את n! הוא k=1npk . הסכום האינסופי לכאורה הוא למעשה סכום סופי, שכן החל משלב מסוים כל איברי הסכום מתאפסים משום שעבור pk>n מתקיים npk=0 .

הנוסחה, הנקראת על שם המתמטיקאי אדריאן-מארי לז'נדר, נקראת גם נוסחת דה פוליניאק על שם אלפונס דה פוליניאק.

הוכחה

n! הוא מכפלת המספרים מ-1 עד n . לכן המעריך של החזקה הגבוהה ביותר של ראשוני p המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של p המחלקות כל אחד מהמספרים מ-1 עד n . כל ראשוני p מחלק בדיוק np מספרים מ-1 עד n (שכן כפולותיו הן p,2p,3p,,npp). ביניהם np2 מספרים המתחלקים אפילו ב-p2 , ולכן יש לספור אותם פעם נוספת. ובאופן כללי, יש ביניהם בדיוק npk המתחלקים ב-pk , ויש לספור אותם שוב. נסכום את כל המקרים יחדיו ונקבל שהמעריך של החזקה הגבוהה ביותר של p המחלקת את n! הוא k=1npk .

דוגמה

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

k=11995k=39+7+1+0+0+=47

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

ניסוח שקול

נסמן Sp(n) את סכום הספרות של n בבסיס p . ניסוח שקול לנוסחת לז'נדר קובע שהמעריך של החזקה הגבוהה ביותר של p המחלקת את n! הוא nSp(n)p1 .

הוכחה

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

n=arpr+ar1pr1++a1p+a0;ar,,a0<p

כעת נשים לב כי

npk=arpr++a0pk=arprk++ak+ak1p1++a0pk=arprk++ak

זאת מכיוון ש-ak1p1++a0pk<1 . מכאן לפי נוסחת לז'נדר המעריך של חזקה הגבוהה ביותר של p המחלקת את n! הוא:

k=1npk=k=1(arprk++ak)

נבחין כי בטור האחרון לכל 1ir , המקדם ai מופיע פעם אחת בדיוק כמקדם של כל אחד מבין 1,p,,pi1 . לכן נוכל לסדר מחדש את הטור האחרון בצורה:

=i=1rai(1+p++pi1)=i=1rai(pi1p1)=1p1(i=1raipii=1rai)=(na0)(Sp(n)a0)p1=nSp(n)p1

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

שימושים

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

פונקציית הערך השלם מקיימת את אי-השוויון הטריוויאלי a+ba+b . לכן מתקיים:

k=1rpk+k=1nrpkk=1npk

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

לפי נוסחת לז'נדר המעריך של החזקה הגבוהה ביותר של p המחלקת את (2nn) הוא k=1(2npk2npk) , עובדה המשמשת בהוכחה האלמנטרית של ארדש להשערת ברטראן. נוסחת_לז'נדר16686636Q23041626