\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Fundamental theorem proof}


{\bf Theorem}: Every positive integer {\it greater than 1} is a product of (one or more) primes.

{\bf Before we prove, let's try some examples}:

$20 = $

$100 = $

$5 = $


{\bf Proof by strong induction}, with $b=2$ and $j=0$.

{\bf Basis step}:  WTS property is true about  $2$.

Since $2$ is itself prime,
it is already written as a product of (one) prime.


{\bf Recursive step}: Consider an arbitrary integer $n \geq 2$.
Assume (as the strong induction hypothesis, IH) that the property is true about  each of $2, \ldots, n$.  
WTS that the property is true about  $n+1$: We want to show that $n+1$ can be written 
as a product of primes.  Notice that $n+1$ is itself prime or it is composite.

{\it Case 1}: assume $n+1$ is prime and then immediately it is written as a product
of (one) prime so we are done.  

{\it Case 2}: assume that $n+1$ is composite
so there are integers $x$ and $y$ where $n+1 = xy$ and each of them is between $2$ and $n$
(inclusive).  Therefore, the induction hypothesis applies to each of $x$ and $y$ so each 
of these factors of $n+1$ can be written as a product of primes.  Multiplying these products together, 
we get a product of primes that gives $n+1$, as required. 

Since both cases give the necessary
conclusion, the proof by cases for the recursive step is complete. \vfill
\section*{Least greatest proofs}


For a set of numbers $X$, how do you formalize ``there is a greatest $X$'' 
or ``there is a least $X$''?

\vspace{30pt}

{\bf Prove} or {\bf  disprove}:  There is a least prime number.

\vspace{100pt}

{\bf Prove} or {\bf  disprove}: There is a greatest integer. 

{\it Approach 1, De Morgan's and universal generalization}: 

\vspace{100pt}

{\it Approach 2, proof by contradiction}: 

\vspace{200pt}

{\it Extra examples}: 
Prove or disprove that $\mathbb{N}$,  $\mathbb{Q}$ each have a
least and a greatest element. 
 \vfill
\section*{Gcd definition}


{\bf Definition}: {\bf Greatest common divisor} Let $a$ and $b$ be integers, not both zero. The largest integer $d$ such that 
$d$ is a  factor of $a$ and $d$ is a factor of  $b$ is called the greatest common divisor of $a$ and $b$ 
and is denoted by $gcd(~(a, b)~)$. \vfill
\section*{Gcd examples}


Why do we restrict to the situation where $a$ and $b$ are not both zero?

\vspace{50pt}


Calculate $gcd(~(10,15)~)$

\vspace{50pt}

Calculate $gcd(~(10,20)~)$

\vspace{50pt} \vfill
\section*{Gcd basic claims}


{\bf Claim}: For any integers $a,b$ (not both zero), $gcd(~(a,b)~) \geq 1$.

{\bf Proof}: {\it Show that $1$ is a common factor of any two integers, so since the gcd 
is the greatest common factor it is greater than or equal to any common factor.}

\vspace{150pt}

{\bf Claim}: For any positive integers $a,b$, $gcd(~(a,b)~) \leq a$ and $gcd( ~(a,b)~) \leq b$.

{\bf Proof} {\it Using the definition of gcd and the fact that factors of a positive integer
are less than or equal to that integer.}

\vspace{150pt}

{\bf Claim}: For any positive integers $a,b$, if $a$ divides $b$ then $gcd(~(a,b)~) = a$.

{\bf Proof} {\it Using previous claim and definition of gcd.}

\vspace{150pt}


{\bf Claim}: For any positive integers $a,b,c$, if there is some integer $q$ such that $a = bq + c$,
\[
    gcd(~(a,b)~) = gcd (~(b,c)~)
\]
{\bf Proof} {\it Prove that any common divisor of $a,b$ divides $c$ and that any common 
divisor of $b,c$ divides $a$.}

\vspace{150pt}
 \vfill
\section*{Gcd lemma relatively prime}


{\bf Lemma}: For any integers $p, q$ (not both zero), 
$gcd \left(~ \left(~\frac{p}{gcd(~(p,q)~)}, \frac{q}{gcd(~(p,q)~)} ~\right) ~\right) = 1$ .
In other words, can reduce to relatively prime integers by dividing by gcd.

{\bf Proof}:

Let $x$ be arbitrary positive integer and assume that $x$ is a 
factor of each of $\frac{p}{gcd(~(p,q)~)}$ and $\frac{q}{gcd(~(p,q)~)}$. 
This gives integers $\alpha$, $\beta$ such that 
\[
    \alpha x = \frac{p}{gcd(~(p,q)~)} \qquad \qquad \beta x = \frac{q}{gcd(~(p,q)~)}
\]
Multiplying both sides by the denominator in the RHS: 
\[
    \alpha x \cdot gcd(~(p,q)~)= p \qquad \qquad \beta x \cdot gcd(~(p,q)~)= q
\]
In other words, $x \cdot gcd(~(p,q)~)$ is a common divisor of $p, q$. By definition of $gcd$, this means
\[
    x \cdot gcd (~(p,q)~) \leq gcd (~(p,q)~)
\]
and since $gcd(~(p,q)~)$ is positive, this means, $x \leq 1$.
\vspace{350pt}
 \vfill
\end{document}