שינויים

* אם <math>a,b</math> זרים ו־<math>a\mid bc</math> אזי <math>a\mid c</math>.

* אם <math>\forall i:\ k_i,m_i\in\mathbb N</math> וה־<math>p_i</math> שונים זה מזה אזי <math>\left(\prod_i p_i^{k_i},\prod_i p_i^{m_i}\right)=\prod_i p_i^{\min\{k_i,m_i\}}</math>.

* '''אלגוריתם אוקלידס:''' נניח <math>b\ne0</math> ונרצה לחשב <math>(a,b)</math> כאשר <math>a>b</math>. אם <math>r</math> שארית החלוקה של <math>a</math> ב־<math>b</math> אזי <math>(a,b)=(b,r)</math>. נמשיך כך עד שנקבל <math>(x,0)=x</math>. ניתן להעזר באלגוריתם גם כדי לפתור את <math>ax+by=(a,b)</math>: נסמן <math>r_{-1}=a, r_0=b</math> ולכן בתהליך החישוב של <math>(a,b)</math> עם האלגוריתם נקבל <math>\forall0\le i\le k:\ r_{i-1}=r_iq_{i+1}+r_{i+1}</math> כאשר <math>r_{k+1}=(a,b)</math>. לפיכך:{{left|<math>\begin{align}r_{k+1}&=r_{k-1}-r_kq_{k+1}\\&=r_{k-1}-(r_{k-2}-r_{k-1}q_k)q_{k+1}\\&=r_{k-1}(1+q_kq_{k+1})-r_{k-2}q_{k+1}\\&=\dots\\&=r_0y-r_{-1}(-x)\\&=ax+by\end{align}</math>}}

* נאמר ש־<math>a,b</math> חופפים מודולו <math>m>1</math> (ונסמן <math>a\equiv b\pmod m</math>) אם <math>m\mid a-b</math>. <math>\equiv</math> מגדיר יחס שקילות כאשר <math>\bar a=[a]=a+m\mathbb Z</math> מחלקת השקילות של <math>a</math> ו־<math>\mathbb Z_m</math> קבוצת מחלקות השקילות.