תקציר תורת המספרים, סמסטר א תשע״ג
מתוך Math-Wiki
בקורס זה ו־. כמו כן, אלא אם צוין אחרת, וכל המשתנים והנעלמים שלמים.
- משפט פיאנו: קיימת קבוצה בודדה שעבורה יש פונקציה המקיימת את אקסיומות פיאנו: חח״ע, , ואם מקיימת אזי .
- מחולק לשלוש קבוצות: יחידות – , ראשוניים – ופריקים – .
- לכל ו־ קיים זוג יחיד של שארית ומנה כך ש־.
- המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
- למת אוקלידס: יהי . אם אז .
- יהיו . נסמן אם .
- נניח ש־ ו/או שונים מ־0. אזי קיים יחיד (הנקרא מחלק משותף מקסימלי של ומסומן ) עבורו ואם כך ש־ אזי .
- אם אזי .
- .
- .
- אם זרים ו־ אזי .
- אם אזי .
- אלגוריתם אוקלידס: נניח ונרצה לחשב כאשר . אם שארית החלוקה של ב־ אזי . נמשיך כך עד שנקבל . ניתן להעזר באלגוריתם גם כדי לפתור את : נסמן ולכן בתהליך החישוב של עם האלגוריתם נקבל כאשר . לפיכך:
- משוואה דיאופנטית ב־2 משתנים: נרצה לפתור כאשר משתנים והשאר קבועים. נחלק למקרים:
- : אין פתרון.
- : ניתן לפתור ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא לכל .
- : נחלק את אגפי המשוואה ב־ ונקבל משוואה חדשה מהמקרה הקודם.
- אם בפרט אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
- נאמר ש־ חופפים מודולו (ונסמן ) אם . מגדיר יחס שקילות כאשר מחלקת השקילות של ו־ קבוצת מחלקות השקילות.
- אם ו־ אז .
- יהי . אם״ם הפיך. ניתן למצוא את ההופכי ל־ ע״י פתירת , ואז .
- .
- פונקציית אוילר היא עבורה .
- אם אז .
- מערכת מלאה מודולו m היא קבוצה עבורה . קיים כנ״ל יחיד לכל . באופן שקול, המערכת מלאה מודולו אם .
- אם מלאה מודולו , ו־ שלם אזי מלאה מודולו .
- מערכת מצומצמת מודולו m היא קבוצה כך ש־.
- אם מצומצמת מודולו ו־ אז מצומצמת מודולו .
- אם אזי . בפרט, .
- משפט גאוס: .
- משפט אוילר: אם אז . משפט פרמה הוא מקרה פרטי כאשר ראשוני.
- פתרון משוואות פולינומיאליות מעל ℤm: יהי ונרצה לפתור או לבדוק כמה פתרונות יש ל־ כאשר .
- משוואה לינארית: . קיים פתרון אם״ם . אם פתרון פרטי של אז כל הפתרונות הם כאשר , ויש פתרונות.