שינויים
/* כמה מושגים בתורת המספרים */
<math>(na+mp)mod~p = 1mod~p</math>
שהופך ל <math>(na)mod~p = 1</math>
לכן <math>n~mod~p</math> הוא הפכי מתאים ל <math>a</math>.
כל זה טוב ויפה, אבל איך מוצאים את <math>n</math>?
== חישוב ההפכי ==
עבור שני מספרים <math>a,b \in \mathbb{Z}</math> כך ש <math>gcd(a,b)=1</math>
נתאר שיטה שבעזרתה ניתן למצוא את המספרים <math>n,m</math> כך ש <math>na+mb=1</math>.
נתחיל מהמקרה <math>a,b>0</math>
נניח ש <math>b>a</math>, נסמן <math>r_1=b \quad r_2 = a</math>.
(אם <math>a>b</math> אז נסמן הפוך)
נחפש את המספר <math>q_2\in \mathbb{N}</math> הגדול ביותר כך ש <math>r_1-q_2r_2>0</math>.
ונסמן <math>r_1-q_2r_2 = r_3</math>.
כעת נחפש את המספר הגדול ביותר <math>q_3\in \mathbb{N}</math> כך ש <math>r_2-q_3r_3>0</math>
ונסמן <math>r_2-q_3r_3 = r_4</math>.
נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>.
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
<math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 1</math>
אבל בשלב הקודם קיבלנו ש <math>r_{k-3} - q_{k-2}r_{k-2} = r_{k-1}</math>
לכן אפשר להציב
<math>r_{k-2}-q_{k-1}(r_{k-3} - q_{k-2}r_{k-2}) = 1</math>
שהופך ל:
<math>(1+q_{k-1}q_{k-2})r_{k-2}-q_{k-1}r_{k-3} = 1</math> <math>(\ast)</math>
אבל שוב, בשלב קודם ראינו ש
<math>r_{k-4} - q_{k-3}r_{k-3} =r_{k-2}</math>
ואפשר להציב את התוצאה ב
<math>r_{k-2}</math>
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה
<math>xr_{k-4}+yr_{k-3}=1</math>
וכן הלאה עד שנגיע לביטוי מהצורה
<math>mr_1+nr_2=1</math>
שזה בדיוק
<math>mb+na=1</math>.
אם <math>a,b<0</math> אז מוצאים <math>n,m</math> מתאימים עבור <math>|a|,|b|</math>
ואז <math>(-n)a+(-m)b=n|a|+m|b|=1</math> אז פשוט לוקחים את <math>-n,-m</math>.
== דוגמא ==
מצא את ההפכי של ב <math>\mathbb{Z}_{101}</math>.
