(הוכחה באינדוקציה על הגודל של n+k. אם n=k סיימנו, אחרת אם <math>k<n</math> אזי <math>gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k</math>)
שני מספרים טבעיים n,k נקראים '''זרים''' אם <math>gcd(n,k)=1</math>
<math>\mathbb{Z}_n</math> עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.
פונקצית אוילר <math>\phi(n)</math> היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
משפט אוילר - יהיו שני מספרים טבעיים '''זרים''' <math>a<n</math>. אזי <math>a^{\phi(n)}\equiv 1</math> מודולו n.
===הרצאות 6-7 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), חתימה; פרק 7 מ[http://abstract.ups.edu/aata/ הספר]===