שינויים
/* כמה מושגים בתורת המספרים */
<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>k</math> שבו <math>r_k=1</math>.
(היות ו <math>gcd(a,b)=1</math> מובטח לנו שנגיע מתישהוא ל <math>1</math>)
עד כאן החלק הקל,
עכשיו צריך להתחיל חישוב אחורה
השלב האחרון שהגענו אליו היה
<math>r_{k-2}-q_{k-1}r_{k-1} = r_k = 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-4} - q_{k-3}r_{k-3}</math> ב <math>r_{k-2}</math>
שמופיע בביטוי <math>(\ast)</math> ולקבל ביטוי מהצורה
<math>xr_{k-4}+yr_{k-3}=1</math>
עבור <math>x,y</math> כלשהם
וכן הלאה עד שנגיע לביטוי מהצורה
* אם <math>b<0</math> או <math>a<0</math> אז מוצאים <math>n',m'</math> מתאימים עבור <math>|a|,|b|</math>בשיטה שתוארה קודם
ואז <math>n'|a|+m'|b|=1</math> ואז
אם <math>b<0</math> לוקחים <math>m=-m'</math> (אחרת <math>m=m'</math>)
* אם <math>a=0</math> הסיכוי היחיד ש <math>gcd(a,b)=1</math> זה אם <math>b=1</math> או <math>b=-1</math> וזה מקרה פשוט
כנ"ל אם <math>b=0</math>
