נוסחת לז'נדר

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

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

בניסוח שקול, הנוסחה קובעת שהמעריך של החזקה הגבוהה ביותר של ראשוני  המחלקת את  הוא . הסכום האינסופי לכאורה הוא למעשה סכום סופי, שכן החל משלב מסוים כל איברי הסכום מתאפסים משום של- מתקיים .

הוכחה
" עצרת" הוא מכפלת המספרים מ-1 עד :

לכן המעריך של החזקה הגבוהה ביותר של ראשוני  המחלקת אותו הוא סכום המעריכים של החזקות הגבוהות ביותר של  המחלקות כל אחד מהמספרים מ-1 עד . 

לכל ראשוני , אנחנו יודעים כי  מחלק בדיוק  מספרים מ-1 עד  שכן כפולותיו הן . 

ביניהם  מספרים שמתחלקים אפילו ב-, ולכן יש לספור אותם פעם נוספת. 

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

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

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

ניסוחים שקולים

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

 הוכחה 
נציג את  בבסיס :

כעת נשים לב כי

זאת מכיוון ש-. מכאן לפי נוסחת לז'נדר המעריך של חזקה הגבוהה ביותר של  המחלקת את  הוא:

המעבר מ-(1) ל-(2) אפשרי מכיוון שלכל , המקדם  מופיע פעם אחת בדיוק כמקדם של כל אחד מבין .

המעבר מ-(2) ל-(3) מתבצע על-ידי שימוש בנוסחה לסכום טור הנדסי.

מ.ש.ל.

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

פונקציית פון מנגולד מוגדרת כך שלכל מספר טבעי :

בגרסה זו, נוסחת לז'נדר מקבלת את הצורה:

 הוכחה 
לוקחים לוגריתם על שני צידי המשוואה בנוסחת לז'נדר המקורית, ומקבלים:

מ.ש.ל.

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

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

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

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

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