מחלק

במתמטיקה, מספר שלם 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}\cdot 3^{1}$, על פי המשפט נובע כי למספר 12 יש בדיוק: $\!\,(2+1)\cdot (1+1)=3\cdot 2=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\leq y_{i}\leq x_{i}$.

כלומר, לכל וקטור מהצורה $\ (y_{1},\dots ,y_{n})$ עם $\ 0\leq y_{i}\leq x_{i}$ מותאם מחלק אחד ויחיד. מקומבינטוריקה בסיסית מקבלים כי מספר הווקטורים הזה הוא בדיוק $\ (x_{1}+1)(x_{2}+1)(x_{3}+1)...(x_{n}+1)$, שכן יש לנו $\ x_{1}+1$ בחירות אפשריות לקואורדינטה הראשונה, $\ x_{2}+1$ בחירות לקואורדינטה השנייה וכן הלאה.

ראו גם

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