מספרים זרים

ריבוי של מספרים שלמים נקרא "מספרים זרים" אם אין להם גורם ראשוני משותף פרט ל־1. גורם ראשוני הוא מספר ראשוני (מספר שמתחלק רק ב־1 ובעצמו). לדוגמה: 1496 = 2^3·11·17 ו־19695 = 3·5·13·101 הם זרים זה לזה. שלשה של מספרים נקראת "שלשה זרה" אם אין מספר גדול מ־1 שמחלק את כולם. ייתכן שקבוצה תהיה זרה ללא היותה זרה בזוגות, למשל 6, 10, 15, אין מחלק גדול מ־1 שמחלק את שלושתם, אבל כל זוג ביניהם אינו זר.

אם קיימים שלמים a ו־b כך ש־a·n + b·m = 1, אז n ו־m זרים. ההפך נכון גם הוא בחוג של המספרים השלמים: לכל שני מספרים זרים קיימים a ו־b כאלה. האלגוריתם של אוקלידס (שיטה למציאת המחלק המשותף הגדול ביותר) מוצא את המקדמים הללו בזמן קצר יחסית. מתכונה זו נובעת הוכחה פשוטה למשפט השאריות הסיני.

המספרים בין 1 ל־n שהם זרים ל־n יוצרים חבורה ביחס לכפל מודולו n. זו חבורת אוילר של n, וגודלה שווה ל־φ(n), כאשר φ היא פונקציית אוילר (מספר המקדמים שלמים מ־1 עד n הזרים ל־n). אם n ו־m זרים, אז המכנה המשותף המינימלי שלהם (ה־lcm) שווה ל־n·m. בנוסף, אם n ו־m זרים, אז כל אחד מהם נשאר זר לכל חזקה של האחר ולסכומם n+m.

נסמן ב־P_N את ההסתברות ששני מספרים טבעיים קטנים מ־N שנבחרים באקראי יהיו זרים. כש־N שואף לאינסוף, P_N שואף ל־6/π^2 ≈ 0.6079. ההסבר העקרוני הוא כזה: הסיכוי שמספר ראשוני p מחלק מספר נתון הוא 1/p, ולכן הסיכוי שהוא מחלק גם את שניהם הוא 1/p^2. ההסתברות שלכל ראשוני p הוא לא יחלק את שניהם היא 1−1/p^2, וההסתברות שאין אף ראשוני כזה היא מכפלת כל התוצאות הללו על פני כל הראשוניים. מכפלה זו שווה ל־1/ζ(2), ובפתרון בעיית בזל היא שווה ל־6/π^2.

בתחומים כלליים יותר (חוגים), אפשר להגדיר זוג איברים כזרים בשתי מנות: או שאין איבר לא־הפיך שמחלק את שניהם, או שהאידיאל שהם מייצרים שווה לכל החוג. האפשרות השנייה חזקה יותר, ובחוגים שבהם כל אידיאל ראשי שתי ההגדרות מתאחדות. שני אידיאלים נקראים זרים אם סכומם שווה לכל החוג; זו תכונה חשובה בהכללה של משפט השאריות הסיני.

מספרים נקראים זרים אם אין להם אף מספר ראשוני משותף חוץ מ־1. מספר ראשוני הוא מספר שמתחלק רק ב־1 ובעצמו. למשל 1496 ו־19695 אינם חולקים אף ראשוני.

שלושה מספרים יכולים להיות זרים יחד גם אם זוגות מהם לא זרים. דוגמה פשוטה: 6, 10 ו־15. אם אפשר להכפיל ולחבר שני מספרים ולקבל 1, אז הם זרים. יש שיטה בשם אלגוריתם של אוקלידס שעוזרת למצוא זאת.

המספרים מ־1 עד n שזרים ל־n הם קבוצה מיוחדת בכפל מודולו n. מספרם נקרא φ(n).

אם בוחרים שני מספרים גדולים מאוד באקראי, הסיכוי שהם יהיו זרים הוא כ־0.608. החישוב משתמש בעובדה שראשון p מחלק מספר ב־1 מתוך p פעמים, ולכן להסביר את זה צריך להכפיל הסתברויות על כל הראשוניים.

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