NT: The Division Algorithm

 Theorem 1. Suppose that $a,b\in\mathbb{Z}$ with $0<a<b$. Then there exists uniquely $q,r\in\mathbb{Z}$, $0\leq r<a$, such that
 $$b=aq+r$$
 
 Theorem 2. If $a$ and $b$ are positive integers, then
 $$(a,b)[a,b]=ab$$
 
 Suppose that $0<a<b$. Then by the division algorithm, there exist uniquely $q,r\in\mathbb{Z}$ such that $b=aq+r$ where $0\leq r<a$. If $d=(a,b)$ then $d|r$. This means $d\leq(a,r)$ since $d$ is a common divisor of $a$ and $r$. Since $(a,r)|a$ and $(a,r)|b$, $(a,r)$ is a common divisor of $a$ and $b$. This implies $(a,r)\leq(a,b)=d$. Thus, $d=(a,r)=(a,b)$. More generally, we have the following lemma holds.
 
 Lemma 3. For any integers $a>0$, $b$, $c$ and $k$, if $a=bk+c$ then $(a,b)=(b,c)$.

Proof. Let $d=(a,b)$. Since $d|a$ and $d|b$, $d|c$. Since $d$ is a common divisor of $b$ and $c$, $(b,c)\leq d=(a,b)$. Let $e=(b,c)$. Since $e|b$ and $e|c$, $e|a$. Since $e$ is a common divisor of $a$ and $b$, $(a,b)\leq e=(b,c)$. Therefore, $(a,b)=(b,c)$.

Example. Let $a=123$ and $b=504$. Then
  $$504=123\cdot 4+12$$
  By Lemma 3 we have
  $$(123,504)=(12,123)$$
  $$123=12\cdot 10+3$$
  By Lemma 3 again, we have
  $$(12,123)=(3,12)=3$$
  Hence, we obtain $(123,504)=3$.
 
  Theorem 4 [The Euclidean Algorithm] Let $a$ and $b$ be integers, $0<a<b$. Apply the division algorithm repeatedly as follows.
 \begin{align*}
        b&=aq_1+r_1,\ 0<r_1<a\\
        a&=r_1q_2+r_2,\ 0<r_2<r_1\\
      r_1&=r_2q_3+r_3,\ 0<r_3<r_2\\
         &\vdots\\
  r_{n-2}&=r_{n-1}q_n+r_n,\ 0<r_n<r_{n-1}\\
  r_{n-1}&=r_nq_{n+1}
 \end{align*}
Let $r_n$ be the last nonzero remainder. Then $(a,b)=r_n$.

Example. Compute $(158,188)$ using the Euclidean algorithm (Theorem 4).
 \begin{align*}
  188&=158\cdot 1+30\\
  158&=30\cdot 5+8\\
   30&=8\cdot 3+6\\
    8&=6\cdot 1+2\\
    6&=2\cdot 3+0
 \end{align*}
Hence, $(158,188)=2$.

MAXIMA [GCD] 

Maxima has a built-in function to compute the gcd

gcd(a,b)
 
 (%i1) gcd(158,188);
 
 (%o1) 2

 PYTHON [GCD]

 Algorithm: The name of the Python code (it is called a Python module) is gcd(a,b) and it implements the Euclidean algorithm to find the GCD of two integers $a$ and $b$.

1. If b==0 then gcd(a,b) returns 0 because every nonzero integer divides $0$.
2. Otherwise, it returns gcd(b,a % b). % is the modulo or remainder operator. a % b returns the remainder when $a$ is divided by $b$ if $a\geq b$ or $a$ if $a<b$ because $a=b\cdot 0+a$. For example, 12345 % 2 returns 1.
3. The loop continues until b==0.
   

 A python code is saved in the file gcd.py and it can be downloaded here. Essentially the same but a slightly different version is available here. On IDLE, the Python module can be run from its pull-down (or drop-down) menu under Run. Its shortcut key is F5. To run it on iPython, first change your current folder location to the one that contains the Python module gcd.py using cd (change directory) command in command shell and then start iPython by typing ipython (you can first start iPython and then change your current folder location as well using cd within iPython) and pressing the enter key. Once iPython is loaded, do
 

$ ipython
Python 3.7.9 (default, Feb 4 2021, 01:17:56)
Type 'copyright', 'credits' or 'license' for more information

IPython 7.19.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: run gcd.py

In [2]: gcd(98,56)

Out[2]: 14

PYTHON [The Euclidean Algorithm]

The Euclidean algorithm itself is a perfect computer algorithm. A Python code of the Euclidean algorithm is available here.

MAXIMA [LCM]

Maxima has a function to compute the lcm

lcm(expr_1,...,expr_n)

This function needs to be loaded by running the command

load(``functs'')
 
(%i1) load("functs")$

(%i2) lcm(6,8,15,32);

(%o2) 480

PYTHON [LCM]

The LCM $[a,b]$ can be obtained by $\frac{ab}{(a,b)}$.
 
 Algorithm: The name of the Python code is lcm(a,b). It computes the LCM of two integers $a$ and $b$.

1. Find the GCD of $a$ and $b$ by running the Python module gcd(a,b).
2. Compute the LCM of $a$ and $b$ using the formula a*b/gcd(a,b).
   

A Python code is saved in the file lcm.py and it can be downloaded from here.

It is possible to use the Euclidean algorithm to write $(a,b)$ in the form $ax+by$. In the above example,
\begin{align*}
 2&=8-6\cdot 1\\
  &=8-(30-8\cdot 3)\cdot 1\\
  &=-30+8\cdot 4\\
  &=-30+(158-30\cdot 5)\cdot 4\\
  &=158\cdot 4-30\cdot 21\\
  &=158\cdot 4-(188-158\cdot 1)\cdot 21\\
  &=158\cdot 25+188\cdot(-21)
\end{align*}
In general, the following property holds.

Theorem 5 [Bézout's Lemma]  If $a$ and $b$ are integers such that $(a,b)$ is defined, then there exist $x,y\in\mathbb{Z}$ such that
$$
(a,b)=ax+by \tag{1}
$$
(1) is called the Bézout's identity.

Corollary 6.  If $d$ is any common divisor of $a$ and $b$, not both of which are $0$, then $d|(a,b)$.

MAXIMA

The Maxima command gcdex implements the Euclidean algorithm. gcdex(a,b) returns [x, y, u] where $u=(a,b)$ and $ax+by=u$. So, one can find a solution of (1) using gcdex. For example, we can solve $2=158x+188y$ by running
 
 (%i2) gcdex(158,188);
 
 (%o2) [25, - 21, 2]
 
 which coincides with what we found in the above example. One can also use the command igcdex. gcdex and igcdex both implement the Euclidean algorithm. The only difference between them is that the argument of igcdex must be integers while the arguments of gcdex can be also polynomials. For instance,
 
(%i7) gcdex(x^2 + 1, x^3 + 4);

(%o7)/R/ [$-\displaystyle\frac{x^2+4x-1}{17}$, $\displaystyle\frac{x+4}{17}$, 1]

PYTHON [Linear Diophantine Equations]

A linear diophantine equation
 $$
  ax+by=c \tag{2}
$$
 is solvable if and only if $(a,b)|c$. If $b|a$ then $(a,b)=b$ and
 $$x=0,\ y=\frac{c}{b}$$
 is a solution. If $b\not|a$, then write $a=bq+r$ and substitute into (2):
 $$(bq+r)x+by=c$$
 This can be rearranged as
 $$b(qx+y)+rx=c$$
 Setting $u=qx+y$ and $v=x$, we obtain the equation
 $$
  bu+rv=c \tag{3}
 $$
 with smaller coefficients. If we can solve (3), we recover a solution of the original equation as
 $$x=v,\ y=u-qv$$
 The process terminates (according to the Euclidean algorithm) with an equation where the second coefficient divides the first. This scheme is embodied in the Python code named diosolve.py which can be downloaded here. Note the function divmod returns a pair of numbers, the quotient and remainder, which we store in q, r. For example, the diophantine equation $12345x+54321y=3$ is solvable because $(12345,54321)=3$. Its solution can be found by running diosolve.py on iPython:
 
In [9]: run diosolve.py

In [10]: diosolve(12345, 54321, 3)

Out[10]: [3617.0, -822.0]

Definition. We say $k$ is a linear combination of $a$ and $b$ if there exist $x,y\in\mathbb{Z}$ such that $k=ax+by$.

Theorem 7. Given integers $a\ne 0$ and $b\ne 0$, and $m$, if $a|m$ and $b|m$ then $[a,b]|m$.

Proof. Assume that $\frac{m}{[a,b]}$ is not an integer. Then there exist $q,r\in\mathbb{Z}$ such that $m=[a,b]q+r$, $0<r<[a,b]$. The remainder $r$ is then written as $r=m-q[a,b]$. By assumption, $a|m$, and also $a|[a,b]$. So, $a|r$. By the same argument, we also obtain $b|r$. This means that $r$ is a common multiple of $a$ and $b$. But it is a contradiction to the fact that $0<r<[a,b]$. Hence, $r=0$.

Remark. Corollary 6 and Theorem 7 are dual to each other.