[Notes](#fn1): Problem Class, 22 Oct 2020

# [Notes](#fn1): Problem Class, 22 Oct 2020 > Group 11 -- Problem Class, MATH40001/40009 IUM > Stergios M. Antonakoudis (stergios@imperial.ac.uk) Welcome to IUM Problem Class Group 11. \ Today's class: **Problem Sheet 3 of Part II.** [^1]: *These notes[^1] are typed up and created during and for the purposes of the discussion in the online session of Problem Class Group 11 for IUM on MS Teams, similarly to the use of a 'whiteboard' in an actual class.* --- ## Questions --- ## Problems ### ==Problem 4.(a)== Let $a,b \in \mathbb{N}$ and $d=\gcd(a,b)$. Show that there exists integers $s,t \in \mathbb{Z}$ such that $as + bt = d$. ### ==Solution 4.(a)== Consider the set $A=\{\;\; N \in \mathbb{N} \;\;:\;\; N=as +bt, \;\; s,t\in \mathbb{Z}\;\;\}$. GOAL: There exists integer $d \in \mathbb{N}$ such that $A= \{ d\cdot k \;:\; k \in \mathbb{N} \}$. Proof: Clearly $A$ is a non-empty set and $0\in A$. Let's consider $d$ the least non-zero element of $A$. In particular, $d= as +bt$ for some $s,t \in \mathbb{Z}$. Hence, $dk = (as)k +(bt)k=a(sk)+b(tk)$ for every $k\in \mathbb{N}$. Therefore all non-negative multiples of $d$ are in the set $A$. Let $N \in A$, if $d | N$ then we're OK. Assume that $d$ does not divide $N$. Then $N= d\cdot q +r$ where $r,q \in \mathbb{N}$ and $1 \leq r < d$. However, $d\cdot q \in A$ and therefore $r=N - d \cdot q \in A$. But this is a contradiction because $1 \leq r < d$. I.e. there is no $N$ such that $d$ does not divide $N$. In other words every element of $A$ is also a multiple of $d$ -- $A = \{d\cdot k \;\; : \;\; k \in \mathbb{N}\}$. QED NEXT GOAL: $d = \gcd(a,b)$ Proof: Firstly, if $c |a$ and $c|b$, then $c | as+bt$ and $d=as+bt$; hence, $c | d$. We conclude that $\gcd(a,b) | d$. On the other hand, $a,b \in A$ and therefore both $a$ and $b$ are multiples of $d$ i.e. $d| a$ and $d| b$, which means $d | \gcd(a,b)$. We conclude that $d=\gcd(a,b)$. QED **QED** In practice, given $a,b \in \mathbb{N}$, we can find $s,t \in \mathbb{Z}$ such that $as+bt = \gcd(a,b)$ by 1) using the Euclidean algorithm to find the $\gcd(a,b)$ and 2) running the Euclidean algorithm backwards to find $s,t$. E.g. $a=11, b=3$ $11 = 3\cdot 3 + 2$ $3 = 1\cdot 2 +1$ Therefore, $\gcd(11,3)=1$. $1 = 3 - 1 \cdot 2$ $1 = 3 - 1 \dot (11 - 3 \cdot 2)$ ==$1= 4\cdot 3 -1 \cdot 11$==