\newlec

\ic{One thing I noticed that I want to spend a bit of time going over at the beginning was how to write a factorization of a number $n$}

\recall Fundamental Theorem of Arithmetic. Suppose that $n > 1$ is an integer. Then $n$ can be factored uniquely as a product of prime numbers up to reordering of prime numbers.
\vskip1em
\note For a natural number $n$ we can write down this factorization in a number of ways:
\begin{enumerate}
\item $n = \displaystyle \prod_{i=1}^{k}p_{i}$ where each $p_{i}$ is prime. ($n > 1$ required)
\item $n = \displaystyle \prod_{i=1}^{k}p_{i}^{\alpha_{i}}$ where each $\alpha_{i} \geq 1$ is an integer and each $p_{i}$ is distinct. ($n > 1$ required)
\item $n = \displaystyle \prod_{i=1}^{k}p_{i}^{\alpha_{i}}$ where each $\alpha_{i} \geq 0$ is an integer and each $p_{i}$ is distinct. This is useful if you have two numbers and want to write them using the same primes $p_{i}$. They might not have the same prime factors, but allowing for the exponent to be $0$ allows you to write them using the same prime factors. For example, $30 = 2^{1} \cdot 3^{1} \cdot 5^{1} \cdot 7^{0}$ and $14 = 2^{1} \cdot 3^{0} \cdot 5^{0} \cdot 7^{1}$.
\end{enumerate}

\ic{This is the 5 minute mark.}

\thm Divisors From Prime Factorization (DFPF). Let $n = \displaystyle \prod_{i=1}^{k}p_{i}^{\alpha_{i}}$ where each $\alpha_{i} \geq1$ is an integer. Then $d$ is a positive divisor of $n$ if and only if a prime factorization of $d$ can be given by
\[
d =  \prod_{i=1}^{k}p_{i}^{\delta_{i}} \quad\quad \text{ where $\delta_{i} \in \mathbb{Z}, 0 \leq \delta_{i} \leq \alpha_{i}$ for $1 \leq i \leq k$}
\]
\pf Extra reading. \qed
\vskip1em
\ex Positive divisors of $63 = 3^{2} \cdot 7$ are given by 
\[
3^{0}\cdot7^{0}, 3^{0}\cdot 7^{1}, 3^{1} \cdot 7^{0}, 3^{1} \cdot 7^{1}, 3^{2} \cdot 7^{0}, 3^{2} \cdot 7^{1}
\]
or
\[
1,7,3,21,9,63
\]
\ic{This is the 15 minute mark}
\newpage

\hdc
How many multiples of 12 are positive divisors of 2940? What are they?
\vskip3em

\soln Notice that $2940 = 12(245)$ (say by long division). Then, to find the number of divisors of $2940$ that are multiples of $12$, you just need to take the divisors of 245 (and then multiply them all by 12). Since $245 = 5\cdot7^{2}$, the total number of divisors is $(1+1)(2+1) = 6$.
\ic{Explain to students this is like taking 0 or 1 five and then 0, 1, or 2 sevens.}
Hence the multiples are:
\[
12, 12\cdot 5, 12\cdot 7, 12\cdot 5 \cdot 7, 12\cdot7^{2}, 12\cdot 5\cdot 7^{2}
\]
\ic{This is the 25 minute mark}
\newpage

\ex Prove that $a^{2} \mid b^{2}$ if and only if $a \mid b$.
\vskip1em
\pf Assume that $a \mid b$. Then there exists a $k \in \mathbb{Z}$ such that $ak = b$. Now $a^{2}k^{2} = b^{2}$ and hence $a^{2} \mid b^{2}$ by definition.
\vskip1em
Now, assume that $a^{2} \mid b^{2}$. For convenience, assume that $a,b > 0$. Now, write
\[
a = \displaystyle \prod_{i=1}^{k}p_{i}^{\alpha_{i}}  \quad\quad b = \displaystyle \prod_{i=1}^{k}p_{i}^{\beta_{i}}.
\] 
where $0 \leq \alpha_{i}$ and $0\leq \beta_{i}$ are integers and the $p_{i}$ are distinct primes. Since $a^{2} \mid b^{2}$, we have that
\[
\left. \prod_{i=1}^{k}p_{i}^{2\alpha_{i}}  ~\middle | ~\prod_{i=1}^{k}p_{i}^{2\beta_{i}}\right.
\]
Now, Divisors From Prime Factorization implies that $2\alpha_{i} \leq 2 \beta_{i}$ and so $\alpha_{i} \leq \beta_{i}$ true for $1 \leq i \leq k$. Divisors From Prime Factorization again implies that
\[
a = \left . \prod_{i=1}^{k}p_{i}^{\alpha_{i}}  ~\middle| ~\prod_{i=1}^{k}p_{i}^{\beta_{i}} = b \right.
\]
as required. \qed
\vskip1em
\ic{One more theorem. This is the 35 minute mark}

\ex 
\begin{align*}
\gcd(2^{5}\cdot 3^{0} \cdot 5^{4}, 2^{4} \cdot 3^{1} \cdot 5^{4}) &= 2^{\min\{4,5\}}\cdot 3^{\min\{0,1\}}\cdot 5^{\min\{4,4\}}\\
&= 2^{4} \cdot 5^{4} \\
&= 10000
\end{align*}

\ic{Mention that factoring is very complicated.}

\thm (GCD From Prime Factors (GCDPF)) If 
\[
a = \displaystyle \prod_{i=1}^{k}p_{i}^{\alpha_{i}}  \quad\quad b = \displaystyle \prod_{i=1}^{k}p_{i}^{\beta_{i}}.
\] 
where $0 \leq \alpha_{i}$ and $0\leq \beta_{i}$ are integers and the $p_{i}$ are distinct primes, then
\[
\gcd(a,b) = \prod_{i=1}^{k}p_{i}^{m_{i}}
\]
where $m_{i} = \min\{\alpha_{i}, \beta_{i}\}$ for $1 \leq i\leq k$.
\vskip1em
\pf More extra reading. \qed

\ic{The next topic is completely optional on least common multiples. Do it if you have time}

Let $\lcm(a,b)$ represent the least common multiple of $a$ and $b$.
\vskip1em
\ex\begin{enumerate}
\item Write out a formal definition of $\lcm(a,b)$.
\item Show that $\lcm(a,b) = \prod_{i=1}^{k}p_{i}^{e_{i}}$ where $e_{i} = \max\{\alpha_{i},\beta_{i}\}$.
\item Prove that $\gcd(a,b)\cdot \lcm(a,b) = ab$.
\end{enumerate}

\ic{Lastly, I give tips for solving GCD problems. The analogy is going to Toronto: Taking the 401 (might be hard but is ideal). Walking (Slow but will get you there). Flying (Theoretically fastest but takes longer to set up) These are continued on the lecture if you run out of time.}

When solving GCD problems, the following gives a rough order of how and when you should try a technique
\begin{enumerate}
\item B\'{e}zout's Theorem (EEA) [Good when gcd is in hypothesis]
\item GCDWR [Good when terms in gcd depend on each other; good for computations]
\item GCDCT [Good when gcd is in conclusion]
\item Definition [Good when nothing else seems to work]
\item GCDPF [Good when you're desperate]
\end{enumerate}


%
%MATH 135 students often struggle proving results about $$\gcd$$. In general, we have three approaches to proving such results:
%
%    Use key theorems (especially GCD WR, GCD CT and EEA).
%    Use the definition of $$\gcd$$
%    Use prime factorizations.

%It is normally best to try them in the order listed above. That is, generally, using key theorems is the easiest approach and using prime factorizations is generally the most difficult.
%

%Let me use an analogy that I thought of last year. Think of proving a result about $$\gcd$$ as getting from Waterloo to Toronto. Using a key theorem is like taking Highway 401. It tends to be quick and direct. Using the definition of $$\gcd$$ is like taking Highway 7. It will take you there but is slower and there is more to worry about. Using prime factorization feels quick and easy so it is analogous to taking an airplane. The problem is that there is lots to worry about at the start (parking, security, etc.) and as you fly, it is easy to "skip" things. Then there is lots to worry about at the end. (luggage, security, etc.).
%
% 
%
%So, try the easy way first. Take the 401. Sometimes traffic and/or construction are bad so you'll have to get there another way but it should be the default route.

 

