פונקציית מביוס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←דוגמאות: מיותר, כל שני ראשוניים הם זרים תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
תיקון בהסבר, בלבול בין m ל-n |
||
שורה 29:
נסמן <math>f(m,n)=|\{k: 1\le k \le m, (k,n)=1\}|</math>, כלומר (f(m,n הוא מספר המספרים בין 1 ל-m שזרים ל-n. נרצה למצוא נוסחה לחישוב f.
נסמן ב p<sub>1</sub>,p<sub>2</sub>...p<sub>r</sub> את הראשוניים השונים שמחלקים את n (ייתכן יותר מפעם אחת). נחשב את f לפי [[עקרון ההכלה וההפרדה]]: ראשית נוסיף את כל המספרים בין 1 ל-m, יש m כאלו. אחר כך לכל p<sub>i</sub> נוריד את כל המספרים שמתחלקים בו, יש <math>\left[\frac{
<math>\left[\frac{
<math>f(m,n)=\sum_{S\subset\{1,...,r\}}{(-1)^{|S|}\left[\frac{m}{\prod_{s \in S}p_s}\right]}</math>
| |||