== כמה מושגים בתורת המספרים ==
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> אומרים ש <math>a</math> מחלק את <math>b</math> (ומסמנים <math>a|b</math>)
אם קיים <math>c\in \mathbb{Z}</math> כך ש <math>ac=b</math>.
'''הגדרה''': יהיו <math>a,b\in \mathbb{Z}</math> המחלק המשותף המירבי של <math>a,b</math> (מסומן <math>gcd(a,b)</math>) הוא המספר הגדול ביותר שמחלק גם את <math>a</math> וגם את <math>b</math>.
כלומר <math>gcd(a,b)=max\{g\in \mathbb{Z}\mid g|a\quad g|b\}</math>
ההגדרה הזאת בעייתית כאשר <math>a=b=0</math> במצב זה אומרים ש <math>gcd(0,0)=0</math>.
נשים לב שאם <math>p</math> מספר ראשוני ו <math>1\geq a\geq p-1</math> אז <math>gcd(a,p)=1</math>
'''משפט''': יהיו <math>a,b\in \mathbb{Z}</math> ו <math>g=gcd(a,b)</math> אזי קיימים <math>m,n\in\mathbb{Z}</math> כך ש <math>na+mb=g</math>.
הערה: נשים לב כי באמצעות משפט זה ניתן להוכיח את קיום ההופכי ב <math>\mathbb{Z}_p</math>, כי אם <math>0\neq a\in\mathbb{Z}_p</math> אז
<math>gcd(a,p)=1</math> לכן קיימים <math>m,n</math> כך ש <math>na+mp=1</math>.
אם נפעיל <math>mod~p</math> על שני צידי המשוואה הזאת נקבל
<math>(na+mp)mod~p = 1mod~p</math>
שהופך ל <math>(na)mod~p = 1</math>
לכן <math>n~mod~p</math> הוא הפכי מתאים ל <math>a</math>.