נוסחת לז'נדר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
אין תקציר עריכה |
||
שורה 8:
==הוכחה==
<math>n!</math> הוא מכפלת המספרים מ-1 עד n. לכן החזקה הגבוהה ביותר של ראשוני <math>p</math> המחלקת אותו היא סכום החזקות הגבוהות ביותר של p המחלקות כל אחד מהמספרים מ-1 עד n. לכל ראשוני <math>p</math>, <math>p</math> מחלק בדיוק <math> \left \lfloor \tfrac{n}{p} \right \rfloor</math> מספרים מ-1 עד n (שכן כפולותיו הן <math>p, 2p, 3p,\ldots, \left \lfloor \tfrac{n}{p} \right \rfloor p</math>). ביניהם <math> \left \lfloor \tfrac{n}{p^2} \right \rfloor</math> מספרים שמתחלקים אפילו ב-<math>p^2</math>. ובאופן כללי ביניהם יש בדיוק <math> \left \lfloor \tfrac{n}{p^k} \right \rfloor</math> המתחלקים ב-<math>p^k</math>. נסכום את כל המקרים יחדיו ונקבל שהחזקה הגבוהה ביותר של <math>p</math> המחלקת את <math>n!</math> היא <math>\sum_{k=1}^{\infty} \left \lfloor \frac{n}{p^k} \right \rfloor</math>.
==ניסוח שקול==
נסמן ב-<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_r p^r + a_{r-1} p^{r-1} + \ldots + a_1 p + a_0 \quad ;\quad a_r,\ldots,a_0 < p</math>
כעת נשים לב כי:
:<math>\left \lfloor \frac{n}{p^k} \right \rfloor = \left \lfloor \frac{a_r p^r + \ldots + a_0}{p^k} \right \rfloor = \left \lfloor a_r p^{r-k} + \ldots + a_k + a_{k-1}p^{-1}\ldots + a_0 p^{-k} \right \rfloor = a_r p^{r-k} + \ldots + a_k</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_r p^{r-k} + \ldots + a_k) = </math>
==דוגמה==
שורה 14 ⟵ 27:
מכאן שהמספר <math>199!</math> מסתיים ב-47 אפסים.
==שימושים==
| |||