נמשיך כך עד שנגיע לשלב <math>k</math> שבו <math>r_k=1</math>.
(היות ו <math>gcd(a,b)=1</math> מובטח לנו שנגיע מתישהוא ל <math>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>