מחלק

במתמטיקה, מספר שלם 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$ בחירות לקואורדינטה השנייה וכן הלאה.

ראו גם

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