שינויים
/* המחלק המשותף הגדול ביותר */
===המחלק המשותף הגדול ביותר===
*לכל שני מספרים טבעיים <math>k<n</math> מתקיים כי <math>gcd(n,k)=gcd(n-k,k)</math>
**נוכיח שכל מספר שמחלק את <math>n,k</math> מחלק גם את <math>n-k,k</math> וההפך, ולכן הגדול ביותר הוא אותו האחד.
**אם <math>a</math> מחלק את <math>n,k</math> אזי <math>n=qa,k=ta</math>, לכן <math>n-k=(q-t)a</math>.
**אם <math>a</math> מחלק את <math>n-k,k</math> אזי <math>n-k=qa,k=ta</math> ולכן <math>n=(q+t)a</math>.
*לכל שני מספריים טבעיים <math>n,k</math> קיימים מספרים שלמים <math>a,b</math> כך ש <math>an+bk=gcd(n,k)</math>
**עבור <math>n=k=1</math> מתקיים כי <math>1\cdot 1 + 0\cdot 1 = 1 = gcd(הוכחה באינדוקציה על הגודל של 1,1)</math>.**נניח שהטענה נכונה לכל <math>n+k<m</math> נוכיח שהיא נכונה עבור <math>n+k=m</math>. **אם <math>n=k סיימנו</math> אזי <math>1\cdot n + 0\cdot k = n =gcd(n, n)=gcd(n,k)</math>.**אחרת , אם <math>n>k<n</math> אזי מתקיים כי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>).**שימו לב שהנחת האינדוקציה התקיימה עבור הזוג <math>n-k,k</math>.
*עבור מספר טבעי <math>1<n</math> קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית '''חבורת אוילר''' ומסומנת <math>U_n</math>.
*<math>\mathbb{Z}_n</math> עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.
===פונקצית אוילר, משפט אוילר והמשפט הקטן של פרמה===
