הצגת המקור של הדף "מספרים זרים"

שני [[מספר שלם|מספרים שלמים]] נקראים '''מספרים זרים''', אם [[מחלק משותף מקסימלי|המחלק המשותף המקסימלי]] שלהם הוא 1, כלומר, אין אף מספר גדול מאחת ש[[מחלק]] את שניהם.

על-פי [[המשפט היסודי של האריתמטיקה]] אפשר לכתוב כל [[מספר טבעי]] באופן יחיד כמכפלה של גורמים ראשוניים. שני מספרים הם זרים [[אם ורק אם]] אין ברשימת הגורמים שלהם אף ראשוני משותף; לדוגמה, <math>\ 1496 = 2^3 \cdot 11\cdot 17</math> זר ל- <math>\ 19695=3\cdot 5\cdot 13\cdot 101</math>.

דוגמאות נוספות:
*5 ו-7 הם מספרים זרים.
*4 ו-6 אינם זרים, מכיוון ששניהם מתחלקים ב-2.
*אם p [[מספר ראשוני|ראשוני]], אז כל מספר שאינו מתחלק ב־p בהכרח זר ל-p.

שלשה של מספרים נקראת 'שלשה זרה' (ולפעמים 'שלשה פרימיטיבית') אם אין אף מספר גדול מאחת המחלק את כולם; וכן לרביעייה, חמישייה או קבוצה גדולה יותר. אם המספרים בקבוצה זרים גם זה לזה, אומרים שהם 'זרים בזוגות'. ייתכן שבקבוצת מספרים המספרים יהיו זרים בלי להיות זרים בזוגות. למשל 6,10,15 - אין מספר גדול מאחד המחלק את שלושתם, אך כל זוג מתוכם אינו זר.

==תכונות של מספרים זרים==

אם קיימים מספרים שלמים a,b כך ש- <math>\ an+bm=1</math>, אז n,m זרים, משום שכל מחלק משותף שלהם מחלק גם את אגף ימין בשוויון הזה. מאידך, מכיוון ש[[חוג המספרים השלמים]] הוא [[תחום ראשי]], לכל שני מספרים זרים n ו-m קיימים a ו־b כך ש- <math>\ an+bm=1</math>. [[האלגוריתם של אוקלידס]] מוצא את המקדמים הללו ב[[סיבוכיות זמן|זמן]] קצר יחסית. מתכונה זו מתקבלת הוכחה קלה של [[משפט השאריות הסיני]].

קבוצת המספרים בין 1 ל־n הזרים ל-n היא [[חבורה (מבנה אלגברי)|חבורה]] ביחס ל[[חשבון מודולרי|כפל מודולו]] n, הנקראת [[חבורת אוילר]] של n. גודלה של חבורה זו שווה ל-<math>\ \phi(n)</math>, כאשר <math>\ \phi</math> היא [[פונקציית אוילר]].

אם n ו־m זרים, אז [[כפולה משותפת מינימלית|הכפולה המשותפת המינימלית]] שלהם שווה ל[[כפל|מכפלתם]] nm.

עבור כל שני מספרים זרים n ו־m מתקיים שכל אחד מהם זר לכל [[חזקה (מתמטיקה)|העלאה בחזקה]] של האחר (לדוגמה, n זר ל-m<sup>3</sup>), וכן מתקיים שכל אחד מהם זר לסכומם n+m.

==ההסתברות ששני מספרים יהיו זרים==
נסמן ב-<math>P_N</math> את ההסתברות ששני מספרים טבעיים קטנים מ-N שנבחרים באקראי (ב[[התפלגות אחידה בדידה]]) יהיו זרים. כאשר N שואף לאינסוף, <math>P_N</math> שואף ל-<math>\tfrac{6}{\pi^2}\approx 0.6079</math>. על כן ניתן לומר שההסתברות ששני מספרים טבעיים כלשהם יהיו זרים היא <math>\tfrac{6}{\pi^2}</math> (נדרש תיאור של [[הסתברות]] זו כגבול משום שאי אפשר לבחור שני מספרים טבעיים סתם, בהתפלגות אחידה).

המקור לטענה הוא בנימוק הבא: נבחר שני מספרים באופן אקראי (למען הפשטות, נוותר על הדיוק ונניח שניתן לבחור מספרים טבעיים לא חסומים באופן אחיד). המספרים זרים אם ורק אם אין ראשוני שמחלק את שניהם. הסיכוי שראשוני <math>p</math> מחלק כל אחד מהם היא <math>\tfrac{1}{p}</math>, ולכן הסיכוי שהוא מחלק את שניהם הוא <math>\tfrac{1}{p^2}</math>. מכאן שהסיכוי שהוא לא מחלק את שניהם הוא <math>1-\tfrac{1}{p^2}</math>. לכל שני ראשוניים שונים, המאורעות הללו [[תלות (הסתברות)|בלתי תלויים]] ([[משפט השאריות הסיני]]). מכאן שההסתברות שאין אף ראשוני שמחלק את שני המספרים שנבחרו היא מכפלת ההסתברויות שכל ראשוני בנפרד לא מחלק את שניהם. כלומר ההסתברות היא:
: <math>\prod_p \left(1-\tfrac{1}{p^2}\right)</math>
כאשר המכפלה עוברת על כל הראשוניים. קיבלנו את ההופכי של [[מכפלת אוילר]] של [[פונקציית זטא של רימן]] בנקודה <math>s=2</math>, ולכן ההסתברות שווה ל-<math>\tfrac{1}{\zeta(2)}</math>. לפי הפתרון של [[בעיית בזל]], ערך זה שווה ל-<math>\tfrac{6}{\pi^2}</math>.

==הכללות==
ב[[חוג (מבנה אלגברי)|חוגים]] כלליים, לטענה שאיברים a ו־b זרים יכולה להיות שתי משמעויות: או שאין איבר לא [[איבר הפיך|הפיך]] שמחלק את שניהם, או שאין [[אידיאל (אלגברה)|אידיאל]] שמחלק את שניהם (ובמלים אחרות, האידיאל <math>\langle a,b\rangle</math> שווה לכל החוג). האפשרות השנייה תמיד חזקה מן הראשונה, וב[[תחום ראשי|תחומי אידיאלים ראשיים]] הן מתלכדות.

אומרים ששני אידיאלים (של [[חוג (מבנה אלגברי)|חוג]] כלשהו) הם זרים (או '''קו-מקסימליים''', או מקסימליים הדדית), אם סכומם שווה לכל החוג. זוהי תכונה מרכזית בהכללה של משפט השאריות הסיני לחוגים כלליים.
==קישורים חיצוניים==
{{מיזמים|ויקימילון=מספרים זרים}}
* {{MathWorld}}

[[קטגוריה:תורת המספרים]]
[[קטגוריה:הוכחות]]