מחלק

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

במתמטיקה, מספר שלם a הוא מחלק של מספר שלם b אם אפשר לכתוב את b כמכפלה של a במספר שלם אחר. במקרה כזה, השארית בחלוקה של b ב-a היא 0. לדוגמה: 5 הוא מחלק של המספר 35, אך לא של המספר 33.

נהוג לסמן מחלקים כך: a|b פירושו "a מחלק את b."

היחס "לחלק את" הוא יחס סדר: הוא רפלקסיבי (a|a), טרנזיטיבי (אם a|b וגם b|c אז a|c) ואנטי סימטרי (אם a|b וגם b|a אז a=b).

למושג המחלק המשותף המקסימלי של שני מספרים יש חשיבות רבה במתמטיקה.

[עריכה] הכללה

כאשר עוסקים בחוג כלשהו, גם כן ניתן לדבר על יחס של חלוקה. נאמר כי איבר \ a הוא מחלק של איבר \ b אם קיים בחוג איבר \ c כך ש-\ b=ac.

מושג המחלק הוא בסיסי לצורך עיסוק במושג של תחום פריקות חד ערכית.

[עריכה] מספר מחלקיו של מספר שלם

משפט: מספר המחלקים של מספר שלם המיוצג בצורה:

\!\, {p_1}^{x_1}\cdot{p_2}^{x_2}\cdot{p_3}^{x_3}\cdot...\cdot{p_n}^{x_n}

כאשר המספרים: \!\, p_1,...,p_n ראשוניים, והמספרים: \!\, x_1,...,x_n שלמים, (על פי המשפט היסודי של האריתמטיקה, לכל מספר שלם יש הצגה יחידה כמכפלה של מספרים ראשוניים), הוא:

\  (x_1+1)(x_2+1)(x_3+1)...(x_n+1)

מכאן, הפונקציה האריתמטית \ d(n) הסופרת את המחלקים של \ n, היא פונקציה כפלית.

לדוגמה ניקח את המספר 12. ברור כי למספר 12 יש בדיוק שישה מחלקים: 1,2,3,4,6,12
נציג את המספר כמכפלה של ראשוניים: \!\, 2^2\cdot3^1, על פי המשפט נובע כי למספר 12 יש בדיוק: \!\, (2+1)\cdot(1+1)=3\cdot2=6 מחלקים.

הוכחה: כדי להיווכח בנכונות המשפט די לשים לב לכך שכל מחלק של המספר \ {p_1}^{x_1}\cdot{p_2}^{x_2}\cdot{p_3}^{x_3}\cdot...\cdot{p_n}^{x_n} הוא מהצורה \ {p_1}^{y_1}\cdot{p_2}^{y_2}\cdot{p_3}^{y_3}\cdot...\cdot{p_n}^{y_n} כאשר \ 0\le y_i\le x_i.

כלומר, לכל וקטור מהצורה \ (y_1,\dots,y_n) עם \ 0\le y_i\le x_i מותאם מחלק אחד ויחיד. מקומבינטוריקה בסיסית מקבלים כי מספר הווקטורים הזה הוא בדיוק \ (x_1+1)(x_2+1)(x_3+1)...(x_n+1), שכן יש לנו \ x_1+1 בחירות אפשריות לקואורדינטה הראשונה, \ x_2+1 בחירות לקואורדינטה השנייה וכן הלאה.

[עריכה] ראו גם

מבחני התחלקות

שפות אחרות