תקציר תורת המספרים, סמסטר א תשע״ג
מתוך Math-Wiki
גרסה מ־21:45, 21 בדצמבר 2012 מאת אור שחף (שיחה | תרומות) (יצירת דף עם התוכן "בקורס זה <math>\mathbb N=\{0,1,2,\dots\}</math> ו־<math>\mathbb N^+=\{1,2,\dots\}</math>. כמו כן, אלא אם צוין אחרת, <math>A^+:=A\cap\math...")
בקורס זה ו־. כמו כן, אלא אם צוין אחרת, וכל המשתנים והנעלמים שלמים.
- משפט פיאנו: קיימת קבוצה בודדה שעבורה יש פונקציה המקיימת את אקסיומות פיאנו: חח״ע, , ואם מקיימת אזי .
- מחולק לשלוש קבוצות: יחידות – , ראשוניים – ופריקים – .
- לכל ו־ קיים זוג יחיד של שארית ומנה כך ש־.
- המשפט הבסיסי של האתריתמטיקה: כל מספר ב־ ניתן לפירוק יחיד (עד כדי סדר ההכפלה) של גורמים ראשוניים.
- למת אוקלידס: יהי . אם אז .
- יהיו . נסמן אם .
- נניח ש־ ו/או שונים מ־0. אזי קיים יחיד (הנקרא מחלק משותף מקסימלי של ומסומן ) עבורו ואם כך ש־ אזי .
- אם אזי .
- .
- .
- אם זרים ו־ אזי .
- אם אזי .
- אלגוריתם אוקלידס: נניח ונרצה לחשב כאשר . אם שארית החלוקה של ב־ אזי . נמשיך כך עד שנקבל . ניתן להעזר באלגוריתם גם כדי לפתור את : נסמן ולכן בתהליך החישוב של עם האלגוריתם נקבל כאשר . לפיכך:
- משוואה דיאופנטית ב־2 משתנים: נרצה לפתור כאשר משתנים והשאר קבועים. נחלק למקרים:
- : אין פתרון.
- : ניתן לפתור ע״י אלגוריתם אוקלידס (כמפורט בהמשך הסעיף). הפתרון הכללי הוא לכל .
- : נחלק את אגפי המשוואה ב־ ונקבל משוואה חדשה מהמקרה הקודם.
- אם בפרט אז ניתן לפתור גם באמצעות אלגוריתם אוקלידס.
- נאמר ש־ חופפים מודולו (ונסמן ) אם . מגדיר יחס שקילות כאשר מחלקת השקילות של ו־ קבוצת מחלקות השקילות.
- אם ו־ אז .
- יהי . אם״ם הפיך. ניתן למצוא את ההופכי ל־ ע״י פתירת , ואז .
- .
- פונקציית אוילר היא עבורה .
- משפט אוילר: אם אז .
- מערכת מלאה מודולו m היא קבוצה עבורה . קיים כנ״ל יחיד לכל . באופן שקול, המערכת מלאה מודולו אם .
- אם מלאה מודולו , ו־ שלם אזי מלאה מודולו .
- מערכת מצומצמת מודולו m היא קבוצה כך ש־.
- אם מצומצמת מודולו ו־ אז מצומצמת מודולו .