Finding gcd by Euclidean algorithm and extended Euclidean algorithm

Task: find the greatest common divisor of two integers a and b using python

The first program relies on the fact that if $d\mid a$ and $d\mid b$, then $d|(a-b)$. In the third program, we need to ensure that b is not zero because division by zero is not defined. Line 21 follows from Euclidean algorithm. (In fact, it does not matter whether a or b is the larger number. Here is an example for illustration. When a = 210 and b = 7, 210 is assigned to 7 and 7 to 0. The program then stops and returns 7. When a = 7 and b = 210, 7 is assigned to 210 and 210 is assigned to 7 % 210. 7 % 210 is 0 with remainder 7. Now, 210 is assigned to 7 and 7 to 0. The program terminates and returns 7.)

The fourth program is known as the extended Euclidean algorithm and it takes some time to understand. Note that for integers $a,b$ where $a>b$, $a=qb+r=\lfloor a/b \rfloor b+a-\lfloor a/b \rfloor b$, or in python $a=a//b*b+a\%b$. Recall that each iteration in the Euclidean algorithm replaces $(a,b)$ by $(b,a\;\text{mod}\; b)$. We can formulate this as a matrix multiplication: $$\begin{pmatrix}b & a\;\text{mod}\;b\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q\end{pmatrix},\qquad q=\lfloor a/b \rfloor.$$Suppose that the algorithm terminates after $k$ iterations, then the operations performed on $\text{gcd}(a,b)$ can be summarised in matrix notation by $$\begin{pmatrix}\text{gcd}(a,b)&0\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q_1\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q_2\end{pmatrix}\cdots\begin{pmatrix}0 & 1\\ 1 & -q_k\end{pmatrix}$$ or $$\begin{pmatrix}\text{gcd}(a,b)&0\end{pmatrix}=\begin{pmatrix}a&b\end{pmatrix}\begin{pmatrix}x & u\\ y & v\end{pmatrix}.$$Since we want to find the triple $(d,x,y)$, namely, the gcd and the first column of the resulting matrix, we want to keep track of the product of matrices along with the remainder computation. Therefore, we start with the matrix $$\begin{pmatrix}x & u\\ y & v\\ a & b\end{pmatrix}=\begin{pmatrix}1 & 0\\ 0 & 1\\ a & b\end{pmatrix},$$ or set $x,y,u,v=1,0,0,1$. Note that $$\begin{pmatrix}x & u\\ y & v\\ a & b\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & -q\end{pmatrix}=\begin{pmatrix}u & x-uq\\ v & y-vq\\ b & a-bq\end{pmatrix}$$ It is then natural to assign $x$ to $u$, $y$ to $v$; $u$ to $x-uq$, $v$ to $y-vq$. The rest is similar to program $3$. Here's a second interpretation. The algorithm aims to compute the tuple $(d,x,y)$ such that $ax+by=d$. We know that $$a\cdot 1+b\cdot 0=a\\ a\cdot 0+b\cdot 1=b.$$ We then set $$a\cdot x+b\cdot y=a\quad(1)\\ a\cdot u+b\cdot v=b\quad(2)$$ where $x,y,u,v$ are $1,0,0,1$. Note that $\text{gcd}(a,b)=\text{gcd}(b,r=a\;\text{mod}\; b)$. We thus have a new pair of equations: $$(1)-(2)\cdot q,\quad a\cdot(x-uq)+b\cdot(y-vq)=r,\quad q=\lfloor a/b \rfloor. \\ a\cdot x+b\cdot y=b$$ Assigning $a$ to $b$, $b$ to $r$ and changing the values of $x,y,u,v$ accordingly, the program will eventually terminate when $b$ becomes $0$. It follows that $$a\cdot u+b\cdot v=0\\ a\cdot x+b\cdot y=\text{gcd}(a,b).$$Then we take the second equation and we have $(d,x,y)$.

In the sixth program, we are still relying on the fact that $\text{gcd}(a,b)=\text{gcd}(b,r=a\;\text{mod}\; b)$. We have $$ax+by=\text{gcd}(a,b)\\ bx'+ry'=\text{gcd}(a,b).$$ Put $x=y',y=x'$. Then $$\begin{align}ax+by&=ay'+bx'\\ &=(qb+r)y'+bx'\\ &=qby'+(ry'+bx')\\ ay'+bx'&=qby'+\text{gcd}(a,b)\\ \Rightarrow ay'+b(x'-qy')&=\text{gcd}(a,b).\end{align}$$ Finally, we put $x=y',y=x'-qy'$, where $x,y$ are the values we want.

Lessons learnt:

• = vs ==: The first one assigns a value to the variable on the left; the second one means that the value of the variable is that on the right.
• % // operators
• while loop
• iterative (loop) vs recursive (a function calling itself repeatedly)
• multiple assignment: In python, we don't need a swap function because a, b = b, a works sufficiently without defining a temp variable, c. This is useful when we want a to be larger than b:

if a < b:

    a, b = b, a
else:
    pass

More to know:

subtractive algorithm 1, 2, 3

binary gcd algorithm 1

extended Euclidean algorithm

Reference:
program 4 1, 2, 3
program 6 1, 2, 3

Probability that two randomly selected integers are relatively prime

We make use of this result: $$\bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=1.$$ Why is this true? Note that $$\bigg(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots \bigg)\bigg(1-\dfrac{1}{2^2}\bigg)=1+\dfrac{1}{3^2}+\dfrac{1}{5^2}+\cdots$$ In the equation, all the multiples of $\dfrac{1}{2^2}$ in the first factor have been knocked out by $\bigg(1-\dfrac{1}{2^2}\bigg)$. Similarly, multiplying by $\bigg(1-\dfrac{1}{3^2}\bigg)$ cancels multiples of $\dfrac{1}{3^2}$. Recall that $$1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots=\dfrac{\pi^2}{6}.$$ We thus have $$\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{1}{\dfrac{\pi^2}{6}}=\dfrac{6}{\pi^2}.$$We are now ready to proceed with the solution of the original problem. Let $m, n$ be the given random numbers. Let $a$ be any prime. Since $a$ divides $1$ only, $1/a $ of all the integers are divisible by $a$. The probability of $a$ dividing $m$ is thus $1/a $. Similarly, that of $a$ dividing $n$ is $1/a $. We have the followings: $$P(a|m \wedge a|n) = 1/a \cdot 1/a=1/a^2\\ P(a\not\mid m \wedge a\not\mid n)=1-1/a^2\\ P((m,n)=1)=\bigg(1-\dfrac{1}{2^2}\bigg)\bigg(1-\dfrac{1}{3^2}\bigg)\bigg(1-\dfrac{1}{5^2}\bigg)\bigg(1-\dfrac{1}{7^2}\bigg)\cdots \bigg(1-\dfrac{1}{\text{prime squares}}\bigg)=\dfrac{6}{\pi^2}$$ [...]

Divisibility Criteria

You may already have been told how to tell when a number is divisible by $3$ or $9$: you add up the digits of the number and ask whether the sum of the digits is divisible by $3$ or $9$. For example, $$3\mid 1+1+3+1 \Rightarrow 3\mid 1131.$$ We actually have a theorem: let $n\in \Bbb N$, where $n$ can be expressed in base $10$ as $n=a_k a_{k-1} \cdots a_1 a_0$. (Here $a_0,a_1,\cdots,a_{k-1},a_k$ represent different digits, and they are not being multiplied together.) Then $$m=a_0+a_1+\cdots+a_{k-1}+a_k \Rightarrow n \equiv_3 m.$$
My approach to proving this theorem is first to express $n$ as $a_0+10a_1+\cdots+10^{k-1}a_{k-1}+10^ka_k$. We now look at some specific cases of this theorem: consider $n$ as a two-digit number. Then $n=a_0+10a_1$ and $m=a_0+a_1$. Observe that $n-m=9a_1$. Since $9a_1\equiv_9 0$, we have $n\equiv_9 m$. Now, consider $n$ as a three-digit number: $$\begin{align}n&=a_0+10a_1+10^2a_2\\ m&=a_0+a_1+a_2\\ n-m&=9a_1+99a_2\\ n&\equiv_9 m.\end{align}$$ Do you see a pattern? Is it clear to you now why the sum of digits works? This works because $10^k-1$ is a multiple of $9$: $$\begin{align}\vdash 10^k-1&\equiv_9 0\\ 10&\equiv_9 1\\ 10^k&\equiv_9 1^k\\ 10^k-1&\equiv_9 0\qquad\Box \end{align}$$ But then the question requires us to prove $n \equiv_3 m$. We actually have something stronger! Let us go ahead and prove that $\equiv_9\; \Rightarrow \; \equiv_3$. $$\begin{align}\vdash a\equiv_9 b &\Rightarrow a\equiv_3 b\\ a\equiv_9 b &\Rightarrow 9\mid (a-b)\\ &\Rightarrow 3\cdot 3\mid (a-b)\\ &\Rightarrow a-b=3\cdot 3k \quad \exists k\in \Bbb Z\\ &\Rightarrow a-b=3\cdot p \quad \exists p\in \Bbb Z\\ &\Rightarrow 3\mid (a-b) \\ &\Rightarrow a\equiv_3 b\qquad\Box \end{align}$$ We also have $\equiv_8\; \Rightarrow\; \equiv_4 \wedge \equiv_2$. We can generalise these results as $\equiv_n\; \Rightarrow\; \equiv_{\;\text{factors of n except 1}}$. It is still not the time to put this problem away. We can ask ourselves: are there extensions of this result? Are there related theorems provable using the same technique? Up to this point, we know when a number is divisible by $2,3,5,9$. What about the cases for $4,6,7,8$? Since we are still dealing with numbers in base $10$, we can modify our $10^k-1$ argument to $10^k-c^k$ for $c=4,6,7,8$. Observe that $$10^k\equiv_4 6^k\\ 10^k\equiv_6 4^k\\ 10^k\equiv_7 3^k\\ 10^k\equiv_8 2^k.$$ The key idea is to change the coefficients of the digits into powers of $c$. We state without proofs the followings: $$m=a_0+6a_1+\cdots+6^{k-1}a_{k-1}+6^ka_k \Rightarrow n \equiv_4 m\\
m=a_0+\color{blue}{2}a_1+\cdots+\color{blue}{2}^{k-1}a_{k-1}+\color{blue}{2}^ka_k \Rightarrow n \equiv_4 m\\
m=a_0+4a_1+\cdots+4^{k-1}a_{k-1}+4^ka_k \Rightarrow n \equiv_6 m\\ m=a_0+3a_1+\cdots+3^{k-1}a_{k-1}+3^ka_k \Rightarrow n \equiv_7 m\\ m=a_0+2a_1+\cdots+2^{k-1}a_{k-1}+2^ka_k \Rightarrow n \equiv_8 m.$$ You may then ask: when can we use these results? Here is an example. Say we want to divide $110$ by $7$. Using the above result and without resorting to division algorithm, we know that the remainder is $5$ because $110 \equiv_7 12 \equiv_7 5$. Here $12=3+3^2$ is our $m$. The 'beauty' of this result is that we are reducing a division problem into an addition problem! (Alternatively, we can argue that $110 \equiv_7 11\cdot 10 \equiv_7 4\cdot 3 \equiv_7 12 \equiv_7 5$ to have the same result.) There may still be something interesting about this theorem. Are there any applications if we switch to other number systems like hexadecimal or binary (by changing $n$)? Is there a relationship between modular arithmetic and change of base? Further extensions of the theorem: divisibility by $11,12,\cdots,n$?

More to read:
Fun With Modular Arithmetic

Reference:
Number Theory Through Inquiry by David C. Marshall, Edward Odell, and Michael Starbird