|
'''משפט [[לאונרד אוילר|אוילר]]''' הוא הכללה של [[המשפט הקטן של פרמה]] ממספרים [[מספר ראשוני|מספרים ראשוניים]] ל[[מספר טבעי|מספרים טבעיים]] כלשהם. נסמן ב- <math>\phi \left(n\right)</math> (קרי: "פִי של n" (פ' רפה), או "[[פונקציה|פונקציית]] אוילר של n") את מספר המספרים הטבעיים הקטנים מ-n נתון, ו[[מספרים זרים|זרים]] ל-n (זוהי דוגמא חשובה ל[[פונקציות אריתמטיות|פונקציה אריתמטית]]).
'''משפטהמשפט אוילר''' אומרקובע שאם 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 וקטנים ממנו.
==חישוב הפונקציה של אוילר==
ישנן שתי דרכים לחישוב הפונקציה. האחת:
<math>\ \phi (n) = n(1-{1\over p_1})(1-{1\over p_2})...(1-{1\over p_k})</math>
כאשר <math>\ p_1,p_2,...,p_k</math> הם הגורמים הראשוניים השונים של n. לדוגמא <math>\ \phi(45)=45(1-\frac{1}{3})(1-\frac{1}{5})=24</math>.
דרך נוספת לחישוב היא הדרך הבאה:
<math>\ \phi (n) = (p_1^{s_1}-p_1^{s_1-1})(p_2^{s_2}-p_2^{s_2-1})...(p_K^{s_K}-p_K^{s_K-1})</math>
כש- <math>\ n=p_1^{s_1}\dots p_k^{s_k}</math>.
[[הוכחה|נוכיח]] ששתי הנוסחאות מביאות לאותה תוצאה.
מהגדרת הסדרות <math>\ p</math> ו-<math>\ s</math>, ברור כי <math>\ n=p_1^{s_1}p_2^{s_2}...p_k^{s_k}</math>. לפיכך, ניתן לכתוב את דרך החישוב הראשונה כך:
<math>\ p_1^{s_1}(1-{1\over p_1})p_2^{s_2}(1-{1\over p_2})...p_K^{s_k}(1-{1\over p_k})</math>
כך שבעצם תוצאת הפונקציה היא מכפלה של סדרת איברים, מהצורה הבאה:
<math>\ p_m^{s_m}(1-{1\over p_m})=(p_m^{s_m}-{p_m^{s^m}\over p_m})=(p_m^{s_m}-p_m^{s_{m-1}})</math>
כפי שאנו רואים במשוואה, גם דרך החישוב השנייה היא מכפלת איברי אותה הסדרה.
==הוכחת המשפט==
ו-<math>\ k</math>, ע"פ הגדרתו, הוא מספר השאריות הזרות ל-<math>\ n</math> בחילוק ל-
<math>\ n</math>. כלומר - הוא שווה ל-<math>\ \phi \left(n\right)</math>! ומכאן נובע משפט אוילר.
[[קטגוריה:תורת המספרים]]
| 