Facts

Fact 1   If $a\equiv b\pmod{m}$ and $b\equiv c\pmod{m}$, then $a\equiv c\pmod{m}$.

By definition of mod, $a=b+mr_0$ and $b=c+mr_1$ for some $r_0,r_1\in{\bf Z}$. So, by substitution, $a=c+mr_1+mr_0$, and by the distributive property, $a=c+m(r_0+r_1)$, so $a\equiv c\pmod{m}$.

Fact 2   If $a,b,c\in{\bf N}$ and $a\vert b$ and $b\vert c$, then $a\vert c$.

By definition of divides, $c=bq$ and $b=ar$ for some $q,r\in{\bf N}$. Substituting, we find that $c=arq$, so $a\vert c$ by the definition of divides.

Fact 3   If $a>0$, $b>0$, and $a\vert b$, then $a\leq b$.

$b=aq$ for some integer $q$ by definition of $a\vert b$. Since $a>0$ and $b>0$, then $q>0$. If $q=1$, then $b=a$, so $a\leq b$. Otherwise, $q>1$, so $q-1>0$, so we can subtract $a$ and factor on the right to get $b-a=a(q-1)$. Since $a(q-1)\in{\bf N}$, then $a<b$ by definition, so $a\leq b$.

Fact 4   Let $a$ and $b$ be integers, with $b>0$. Then there exist unique integers q and r such that $a=bq+r$, where $0\leq r<b$. This is called the division algorithm.

Let $S$ be the set of all numbers of the form $a-bx$, where $x$ is an integer, such that $a-bx\geq 0$. If $a=0$, then let $x=0$, so $S$ has an element. If $a>0$, then let $x=0$, so S has an element. If $a<0$, then let $x=a$, so $a-bx=a-ba=a(1-b)$. Since $b>0$, then $-b<0$, so $1-b\leq 0$. If $1-b=0$, then $a-bx=0$, so $S$ has an element. If $1-b<0$, then $a(1-b)>0$ (since $a<0$), so $S$ has an element. So, $S$ is not empty. Now, if $0\in S$, then $a-bx=0$ for some $x\in{\bf Z}$, and we can let $q=x$ and $r=0$, so $a=bq+r$ where $0\leq r<b$, so we are done. So, the other case we have to consider is if $0\notin S$. Then $S\subseteq{\bf N}$, so by WOP, S has a least element $r_0$. Since $r_0\in S$, we know that $r_0\geq 0$. So, we need to show that $r_0<b$. Assume that $r_0\geq b$ and try to arrive at a contradiction (this is called proof by contradiction). $r_0=a-bx$ for some $x$ since $r_0\in S$. Let $r_1=a-b(x+1)$. So $r_1=a-bx-b=r_0-b$. Since $r_0>b$, $r_0-b>0$ (by definition of $a<b$). So $r_1>0$, and $r_1=a-b(x+1)$, so $r_1\in S$. But $r_1 = r_0-b$, so $r_1<r_0$. However, this is not true, since $r_0$ is the least element in $S$. So, we have arrived at a contradiction, so our hypothesis was incorrect - so $r_0\not\geq b$, so $r_0<b$.

Fact 5   Let $d=(a,b)$. Then there exist integers $x$ and $y$ such that $ax+by=d$.

Let $S$ be the set of all numbers that can be expressed as $ax+by$ such that $x$ and $y$ are integers and $ax+by>0$. $S$ is not empty, since we can choose $x=a$ and $y=b$, so $a^2 + b^2>0$, so $a^2 + b^2$ is in $S$. Since $S\subset N$, by WOP $S$ has a least element, which we will call $w$. If we can show that $w$ is the GCD of $a$ and $b$, then we will be done, because $w\in S$, so $w=ax+by$ for some integers $x$ and $y$. Now we will show that $w$ is the GCD of $a$ and $b$ by using the definition of GCD.

Part 1: WTS: $w\vert a$ and $w\vert b$.

By the division algorithm, $a=wq+r$ for some $q$ and $r$ in ${\bf Z}$ such that $0\leq r<w$. We want to show that $r=0$, so we will assume that $r\neq 0$ and try to reach a contradiction. Since $r\neq 0$ and $0\leq r<w$, we know that $0<r<w$. We know $r=a-wq$ (since $a=wq+r$). Since $w\in S$, we can find an $x_0$ and a $y+0$ in ${\bf Z}$ such that $w=ax_0+by_0$. We can substitute in to get $r=a-(ax_0 + by_0)q$, or $r=a(1-x_0q)+b(-y_0 q)$, which means that $r\in S$. But, $r<w$, and this contradicts the fact that $w$ is the least element in $S$. So, we conclude that $r=0$, so $a=wq$, so $w\vert a$. Similarly, $w\vert b$.

Part 2: WTS: If $c\vert a$ and $c\vert b$ then $c\leq w$.

By definition of divides, $a=cu$ and $b=cv$ for some $u$ and $v$ in ${\bf Z}$. Since $w=ax_0+by_0$, we can substitute to get $w=cux_0+cvy_0$, so $w=c(ux_0+vy_0)$, so $c\vert w$ (by definition of divides), so by Fact 1, $c\leq w$.

Fact 6   If there exist integers $x$, $y$ such that $ax+by=c$, then $(a,b)\vert c$.

Let $d=(a,b)$, so $a=da_1$ and $b=db_1$. So, $da_1x+db_1y=c$, so $d(a_1x+b_1y)=c$, so $d\vert c$ by definition of divides, so $(a,b)\vert c$.

Fact 7   If $(a,nb)=1$, then $(a,b)=1$.

Since $(a,nb)=1$, there exist integers $x$, $y$, such that $ax+nby=1$. We can write this as $ax+b(ny)=1$, so $(a,b)\vert 1$ (by Fact 6), and since $(a,b)>0$, then $(a,b)=1$.

Fact 8   If $b\vert a$ and $c\vert a$ and $(b,c)=1$, then $bc\vert a$.

We know $a=bq$ and $a=cr$ for some $q,r\in{\bf Z}$. Since $(b,c)=1$, then $bx+cy=1$ for some $x,y\in{\bf Z}$ by Fact 5. We can multiply by $a$ to get $abx+acy=a$. We can substitute to get $crbx+bqcy=a$, and factor to get $bc(rx+qy)=a$, so $bc\vert a$ by definition of divides.

Fact 9   If $a\vert bc$ and $(a,b)=1$ then $a\vert c$.

Since $a\vert bc$, we know $bc=aj$ for some $j\in{\bf Z}$. $(a,b)=1$, so $ax+by=1$ for some $x,y\in{\bf Z}$. Multiply by c to get $acx+bcy=c$, substitute to get $acx+ajy=c$, and factor to get $a(cx+jy)=c$. So, by definition of divides, $a\vert c$.

Fact 10   If $(a,b)=1$, then $(a,a+b)=1$.

There exist integers $x$, $y$ such that $ax+by=1$ by Fact 5, so $ax+by-ay+ay=1$, so $ax-ay+by+ay=1$, so $a(x-y)+(b+a)y=1$, so $(a,a+b)\vert 1$ (by Fact 6), so $(a,a+b)=1$.

Fact 11   If $(a,c)=1$ and $(b,c)=1$, then $(ab,c)=1$.

We will prove this by contradiction. Assume for the sake of contradiction that there exists a $d\in{\bf N}$ such that $d>1$ and $d\vert ab$ and $d\vert c$. Now, assume for the sake of contradiction that $(d,a)=e$, where $e\in{\bf N}$ and $e>1$. Then $e\vert a$ and $e\vert d$. Since $d\vert c$, by Fact 2 we can say that $e\vert c$. So, since $e\vert a$ and $e\vert c$ and $e>1$, this is a contradiction to $(a,c)=1$, and we conclude that $(d,a)=1$. Now, since $d\vert ab$, by Fact 9, $d\vert b$. But, since we know that $d\vert c$, this is a contradiction to $(b,c)=1$. So, $d=1$, and we conclude that $(ab,c)=1$.

Fact 12   If $(a,b)=1$, then $(a^n,b)=1$ for all $n\in{\bf N}$.

This will be proven by weak mathematical induction on $n$.

Base Case: Want To Show(WTS): $(a^1,b)=1$.

Since $a^1=a$ and $(a,b)=1$, then $(a^1,b)=1$.

Induction Step: Assume $(a^n,b)=1$.

WTS: $(a^{n+1},b)=1$.

Since we know that $(a,b)=1$ and $(a^n,b)=1$, we can apply Fact 11 to say that $(a*a^n,b)=1$, or $(a^{n+1},b)=1$.

Fact 13   If $(a,m)=1$, then there exists some $b\in{\bf Z}$ such that $ab\equiv 1\pmod{m}$.

There exists $x,y\in{\bf Z}$ such that $ax+my=1$ (by Fact 5), so $ax=1-my$, so $ax\equiv 1\pmod{m}$. $x$ is the integer we were looking for, so we are done.

Fact 14   If $ab\equiv 0\pmod{m}$, and $(a,m)=1$, then $b\equiv 0\pmod{m}$.

By definition of mod, $m\vert ab$, and since $(a,m)=1$, then $m\vert b$ (by Fact 9), so $b\equiv 0\pmod{m}$, and we are done.

Fact 15   If $a\vert b$ and $b\vert a$ and $a,b>0$ then $a=b$.

Since $a\vert b$, then $b=ax_0$ for some $x_0\in{\bf Z}$. Since $a,b>0$, then $x_0>0$. Since $b\vert a$, then $a=bx_1$ for some $x_1\in{\bf Z}$. Since $a,b>0$, then $x_1>0$. Substituting, we find that $b=bx_0x_1$, or $1=x_0x_1$. Since $x_0,x_1>0$, it follows that $x_0=1$ and $x_1=1$. Substituting, we find that $a=b$.

Fact 16   If $a\equiv b\pmod{xy}$ then $a\equiv b\pmod{x}$.

Since $a\equiv b\pmod{xy}$, then $a=b+xyz$, for some $z\in{\bf Z}$. So, $a=b+x(yz)$, so $a\equiv b\pmod{x}$ by definition of mod.