Class 1 Division and Euclidean Algorithm - Jakub's notes

$\newcommand{\Gr}{\mathrm{Gr}}\newcommand{\DR}{\mathrm{DR}}\newcommand{\bA}{\mathbb{A}} \newcommand{\bB}{\mathbb{B}}\newcommand{\bC}{\mathbb{C}}\newcommand{\bD}{\mathbb{D}}\newcommand{\bE}{\mathbb{E}}\newcommand{\bF}{\mathbb{F}}\newcommand{\bG}{\mathbb{G}}\newcommand{\bH}{\mathbb{H}}\newcommand{\bI}{\mathbb{I}}\newcommand{\bJ}{\mathbb{J}}\newcommand{\bK}{\mathbb{K}}\newcommand{\bL}{\mathbb{L}}\newcommand{\bM}{\mathbb{M}}\newcommand{\bN}{\mathbb{N}}\newcommand{\bO}{\mathbb{O}}\newcommand{\bP}{\mathbb{P}}\newcommand{\bQ}{\mathbb{Q}}\newcommand{\bR}{\mathbb{R}}\newcommand{\bS}{\mathbb{S}}\newcommand{\bT}{\mathbb{T}}\newcommand{\bU}{\mathbb{U}}\newcommand{\bV}{\mathbb{V}}\newcommand{\bW}{\mathbb{W}}\newcommand{\bX}{\mathbb{X}}\newcommand{\bY}{\mathbb{Y}}\newcommand{\bZ}{\mathbb{Z}}\newcommand{\cA}{\mathcal{A}}\newcommand{\cB}{\mathcal{B}}\newcommand{\cC}{\mathcal{C}}\newcommand{\cD}{\mathcal{D}}\newcommand{\cE}{\mathcal{E}}\newcommand{\cF}{\mathcal{F}}\newcommand{\cG}{\mathcal{G}}\newcommand{\cH}{\mathcal{H}}\newcommand{\cJ}{\mathcal{J}}\newcommand{\cI}{\mathcal{I}}\newcommand{\cK}{\mathcal{K}}\newcommand{\cL}{\mathcal{L}}\newcommand{\cN}{\mathcal{N}}\newcommand{\cM}{\mathcal{M}}\newcommand{\cO}{\mathcal{O}}\newcommand{\cV}{\mathcal{V}}\newcommand{\cX}{\mathcal{X}}\newcommand{\cY}{\mathcal{Y}}\newcommand{\cZ}{\mathcal{Z}}\newcommand{\uC}{\underline{\mathbb{C}}}\newcommand{\RH}{\mathrm{RH}}\newcommand{\todo}[1]{\fbox{$\color{Mahogany} \textbf{ Todo }$: #1}}\newcommand{\cbox}[1]{\fbox{$\color{Mahogany} \textbf{ Comment: }$ #1}}\newcommand{\rup}[1]{\lceil #1 \rceil}\newcommand{\rdown}[1]{\lfloor #1 \rfloor}\newcommand{\Perv}{\mathrm{Perv}}\newcommand{\Hom}{\mathrm{Hom}}\newcommand{\cHom}{\mathop{\mathcal{H}\! \mathit{om}}}\newcommand{\RcHom}{\mathop{R\mathcal{H}\! \mathit{om}}}\newcommand{\RHom}{\mathrm{RHom}}\newcommand{\IC}{\mathrm{IC}}\newcommand{\cExt}{{\mathop{\mathcal{E}\! \mathit{xt}}}}\newcommand{\op}{\mathrm{op}}\newcommand{\Supp}{\mathrm{Supp}}\newcommand{\Exc}{\mathrm{Exc}}\renewcommand{\div}{\mathrm{div}}\newcommand{\fram}{\mathfrak{m}}\newcommand{\modd}{\ {\rm mod}\ }\newcommand{\pinkbox}{{\color{pink}\colorbox{pink}{a}}}$  **Remark** Mathematicians write proofs using full sentences and use mathematical symbols only when it makes the presentation cleaner and easier to follow. In particular, when writing explanations: * Begin each sentence with a capital letter and finish with a full stop. * Write sentences which are logically connected by using words such as: and, so, thus, therefore, because, since, etc.. * Write mathematical formulas as part of full sentences and not just put them by themselves. * Do not use unnecessary symbols. In particular, do not use: $\therefore$ and $\because$, and write *therefore* and *because* instead. Similarly minimise the use of $\forall$ (for all) and $\exists$ (exists). **Warm-up** True or False. 1. The integer -4 is a factor of both 24 and 100. 2. The integer 1 has exactly two divisors. 3. The integer 0 has exactly one divisor. 4. The integer 3 is a divisor of 4. 5. If $n \in \mathbb{Z}$, then 5 divides $5 n$. 6. If $n \in \mathbb{R}$, then 5 divides $5 n$. 7. If $a, b, c$ are integers, $a \mid b$, and $b \mid c$, then $a \mid c$. The goal of this note is to discuss the following fundamental theorem. At first glance, this theorem seems very intuitive and easy, but the proof is not obvious at all. It is based on Euclid's lemma which we will discuss later below. > [!theorem] Fundamental theorem of arithmetic > > Let $n$ be a positive natural number. Then there is a *unique* way of writing $n$ as a product of powers of prime numbers up to rearranging of their order. Precisely: $n= p_1^{\alpha_1}\cdot \ldots \cdot p_k^{\alpha_k}$ for unique prime numbers $p_1, \ldots, p_k$ and unique $\alpha_1, \ldots, \alpha_k \in \bN$. ## Division of integers First recall the following result. > [!theorem] Division Algorithm Theorem > Let $n, d \in \mathbb Z$ with $d>0$. There exists *unique* $q, r \in \mathbb Z$ such that > $n = q d + r \,\,\,\,\,\,\,\,\,\,\,\,\, {\text{ and }} \,\,\,\,\,\,\, 0 \leqslant r < d.$ **Example** For $n=8$ and $d=3$ we have $8 = \colorbox{pink}{2} \cdot 3 + \colorbox{pink}{2}.$ **Explicitly:** $n = \lfloor \frac{n}{d} \rfloor d + (n \modd d)$ We briefly recall the proof of the division algorithm theorem. > [!summary]- Proof of the division algorithm (existence) > Define the set > > $S := \{n - dx \mid x \in \bZ \textrm { and } n-dx \geq 0 \}.$ > > Pick $r$ to be the smallest number in this set and let $q \in \bZ$ be such that $n-dq=r$. Then by definition, $n = dq + r$. > > We need to argue that $r < d$. Suppose by contradiction that this is not the case, that is, $r \geq d$. Then > $n - d(q+1) = r-d \geq 0,$ > and so $r-d \in S$, contradicting the fact that $r$ was the smallest number in $S$. > > **Exercise.** Write down the set $S$ for $n=17$ and $d=5$. > [!summary]- Proof of the division algorithm (uniqueness) > Suppose that $n= dq+r$ and $n= dq' + r'$ for $q,r, q', r' \in \bZ$ such that $0 \leq r,r' < d$. We need to show that $q=q'$ and $r=r'$. > > By assumptions, $dq+r = dq'+ r'$, and so > > $d(q'-q) + r'-r = 0.$ > > Thus $d \mid r'-r$. But $-d < r'-r < d$, which implies that $r'-r = 0$. Hence > > $d(q'-q) = 0,$ > and so $q' = q$, concluding the proof. > [!Definition] > Let $a, b \in \mathbb Z$. We say $a$ *divides* $b$ if there exists $q \in \mathbb Z$ such that $b = a q$. Equivalently, in this case, we say $a$ is a *divisor* or *factor* of $b$, or that $b$ *is divisible by* $a$, and write $a \mid b$. > > [!definition] > Given two natural integers $a,b$ we define the *greatest common divisor* to be a common divisor of $a$ and $b$ which is divisible by any other common divisor. We denote it by $\gcd(a,b)$. In what follows, we recall an algorithm for calculating gcd called the Euclidean algorithm and then discuss its extended variant. ## Euclidean algorithms and Bézout's identity **Euclidean algorithm** works as follows: repeat the formula $\begin{align} \gcd(a,b)=\gcd(a-b,b) \textrm{ if } a\geq b,\\ \gcd(a,b)=\gcd(a,b-a) \textrm{ if } a < b. \end{align}$ until you reach $\gcd(a,0)=a$ or $\gcd(0,b)=b$. One can make the algorithm even faster by noting that $ \gcd(a,b) = \gcd(a \ {\rm mod }\ b, b). $ **Example.** $\gcd(24,9) = \gcd(6, 9) = \gcd(6, 3) = \gcd(0, 3) = 3$. > [!Remark] Remark *(Feel free to skip this remark)* > A priori, it is not even clear that $\gcd(a,b)$, as defined, always exists. However, the fact that the Euclidean algorithm terminates and gives a correct answer, implicitly yields the existence of gcd. Also, it is easy to see now that $\gcd(a,b)$ is nothing but the largest among common divisors of $a$ and $b$. The following theorem is the key for laying the foundations of number theory as in this note. > [!theorem] Theorem (Bézout's identity) > Let $a$ and $b$ be integers, and assume that $a$ and $b$ are not both zero. Then there exist $k,l\in \bZ$ such that $ka+lb=\gcd (a,b)$. In particular, if $a$ and $b$ are coprime, then we can find $k$ and $l$ such that $ka + lb = 1$. **Example:** $\gcd(9,24)=3$ and $\colorbox{pink}{3} \cdot 9 + \colorbox{pink}{-1} \cdot 24 = 3$ but also $\colorbox{pink}{11} \cdot 9 + \colorbox{pink}{-4} \cdot 24 = 3$. **Comment** Note that the equation $ka + lb = m$ does not admit a solution in integers when $\gcd(a,b)$ does not divide $m$.   **The extended Euclidean algirithm** is a method of finding a specific pair of numbers $k,l$ such that $ka+lb=m$ for any $m$ which is divisible by $\gcd(a,b)$. In other words, we look for solutions of $\pinkbox \cdot a + \pinkbox \cdot b = m$. The following procedure works as long as $\gcd(a,b) \mid m$. > [!Remark] Extended Euclidean Algorithm - Example > Here is an example for $\pinkbox \cdot 9 + \pinkbox \cdot 24 =12$. First, you write: > $\begin{align*} &\pinkbox \cdot 9 + \pinkbox \cdot 24 = 12 \ {\scriptsize (R)}\\ > &\pinkbox \cdot 9 + \pinkbox \cdot 6 = 12 \ {\scriptsize (L)}\\ > & \pinkbox \cdot 3 + \pinkbox \cdot 6 = 12 \ {\scriptsize (R)}\\ > & \pinkbox \cdot 3+ \pinkbox \cdot 0 = 12, > \end{align*}$ > by replacing the left black number with the remainder of its division by the right black number (labelled (L)) or vice versa (labelled (R)) depending on which one is bigger. > > So far this is the usual Euclidean algorithm, and so the last equation is going to be > $\pinkbox \cdot \gcd(a,b) + \pinkbox \cdot 0 = m $ > which in our case is $\pinkbox \cdot 3 + \pinkbox \cdot 0 = 12$. It admits a solution, for example, $x=\frac{m}{\gcd(a, b)}, y= 0$. Let us put it in: > > $\begin{align*} > &\pinkbox \cdot9 + \pinkbox \cdot24 = 12 \ {\scriptsize (R)}\\ > &\pinkbox \cdot9 + \pinkbox \cdot6 = 12 \ {\scriptsize (L)}\\ > &\pinkbox \cdot3 + \pinkbox \cdot6 = 12 \ {\scriptsize (R)}\\ > &\colorbox{pink}{4} \cdot 3 + \colorbox{pink}{0} \cdot 0 = 12. > \end{align*} $ > Now going from the bottom up, we fill in the pink boxes. Precisely, if in a given row the numbers in pink boxes are ${\color{purple}(x, y)}$, then in the row one above we put in > $\begin{align*}&{\color{purple}(x, y-\lfloor \frac{a}{b}\rfloor x)} \quad\text{ (in Case (L)), or} \\ &{\color{purple}(x-\lfloor \frac {b}{a} \rfloor y,y)} \quad \text{ (in Case (R))} \end{align*}$ > So in our example > $\begin{align*} > &\colorbox{pink}{12} \cdot 9 + \colorbox{pink}{-4} \cdot24 = 12 \ {\scriptsize (R)}\\ > &\colorbox{pink}{4} \cdot9 + \colorbox{pink}{-4} \cdot6 = 12 \ {\scriptsize (L)}\\ > &\colorbox{pink}{4} \cdot3 + \colorbox{pink}{0} \cdot6 = 12 \ {\scriptsize (R)}\\ > &\colorbox{pink}{4} \cdot3 + \colorbox{pink}{0} \cdot0 = 12. > \end{align*}$ The key why the Euclidean algorithm works is the following observation: * if $x$ and $y$ solve $\pinkbox \cdot (a \modd b) + \pinkbox \cdot b =m$, then $x$ and $y-\lfloor \frac{a}{b}\rfloor x$ solve $\pinkbox \cdot a + \pinkbox \cdot b=m,$ * if $x$ and $y$ solve $\pinkbox \cdot a + \pinkbox \cdot (b \modd a) =m$, then $x-\lfloor \frac {b}{a} \rfloor y$ and $y$ solve $\pinkbox \cdot a + \pinkbox \cdot b=m.$ The fact that Extended Euclidean Algorithm terminates and always give a correct answer provides a constructive proof of Bezoute's identity. Later in the course we will also see an abstract proof of Bezoute's identity. **Practice problem** Apply the extended Euclidean algorithm to $524, 148$ with $m=\gcd(524,148)$. ## Euclid's lemma and its consequences We can finally prove Euclid's lemma. > [!lemma] Euclid's lemma > Let $p$ be a prime number and let $a, b \in \bZ$. In this case, if $p \mid ab$, then $p \mid a$ or $p \mid b$. **Proof of Euclid's lemma.** > Suppose that $p \mid ab$. If $p \mid a$, then we are done. Thus we may assume that $p$ does not divide $a$. > > By definition of a prime number: $\gcd(p,a)=1$, and so by Bezoute's identity, there exist $k, l \in \bZ$ such that $pk + al=1$. Then > > $pkb + alb = b.$ > > Since $p \mid ab$, we get that $p \mid pkb + alb = b$, concluding the proof. Now using Euclid's lemma is not too hard to prove the fundamental theorem of arithmetic. For the **existence of the prime decomposition** we argue as follows. If $n$ is prime, then we are done. Otherwise, we write it as $n=ab$ for $a,b \neq 1$, and repeat the same procedure for $a$ and $b$ until $n$ becomes a product of prime numbers. For the **uniqueness of the prime decomposition** we argue as follows. Write two prime decompositions of $n$: $ n= p_1^{\alpha_1}\cdot \ldots \cdot p_k^{\alpha_k} = q_1^{\beta_1}\cdot \ldots \cdot q_l^{\beta_l}. $ Since $p_1 \mid q_1^{\beta_1}\cdot \ldots \cdot q_l^{\beta_l}$, by Euclid's lemma we get that $p_1$ is equal to one of the $q_i$s. Now we divide both sides of the equation by $p_1$ and continue the same procedure until nothing is left. **Exercise** Prove the fundamental theorem of arithmetic by providing all the details to the above argument.