משפט אוילר – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
הפרדת רשויות
מ הנבואה ניתנה לשוטים, לא למשפטים
שורה 1:
'''משפט [[לאונרד אוילר|אוילר]]''' הוא הכללה של [[המשפט הקטן של פרמה]] ממספרים [[מספר ראשוני|מספרים ראשוניים]] ל[[מספר טבעי|מספרים טבעיים]] כלשהם.
 
המשפט קובע שאם n מספר טבעי, אז לכל a [[מספרים זרים|זר]] ל- n מתקיים <math>\ a^{\phi (n)} \equiv 1\pmod{n}</math>, כלומר, n מחלק את ההפרש <math>\ a^{\phi(n)}-1</math>. לדוגמא, מכיוון ש- <math>\ \phi(15)=8</math>, המשפט מנבאמוכיח ש- 15 מחלק את <math>\ 4^{8}-1=65535</math>. אחד היישומים הבולטים של המשפט הוא בשיטת ה[[הצפנה]] הקרויה [[RSA#המתמטיקה מאחורי השיטה|RSA]].
 
בנוסחה זו, <math>\phi \left(n\right)</math> (קרי: "פִי של n") היא [[פונקציה|פונקציית אוילר]] של n, השווה למספרם של המספרים הזרים ל- n וקטנים ממנו.