\newlec

\thm (Euclid's Theorem) (INF P) There exists infinitely many primes.
\vskip1em
\pf Assume towards a contradiction that there exists finitely many primes, say $p_{1}, p_{2}, ..., p_{n}$. Consider the number
\[
N = 1 + \prod_{i=1}^{n}p_{i}
\]
By the Fundamental Theorem of Arithmetic (UFT), $N$ can be written as a product of primes. In particular, there exists a prime $p \mid N$ by the Generalized Euclid's Lemma. Since we have only finitely many primes, $p = p_{1}$ for some $1 \leq i \leq n$. Since $p \mid N$ and $\left. p ~\middle| ~\displaystyle  \prod_{i=1}^{n}p_{i} \right.$, we conclude by Divisibility of Integer Combinations that 
\begin{align*}
\left. p  ~\middle| ~\left(N - \prod_{i=1}^{n}p_{i}\right) \right. = 1
\end{align*}
This is a contradiction since no prime divides $1$ (you could use Bounds by Divisibility since primes are bigger than 1). Hence, there must be infinitely many primes.\qed 

\vskip1em
To complete the gaps in the previous proofs, we need to talk about the two forms of Euclid's Lemma. To do this, we will need to talk about greatest common divisors and more importantly, B\'{e}zouts Lemma.
\ic{This is the 7-10 minute mark}
\textbf{Greatest Common Divisors}
\ic{Arguably, this is the toughest portion of the course. These arguments for gcds are often tricky and counter intuitive and take a bit of practice before mastering. }

\noindent As an exercise, let's list the divisors of $84$:
\[
\pm1, \pm2, \pm3, \pm4, \pm6, \pm7, \pm12, \pm14, \pm21, \pm28, \pm42, \pm81
\]
Divisors of 120:
\[
\pm1, \pm2, \pm3, \pm4, \pm5, \pm6, \pm8, \pm10, \pm12, \pm15, \pm20, \pm24, \pm30, \pm40, \pm60, \pm120
\]
Hence the greatest common divisors of $84$ and $120$ is $12$.
\vskip1em
\defn The \textit{greatest common divisors} of integers $a$ and $b$ with $a \neq 0$ or $b \neq 0$ is an integer $d > 0$ such that 
\begin{enumerate}
\item $d \mid a$ and $d \mid b$
\item If $c \mid a$ and $c \mid b$, then $c \leq d$
\end{enumerate}
We write $d = \gcd(a,b)$.
\vskip1em
\note 
\begin{enumerate}
\item $\gcd(a,a) = |a| = \gcd(a,0)$
\item Define $\gcd(0,0) = 0$. Note that $\gcd(a,b) = 0 \Leftrightarrow a=b=0$
\item \exr $\gcd(a,b) = \gcd(b,a)$
\end{enumerate}

\ic{This is the 20 minute mark}
\newpage
\hdc
\ex Prove that $\gcd(3a+b,a) = \gcd(a,b)$ using the definition directly.
\vskip3em
\pf. Let $d = \gcd(3a+b,a)$ and $e = \gcd(a,b)$. Then by definition, $d \mid (3a+b)$ and $d \mid a$. By Divisibility of Integer Combinations, 
\[
d \mid (3a+b)-3a = b
\]
Since $e$ is the maximal divisor of $a$ and $b$, we have that $d \leq e$.
\vskip1em
Now, since $e \mid a$ and $e \mid b$, Divisibility of Integer Combinations gives us that $e \mid (3a + b)$. Since $d$ is maximal, $e \leq d$. Hence $d=e$. \qed
\ic{This is the 30 minute mark}
\newpage

\claim $\gcd(a,b)$ exists.
\vskip1em
\pf Suppose that $a \neq 0$ or $b \neq 0$. Clearly $1 \mid a$ and $1 \mid b$ so a divisor exists.
\vskip1em
To show there is a greatest common divisor, it suffices to show that there is an upper bound on common divisors of $a$ and $b$. If $d$ is a positive integer such that $d  \mid a$ and $d \mid b$, then Bounds by Divisibility states that $d \leq |a|$ and $d \leq |b|$. Hence,
\[
1 \leq d \leq \min\{|a|,|b|\}
\]
Since the range on divisors is bounded, there must be a maximum. \qed
\vskip1em
\claim $\gcd(a,b)$ is unique.
\vskip1em
\pf Suppose $d$ and $e$ are both the greatest common divisors of $a$ and $b$. Then $d \mid a$ and $d \mid b$. Thus, since $e$ is maximal, $d \leq e$. Similarly, $e \leq d$. Hence $d=e$.
\ic{This is the 40 minute mark}
Suppose we wanted to find a divisors of two numbers $a$ and $b$. Can we do so? How far do we have to look? Here is a theorem explaining this.
\vskip1em
\prop (Finding a Prime Factor) (FPF) Let $a,b \in \mathbb{N}$. If $n = ab$, then $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$.
\vskip1em
\pf Suppose $n = ab$ and $a > \sqrt{n}$. Then 
\begin{align*}
ab &> b\sqrt{n}\\
n &> b\sqrt{n}\\
\sqrt{n} &> b
\end{align*}
Hence $b \leq \sqrt{n}$. \qed
\vskip1em
\ic{This is the 45 minute mark. From this point on in the course, the theorem cheat sheets on the Math 135 Resources page will be quite useful for students. There will be many named theorems that students will be expected to know.. Don't rush the next example. Maybe do it in this lecture and review it a bit in the next lecture. GCDWR works very well if the two parameters in the greatest common divisor depend on each other in some way.}
\prop GCD With Remainder (GCDWR) If $a,b,q,r \in \mathbb{Z}$ and $a = bq + r$, then $\gcd(a,b) = \gcd(b,r)$.
\vskip1em
\ex $\gcd(72,40) = 8$. Now, $72= 40(2) - 8$ and so GCD With Remainder says that 
\[
\gcd(72,40) = \gcd(40,-8) = 8
\]
Note that this looks similar to the division algorithm, but the `remainder' here can be negative. You can apply this multiple times to help reduce the gcd computation a lot (this we will see later).
\ic{Delay the proof until next class. Talk about the previous example more - maybe even It's included here only if my timings above are incorrect.}
\vskip1em
\pf (of GCDWR) If $a = b = 0$, then $r = a - bq = 0$. Hence $\gcd(a,b) = 0 = \gcd(b,r)$. Now assume that $a \neq 0$ or $b \neq 0$. Let $d = \gcd(a,b)$ and $e = \gcd(b,r)$. Since $a = bq + r$ and $d \mid a$ and $d \mid b$, by Divisibility of Integer Combinations, $d \mid (a - bq) = r$. Thus, since $e$ is the maximal common divisor of $b$ and $r$, we see that $d \leq e$.
\vskip1em
Now, $e \mid b$ and $e \mid r$ so by Divisibility of Integer Combinations, $e \mid (bq + r) = a$. Since $d$ is the largest divisor of $a$ and $b$, we see that $e \leq d$. 
\vskip1em
Hence $d=e$. \qed


