מחלק

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

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

היחס "לחלק את" הוא רפלקסיבי (a|a לכל a), וטרנזיטיבי (אם a|b וגם b|c אז a|c), ולכן הוא מהווה קדם סדר. לעומת זאת היחס אינו אנטי סימטרי ($\,5,-5$ מחלקים זה את זה). בין המספרים הטבעיים היחס הוא יחס סדר חלקי.

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

המשפט היסודי של האריתמטיקה, לפיו כל מספר טבעי יכול להיכתב כמכפלה ייחודית של מספרים ראשוניים, פרט לשינוי הסדר של הגורמים, גורם לעניין מוגבר במספרים הראשוניים המחלקים מספר נתון, כלומר בגורמים הראשוניים שלו.

הכללה

כאשר עוסקים בחוג כלשהו, גם כן ניתן לדבר על יחס של חלוקה. נאמר כי איבר $\ a$ הוא מחלק של איבר $\ b$ אם קיים בחוג איבר $\ c$ כך ש-$\ b=ac$. למשל בחוג הפולינומים במקדמים שלמים, הפולינום $\ x+1$ מחלק את $\ x^{3}-x$, כי $\ x^{3}-x=(x+1)(x^{2}-x)$.

מושג המחלק נחוץ לצורך עיסוק בתחומי פריקות יחידה.

מספר המחלקים של מספר שלם

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

$\!\,{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)\cdot ...\cdot (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)\cdot ...\cdot (x_{n}+1)$, שכן יש לנו $\ x_{1}+1$ בחירות אפשריות לקואורדינטה הראשונה, $\ x_{2}+1$ בחירות לקואורדינטה השנייה וכן הלאה.

ראו גם

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