$\Theta \rho ϵ\eta \Pi \alpha \tau \pi$

Define $S:=\{am+bn:m,n\in \mathbb{Z}\text{ and }am+bn>;0\}$, we first note that $S$ cannot be empty. The only way it could be empty would be if that given any choice of $m,n$ we have $am+bn<;0$, but if that's the case we can always see that $-(am+bn)>;0$ and note that $-(am+bn)=a(-m)+b(-n)$, which shows that there is an element in $S$.

Since $S\subseteq {\mathbb{N}}_0$, the well ordering principle tells us that there is some smallest element of $S$, say $d=aj+bk$. We will prove that $\gcd (a,b)=d$.

By the quotient remainder theorem, we have some $q,r$ such that $a=qd+r$ where $0\le r<;d$, from here we can see that $$\begin{array}{cc}r& amp;=a-qd\\ & amp;=a-q(aj+bk)\\ & amp;=a(1-qj)+b\left(qk\right)\end{array}$$ at this point in time if $r>;0$, then we would have a contradiction because $r$ would be a value smaller than $d$ that is an element of $S$, but we assumed that $d$ was the smallest such element. Therefore, the only way forward is that $r=0$

If $r=0$, then $a=qd$ meaning that $d$ divides $a$, by copying the above text and replacing the variable $a$ with $b$ we obtain a proof that $d$ divides $b$ as well. To complete showing that $d=\gcd (a,b)$ we need to prove that $d$ is the smallest divisor.

Suppose that $m$ is another common divisor of $a,b$, then we have $k_a,k_b\in \mathbb{Z}$, such that $a=k_{a}m$ and $b=k_{b}m$, from $d$'s definition we see $d=aj+bk=\left(k_{a}m\right)j+\left(k_{b}m\right)k=m(k_{a}j+k_{b}k)$, this shows that $m|d$ so that $m\le d$ showing that $d$ is the largest divisor and we conclude $d=\gcd (a,b)$

The gcd is a linear combination, and therefore $ax+ny=1$ so that $abx+nby=b$ since $n|ab$ then we have some $k\in \mathbb{Z}$ such that $ab=nk$ therefore $nkx+nby=b$ so that $n(kx+by)=b$ so therefore $n|b$

$⟹$ Suppose we have a $d\in \mathbb{Z}$ such that $d|a,b$ then we know that $d|ax+by=1$, therefore $d=\pm 1$, therefore by definition $\gcd (a,b)=1$. $⟸$ We know this because gcd is a linear combination

Suppose $r=\frac{a}{b}\in \mathbb{Q}$ and let $d=\gcd (a,b)$ and consider $$\frac{a}{b}=\left(\frac{\frac{1}{d}}{\frac{1}{d}}\right)\left(\frac{a}{d}\right)=\frac{\frac{a}{d}}{\frac{b}{d}}$$ and since we know that $\gcd (\frac{a}{d},\frac{b}{d})=1$ we've proven the statement true

$\subseteq$ Suppose $d|a,b$ therefore $d|a+ka$ as needed. $\supseteq$ now suppose that $d|a,b+ka$ since $d|a$ then $d|ka$ and therefore $d|(b+ka)-ka=b$ therefore $d\in \mathrm{cd}(a,b)$

For any $X\subseteq Y\subseteq \mathbb{Z}$ then $\max \left(X\right)<\max \left(Y\right)$ therefore we have $$\gcd (a,b)=\max (\mathrm{cd}(a,b))\le \max (\mathrm{cd}(p,q))=\gcd (p,q)$$ so that $\gcd (a,b)\le \gcd (p,q)$ as needed.

Suppose that there existed some $d\in {\mathbb{N}}_2$ such that $d|n$ and $d|n+1$ then we would have $d|n+1-n=1$ which implies that $d=\pm 1$ which is a contradiction, thus the only divisor of $n$ and $n+1$ is one, so that $\gcd (n,n+1)=1$

The gcd is a linear combintion of $a,b$ so $ax+by=1$ for some $x,y\in 𝕫$ but then $$acx+bcy=c$$ but recall that $a|c$ and $b|c$ so we have $k_a,k_b\in \mathbb{Z}$ such that $c=k_{a}a$ and $c=k_{b}b$ subbing each of these equations into the above equation we have $$a\left(b{k}_b\right)x+b\left(a{k}_a\right)y=c$$ so therefore $\left(ab\right)(k_{b}x+k_{a}y)=c$ so that $ab|c$ as needed.

Recall this, therefore we can show that $\mathrm{cd}(a,b)\subseteq \mathrm{cd}(ak,b)$ thus $\gcd (a,b)\le \gcd (ka,b)$

Let $g:=\gcd (b,d)$ clearly $g|d$ and since $d|a$ then $g|a$, also we know that $g|b$ and therefore $g$ is a common divisor of $a,b$ and therefore $g=1$, as needed.

We have some $x_1,x_2,y_1,y_2$ such that $$a{x}_1+b{y}_1=1=a{x}_2+c{y}_2$$ So then $$\begin{array}{cccc}& 1& amp;=(a{x}_1+b{y}_1)(a{x}_2+c{y}_2)& \text{<span class="tml-eqn"></span>}\\ & & amp;=a^2{x}_1{x}_2+a{x}_{1}c{y}_2+b{y}_{1}a{x}_2+bc{y}_1{y}_2& \text{<span class="tml-eqn"></span>}\\ & & amp;=a(a{x}_1{x}_2+x_{1}b{y}_2+b{y}_1{x}_2)+bc\left(y_1{y}_2\right)& \text{<span class="tml-eqn"></span>}\end{array}$$ so therefore $\gcd (a,bc)=1$