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