שינויים

***נניח <math>b=q_1a+r_1=q_2a+r_2</math>.

***לכן <math>(q_1-q_2)a=r_2-r_1</math>.

***לכן <math>q_1-q_2=0</math> כלומר <math>q_1=q_2</math> ולכן גם <math>r_1=r_2</math>.

*המספר q נקרא '''מנת''' החלוקה והמספר r נקרא '''שארית''' החלוקה.

**<math>ab=(q_an+r_a)(q_bn+r_b)=(q_aq_bn+r_aq_b+q_ar_b)n+r_ar_b</math>

*מסקנה: באותם תנאים, לכל k טבעי מתקיים כי <math>a^k\equiv r_a^k \mod n</math>.

===המחלק המשותף הגדול ביותר===