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