Division theorem, Euclidean algorithm and Bezout's identityEdexcel A-Level Further Maths: Revision notes

For integers $a$ and $b$ with $b>0$, there are unique integers $q$ (the quotient) and $r$ (the remainder) with $a=bq+r,\qquad 0\leq r<b.$ Example: $252=1\times198+54$, so $q=1$ and $r=54$. In congruence notation, $a\equiv r\pmod b$, because $a$ and $r$ leave the same remainder on division by $b$. The theorem is the engine of the Euclidean algorithm, and $r=0$ exactly when $b$ divides $a$.

The highest common factor $\text{hcf}(a,b)$ is the largest integer dividing both. The key fact is $\text{hcf}(a,b)=\text{hcf}(b,r)$, since any common divisor of $a$ and $b$ divides $r=a-bq$, and any common divisor of $b$ and $r$ divides $a=bq+r$. Repeat the division theorem on the divisor and remainder until the remainder is $0$. The last non-zero remainder is the hcf. Example: $252=1(198)+54$; $198=3(54)+36$; $54=1(36)+18$; $36=2(18)+0$. So $\text{hcf}(252,198)=18$. Two integers with hcf $1$ are coprime, and $\text{lcm}=\frac{ab}{\text{hcf}}$, so $\text{lcm}(252,198)=2772$.

Bezout's identity: for integers $a,b$ (not both zero) there exist integers $x,y$ with $ax+by=\text{hcf}(a,b).$ Find $x$ and $y$ by back substitution: rearrange each step of the algorithm as $r=a-bq$, then work upwards from the line with the hcf, replacing each remainder in turn. Example, $240$ and $46$: $240=5(46)+10$, $46=4(10)+6$, $10=1(6)+4$, $6=1(4)+2$. Then $2=6-4=2(6)-10=2(46)-9(10)=47(46)-9(240)$, so $x=-9$, $y=47$. Always check: $47\times46-9\times240=2162-2160=2$.

Since $\text{hcf}(a,b)$ divides $ax+by$ for all integers $x,y$, the equation $ax+by=c$ has integer solutions if and only if $\text{hcf}(a,b)$ divides $c$. If $d=\text{hcf}(a,b)$ and $d\mid c$, multiply the Bezout solution by $\frac cd$. Example: $1547x+504y=10$ has no solution because $\text{hcf}=7\nmid10$, but $1547x+504y=7$ does: $7=29(1547)-89(504)$. In particular, $a$ and $b$ are coprime if and only if $ax+by=1$ has a solution.