פונקציית אוילר
פונקציית אוילר נקראת על שם אוילר. מסמנים אותה φ (פי). φ(n) סופר כמה מספרים קטנים מ‑n הם "זרים" לו. זר אומר שאין להם מחלק משותף עם n חוץ מ‑1. לדוגמה: φ(5)=4 כי 1,2,3,4 זרים ל‑5. φ(6)=2 כי רק 1 ו‑5 זרים ל‑6. אם p הוא מספר ראשוני, אז φ(p)=p−1. אם יש חזקה של ראשוני p^s נקבל φ(p^s)=p^s−p^{s−1}. הפונקצ...
צפיפות דיריכלה
צפיפות דיריכלה היא דרך להראות כמה גדולה קבוצה בתוך קבוצה אחרת. זהו כלי במתמטיקה שנמצא בשימוש בתורת המספרים, חקר המספרים השלמים. דיריכלה השתמש בזה כדי להראות שיש אין סוף מספרים ראשוניים בסדרות מסוימות. סדרה חשבונית היא סדרת מספרים כמו a, a+n, a+2n, ... דיריכלה הראה שאם a ו-n אינם מתחלקים יחד, אז בין ...
חבורת אוילר
חבורת אוילר היא קבוצת מספרים שלא מתחלקים ב-n. עושים בהם כפל ושומרים רק את השארית אחרי חילוק ב-n. את הקבוצה כותבים U_n. אם שני מספרים לא מתחלקים ב-n, גם המכפלה שלהם לא תתחלק ב-n. לכן הקבוצה סגורה לכפל. לכל מספר כזה יש גם מספר אחר שמכפיל אותו ומקבל 1 בשארית. המספר הזה נקרא הופכי. מספר האיברים בקבוצה...
פונקציית מביוס
פונקציית מביוס נקראת μ(n). זוהי חוק שמקבל מספר טבעי ומחזיר מספר אחר. אם ל-n יש גורם ריבועי, כלומר מספר שהוא כפולה של מספר בעצמו, אז μ(n)=0. אם אין כזה גורם, סופרים כמה ראשוניים שונים מחלקים את n. אם המספר הזה זוגי μ(n)=1. אם הוא אי־זוגי μ(n)=-1. למשל μ(1)=1 ו-μ של ראשוני הוא -1. (ראשוני הוא מספר ...
חבורה ציקלית
חבורה ציקלית היא קבוצה שמתקבלת מאיבר אחד בלבד. האיבר הזה נקרא יוצר. כל איבר בחבורה הוא חזרה על אותו יוצר. דוגמה: כל המספרים השלמים עם חיבור יוצרים חבורה. הירידה או העלייה במספרים נעשית על ידי הוספת 1 שוב ושוב. חבורה עם n איברים היא הקבוצה 0 עד n−1 בחיבור שמחזיר רק את השארית. בחבורה יש כמה יוצרים ל...
טור דיריכלה
טור דיריכלה הוא סכום של ביטויים מהצורה a_n לחלק ב-n^s. a_n הם מספרים קבועים. s הוא מספר מיוחד שנקרא מרוכב. טורים כאלה נראו כבר במאה ה-17. אוילר קישר אותם למספרים ראשוניים. דיריכלה השתמש בהם כדי להראות שיש אינסוף מספרים ראשוניים ברשימות מסוימות של מספרים (רשימה עם הפרש קבוע בין האיברים). הדוגמה המפ...
חשבון מודולרי
חשבון מודולרי עובד עם שאריות. שארית היא מה שמתקבל אחרי חילוק. לדוגמה, בחלוקה ב-7, 11 נותן שארית 4, לכן 5+6 בחשבון זה שווה 4. אם ההפרש בין שני מספרים מתחלק ב-n, הם נחשבים שקולים מודולו n. אפשר לייצג כל קבוצה כ־0 עד n-1. חיבור וכפל במודולו נשמרים בין שקולים. זה אומר שניתן לחשב חיבור וכפל כמו תמיד, ו...
מספרים זרים
מספרים נקראים זרים אם אין להם אף מספר ראשוני משותף חוץ מ־1. מספר ראשוני הוא מספר שמתחלק רק ב־1 ובעצמו. למשל 1496 ו־19695 אינם חולקים אף ראשוני. שלושה מספרים יכולים להיות זרים יחד גם אם זוגות מהם לא זרים. דוגמה פשוטה: 6, 10 ו־15. אם אפשר להכפיל ולחבר שני מספרים ולקבל 1, אז הם זרים. יש שיטה בשם אלגור...
משפט אוילר
משפט אוילר אומר רעיון פשוט וחזק בעשרון המודולרי. אוילר פרסם אותו ב-1744. הוא חשוב גם בהצפנה, למשל ב-RSA. אם a ו-n "זרים" זה לזה, אז a בחזקת φ(n) נותן תוצאה של 1 מול n. "זרים" פירושו שאין להם מחלק משותף חוץ מ-1. φ(n) (פי של n) הוא כמה מספרים קטנים מ-n הם זרים ל-n. דוגמה קטנה: ל-n=15 יש φ(15)=8. לכן...