מספרים זרים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

על-פי המשפט היסודי של האריתמטיקה אפשר לכתוב כל מספר באופן יחיד כמכפלה של גורמים ראשוניים. שני מספרים הם זרים אם ורק אם אין ברשימת הגורמים שלהם אף ראשוני משותף; לדוגמה, \ 2\cdot 2\cdot 2\cdot 11\cdot 17 זר ל- \ 3\cdot 5\cdot 13\cdot 101.

דוגמאות נוספות:

  • 5 ו-7 הם מספרים זרים.
  • 4 ו-6 אינם זרים, מכיוון ששניהם מתחלקים ב-2.
  • אם p ראשוני, אז כל מספר שאינו מתחלק ב- p בהכרח זר ל-p.

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

תכונות של מספרים זרים[עריכת קוד מקור | עריכה]

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

קבוצת המספרים בין 1 ל- n הזרים ל-n היא חבורה ביחס לכפל מודולו n, הנקראת חבורת אוילר של n. גודלה של חבורה זו שווה ל-\ \phi(n), כאשר \ \phi היא פונקציית אוילר.

אם n ו- m זרים, אז הכפולה המשותפת המינימלית שלהם שווה למכפלתם nm.

עבור כל שני מספרים זרים n ו- m מתקיים שכל אחד מהם זר לכל העלאה בחזקה של האחר (לדוגמה, n זר ל-m3), וכן מתקיים שכל אחד מהם זר לסכומם n+m.

ההסתברות ששני מספרים יהיו זרים[עריכת קוד מקור | עריכה]

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

המקור לטענה הוא בנימוק הבא: נבחר שני מספרים באופן אקראי (למען הפשטות, נוותר על הדיוק ונניח שניתן לבחור מספרים טבעיים לא חסומים באופן אחיד). המספרים זרים אם ורק אם אין ראשוני שמחלק את שניהם. הסיכוי שראשוני p מחלק כל אחד מהם היא \tfrac{1}{p}, ולכן הסיכוי שהוא מחלק את שניהם היא \tfrac{1}{p^2}. מכאן שהסיכוי שהוא לא מחלק את שניהם היא 1-\tfrac{1}{p^2}. לכל שני ראשוניים שונים, המאורעות הללו בלתי תלויים (מכיוון שמספר מתחלק בשני ראשוניים שונים אם ורק אם הוא מתחלק במכפלה שלהם). מכאן שההסתברות שאין ראשוני שמחלק את שני המספרים שנבחרו היא מכפלת ההסתברויות שכל ראשוני בנפרד לא מחלק את שניהם. כלומר ההסתברות היא:

\prod_p \left(1-\tfrac{1}{p^2}\right)

כאשר המכפלה עוברת על כל הראשוניים. קיבלנו את ההופכי של מכפלת אוילר של פונקציית זטא של רימן בנקודה s=2, ולכן ההסתברות שווה ל-\tfrac{1}{\zeta(2)}. לפי הפתרון של בעיית בזל, ערך זה שווה ל-\tfrac{6}{\pi^2}.

הכללות[עריכת קוד מקור | עריכה]

בחוגים כלליים, לטענה שאיברים a ו- b זרים יכולה להיות שתי משמעויות: או שאין איבר לא הפיך שמחלק את שניהם, או שאין אידאל שמחלק את שניהם (ובמלים אחרות, האידאל \langle a,b\rangle שווה לכל החוג). האפשרות השנייה תמיד חזקה מן הראשונה, ובתחומי אידאלים ראשיים הן מתלכדות.

אומרים ששני אידאלים (של חוג כלשהו) הם זרים (או קו-מקסימליים, או מקסימליים הדדית), אם סכומם שווה לכל החוג. זוהי תכונה מרכזית בהכללה של משפט השאריות הסיני לחוגים כלליים.