Proof.

•

Reflexivity: Let \(a\) be an integer, then \(a=a\) mod\(_n\) since \(n\) divides \(a - a = 0\).

•

Symmetry: Let \(a\) and \(b\) be integers such that \(a=b\) mod\(_n\) . Then \(n\) divides \(a - b\). But this implies \(n\) divides \(b-a\). Thus \(b = a\) mod\(_n\).

•

Transitivity: Let \(a = b\) mod\(_n\, \cdot \, b = c\) mod\(_n\). We need to show that \(a = c\) mod\(_n\). Now, \(a = b\) mod\(_n\) implies \(n\) divides \(a - b\, ,\,\, b = c\) mod\(_n\, \implies n\) divides \(b-c\) i.e \(\, a - b = kn\) for some \(k\in \mathbb {Z}\) and \(b - c = hn\) for some \(h\in \mathbb {Z}\).
\(\therefore \, a - c = kn + hn = (k+h)\, n).\) Thus \(a-c\) is divisible by \(n\, \implies \, a = c\) mod\(_n\).

□

Proof. We first show that \(q\) and \(r\) do indeed exist and that they are unique. Consider the set \(S=\big \{a - bt\, :\, t\in \mathbb {Z}\big \}\). Let \(S'\) denote the set of non-negative elfs of \(S\). Clearly \(S' \neq \emptyset \), since if \(a\geq 0\), then \(t = 0\) yields \(a\in S'\). If \(a<0\), then \(t=a\), we get \(a - ba\in S\). But \(a - ba = a(1 - b)\geq 0\) because \(a < 0\) and \(1 - b\leq 0\). i.e \(a - ba\in S' \, \implies \neq \emptyset \).
Let \(r\) denote the least integer in \(S'\). If \(0\in S'\), then \(r = 0\), otherwise apply the well ordering principle least integer principle. Let \(q\) denote the allowed value of \(t\) so that \(a - bq = r\, \implies a = bq + r\).
We show that this is a unique representation. Suppose \(a = bq_1 + r_1\) and \(a = bq_2 + r_2\hspace {0.3cm} 0\leq r_1\, ,\, r_2 < b\). We need to show that \(q_1 = q_2\, , \, r_1 = r_2\). Thus we have \(\, bq_1 + r_1 = bq_2 + r_2 \, \implies b(q_1 - q_2) = r_2 - r_1\). Thus \(b\) divides the difference \(r_2 - r_1\). But \(0\leq r_1 < b\) and \(0\leq r_2 < b\). \(\, - b < r_2 - r_1 < b\). The only multiple of \(b\) between \(-b\) and \(b\) is \(0\) thus \(r_2 - r_1 = 0\, \implies r_2 = r_1\). This implies \(b(q_1 - q_2) = 0\) but \(b\neq 0\, \implies q_1 - q_2 = 0\) so that \(q_1 = q_2\).
This proves the uniqueness.

□

Proof. If \(a\in \mathbb {Z}\), then by the division algorithm there exist \(q\, , \, r \) such that \( a = nq + r\, \, 0\leq r < n\). From this, \(a - r = nq\) so that \(n\) divides \(a - r\) and \(a = r\) mod\(_n\). Thus \(a\) is congruent to atleast one of the integers \(0\, , \, 1\, ,\, 2\, \cdots \cdots \, n-1\). We then show that such an \(r\) is unique.
Suppose there is another \(r'\) such that \(a = r'\) mod\(_n\,\), \(\,\, 0\leq r' <n\). Therefore \(a - r' = nt\, , \, t\in \mathbb {Z} \, \implies a = nt + r'\, , \, 0 \leq r' <n\). Thus by the unique representation (from the division algorithm) \(r = r'\). This completes the proof.

□

Proof. Let \(S = \left \{ax+by : x,y\in \mathbb {Z}\right \}\cap \mathbb {Z}^{+}\). Since \(a\) and \(b\) are not both zero, \(S\) is non-empty — it contains \(a^{2}+b^{2}\) — so by well-ordering it has a least element \(d = ax_0+by_0\).

\(d\) divides \(a\): dividing, \(a = qd + r\) with \(0\leq r<d\), and \[r = a - qd = a\left (1-qx_0\right ) + b\left (-qy_0\right )\] is of the same form. If \(r>0\) it would lie in \(S\) and be smaller than \(d\), so \(r=0\). The same argument gives \(d\mid b\), so \(d\) is a common divisor.

Any common divisor \(c\) of \(a\) and \(b\) divides \(ax_0+by_0 = d\), so \(c\leq d\). Hence \(d\) is the greatest common divisor, and it is unique because two positive integers dividing each other are equal. □

Solution.

Solution.