נוסחת לז'נדר

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

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

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

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

הוכחה[עריכת קוד מקור | עריכה]

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

דוגמה[עריכת קוד מקור | עריכה]

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

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

ניסוח שקול[עריכת קוד מקור | עריכה]

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

הוכחה[עריכת קוד מקור | עריכה]

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

כעת נשים לב כי:

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

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

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

שימושים[עריכת קוד מקור | עריכה]

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

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

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

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