Full Euclidean Algorithm by Means of a Steady Walk

Carlos M. Falcon Rodriguez¹, Maria A. Garcia Cruz¹, Claudia Falcon²

¹Grupo de Investigación de Análisis Matemático, Instituto de Formación docente Salomé Ureña, Santo Domingo, D.N., República Dominicana.
²Wake Forest University, Winstom-Salem, NC, USA.

DOI: 10.4236/am.2021.124018                

Abstract

Let x and y be two positive real numbers with x < y. Consider a traveler, on the interval [0, y/2], departing from 0 and taking steps of length equal to x. Every time a step reaches an endpoint of the interval, the traveler rebounds off the endpoint in order to complete the step length. We show that the footprints of the traveler are the output of a full Euclidean algorithm for x and y, whenever y/x is a rational number. In the case that y/x is irrational, the algorithm is, theoretically, not finite; however, it is a new tool for the study of its irrationality.

Keywords

Extended Euclidean Algorithm, Greatest Common Divisor, Incommensurable Numbers, Steady Walk, Diophantine Equation

1. Introduction

The Euclidean greatest common divisor ( $gcd$ ) algorithm is one of the most successful algorithms in Mathematics. Its improvements, like Lehmer’s $gcd$ algorithm [1], are currently being used in cryptography protocols to factorize large composite numbers [2]. Examples of $gcd$ ’s application in Number Theory are: the Diophantine equations [3], the Chinese remainder theorem [4], and continued fractions [5]. The $gcd$ algorithm also inspired Gabriel Lamé in the creation of the computational complexity theory [6]. Euclid gave expression to the $gcd$ algorithm in the propositions of Book Seven of Euclid’s Elements [7]. He used concepts about divisibility and relatively prime numbers that may have taken the focus away from the case when the numbers are not integers. However, it is known that the algorithm works with real numbers, even though there are not many current references on this topic. But in fact, the concept of $gcd$ has historically also used the name “greatest common measure’’ [7], indicating the measurement of real magnitudes.

In this paper, we present an algorithm that finds inspiration in Euclid’s $gcd$ algorithm and Eudoxus’ proportion theory [8]. The impeccable theory of proportions of Eudoxus dates some decades before Euclid and uses the simple idea of fitting integer multiples of two real numbers with the intention of defining their ratio. In the next paragraphs, we provide some preliminary definitions and review useful background for later reference.

Let $x$ and $y$ be positive real numbers. Considering the fraction $y/x$, we distinguish two cases, the case where $y/x$ is a rational, and the case where $y/x$ is an irrational. If $y/x$ is a rational, we denote $SF\left(y/x\right)$ as the unique simplified fraction $a/b$, with $a$ and $b$ natural numbers and $gcd\left(a\mathrm{,}b\right)=1$, such that

$\frac{y}{x}=SF\left(y/x\right)\mathrm{.}$ (1)

The positive real number $z$ is a divisor of $x$ whenever there exists a natural number $k$ fulfilling $kz=x$. Each time the set of common divisors of $x$ and $y$ is not empty, the greatest common divisor of $x$ and $y$, $gcd\left(x\mathrm{,}y\right)$ is the maximum $z$ that is a divisor of $x$ and is also a divisor of $y$. In the case that the set of common divisors of $x$ and $y$ is empty, we say that $x$ and $y$ are incommensurable.

The relation between the previous definitions of $SF$ and $gcd$, is that when $z$ is the greatest common divisor of $x$ and $y$, and $kz=x$, $mz=y$, we have that $mkz=mx,kmz=ky$. Consequently,

$\left(\frac{m}{k}x=y\right)\wedge \left(\frac{k}{m}y=x\right)\mathrm{,}$ (2)

and

$\left(\frac{m}{k}=SF\left(\frac{y}{x}\right)\right)\wedge \left(\frac{k}{m}=SF\left(\frac{x}{y}\right)\right).$ (3)

The veracity of (3) is a consequence of the simple fact that if $gcd\left(k\mathrm{,}m\right)=d$ and $d>1$, then the $gcd\left(x\mathrm{,}y\right)$ would be equal to $zd$ instead of $z$.

The previous definition of $gcd\left(x\mathrm{,}y\right)$ for $x$ and $y$ reals is not new. Indeed, the original version of the Euclidean algorithm works with quantities represented by segments. Its inspiration was to measure one segment with another. The algorithm that we present in Section 2 recovers this original meaning, which can be insightful even for children in elementary school.

The extended Euclidean algorithm, described in [9], has many applications in the solution of Diophantine equations [10] [11]. Improving its performance is a frequent subject in publications [12]. In all the rediscoveries and improvements that we can find since the 5th-6th century to our days, the Euclid’s way to find $gcd$ is the cornerstone. The algorithm we present in Section 2 is not only a way to get the solution of the Diophantine equation,

$mx+ny=gcd\left(x\mathrm{,}y\right)\mathrm{,}$ (4)

but it also provides a complete arithmetic in $x\mathbb{Z}/y\mathbb{Z}$, the ring of the residue classes modulo $y$. The “steady walk” algorithm ( $swa$ ) described in this paper does not use the Euclidean algorithm for $gcd$. The proof we give in Section 2 is interesting by itself and uses the following not common formula of $\tan \left(n\theta \right)$ as a function of $\tan \left(\theta \right)$, when $\tan \left(\theta \right)\ne \infty$ and $n\ge 1$,

$\tan \left(n\theta \right)=\frac{{\displaystyle {\sum }_{k=0}^{\lfloor \left(n-1\right)/2\rfloor }{\left(-1\right)}^k\left(\begin{array}{c}n\\ 2k+1\end{array}\right){\tan }^{2k+1}\left(\theta \right)}}{{\displaystyle {\sum }_{k=0}^{\lfloor n/2\rfloor }{\left(-1\right)}^k\left(\begin{array}{c}n\\ 2k\end{array}\right){\tan }^{2k}\left(\theta \right)}}.$ (5)

The formula (5) can be proven by mathematical induction, using the tangent of the sum of two angles. The integers $\lfloor \left(n-1\right)/2\rfloor$ and $\lfloor n/2\rfloor$ are the floor function values on $\left(n-1\right)/2$ and $n/2$ respectively. Let

$P_n\left(x\right)={\displaystyle \underset{k=0}{\overset{\lfloor \left(n-1\right)/2\rfloor }{\sum }}}{\left(-1\right)}^k\left(\begin{array}{c}n\\ 2k+1\end{array}\right)x^{2k+1}.$ (6)

Consequently, in the case that $\tan \left(x\right)\ne \infty$, the formula (5) implies that

$\tan \left(nx\right)=0\iff P_n\left(\tan \left(x\right)\right)=0.$ (7)

The rest of this article is organized in the following way. Section 2 explains the $swa$ and presents its formal description with the necessary proof. In Section 3, the implementation of the algorithm provides interesting resulting examples. And finally, we present a concluding section.

2. The Algorithm

Let $x$ and $y$ be positive real numbers, with $x<y$. The $swa$ consists in marking, between two “walls”, consecutive steps, with step length equal to $x$. The walls are at 0 and at $y/2$ of the real line. The first step begins at the 0 wall. If a step has not finished when it meets a wall, it rebounds off the wall in order to complete the step length. The walk only changes direction when the steps meet and rebound off the walls.

Formalizing the previous description, we write,

$f:\left[0,+\infty \right[\backslash \left\{\left(ky/2\right):k\in \mathbb{Z},k>0\right\}\to \left[0,y/2\right],$

defined by: $f\left(0\right)=0$ and

$f\left(t\right)=(\begin{array}{l}t-ny/2\mathrm{,}t\in \left(\frac{ny}{2}\mathrm{,}\frac{\left(n+1\right)y}{2}\right)\wedge n\text{is}\text{even}\\ \left(n+1\right)y/2-t\mathrm{,}t\in \left(\frac{ny}{2}\mathrm{,}\frac{\left(n+1\right)y}{2}\right)\wedge n\text{is}\text{odd}\mathrm{.}\end{array}$ (8)

Then the mark of the $m$ -step is $f\left(mx\right)$.

Theorem 1. If the set

$F=\left\{s\in \mathbb{N}:\left(\exists t\in \mathbb{N},t<s,f\left(sx\right)=f\left(tx\right)\right)\vee \left(f\left(sx\right)=y/2\right)\right\}$ (9)

is not empty and we call $k+1=\min \left(F\right)$, then the following statements are true:

1) The set $\left\{f\left(mx\right)\mathrm{<mo>\; :\; </mo>}m\in \left[\mathrm{0,}k\right]\right\}$ is an array of equidistant points.

2) The distance between contiguous points is the $gcd\left(x\mathrm{,}y\right)=d$.

3) The distance between the maximum of $\left\{f\left(mx\right)\mathrm{<mo>\; :\; </mo>}m\in \left[\mathrm{0,}k\right]\right\}$ and $y/2$ is equal to $d$ or $d/2$.

4) If $b$ is the number of points that are less than the first step, then $bd=x$. Additionally, $y=\left(2k+2\right)d\vee y=\left(2k+1\right)d$, in correspondence to the disjunction in item 3, respectively.

5) $\left(2k+2\right)/b=SF\left(y/x\right)\vee \left(2k+1\right)/b=SF\left(y/x\right)$, in correspondence to the above disjunction respectively.

6) If the point id of the array, corresponds to the $m_i$ -step, then,

$m_{i}b\equiv \pm i\left(\mathrm{mod}\left(2k+2\right)\right)\vee m_{i}b\equiv \pm i\left(\mathrm{mod}\left(2k+1\right)\right)\mathrm{,}$

in correspondence to the above disjunction respectively.

Proof. Let us visualize the algorithm in the following way:

Construct a circle of radius equal to $y/\pi$. In this way the semicircle has a length equal to $y$, and the quarter circle is $y/2$ long. The steps will go from the point of zero angle, counterclockwise and each step has length $x$ on the circle. If $mx$ is the $m$ -step, the angle in radians of this point is $mx\pi /y$. We denote the before angle as $\angle x_m$. There is only one angle, $\angle {\tilde{x}}_m$ in the first quadrant fulfilling,

${\tan }^2\left(\angle x_m\right)={\tan }^2\left(\angle {\tilde{x}}_m\right)\mathrm{.}$ (10)

Simple observation shows that the steps ${\tilde{x}}_m$ map on the steps $f\left(mx\right)$ under the natural bijection between the segment $\left[0,y/2\right]$ and the first quarter circle. In the case that there exists $t$, $t<s$, with $f\left(sx\right)=f\left(tx\right)$, we have that ${\tilde{x}}_s={\tilde{x}}_t$ and consequently,

$\left(sx\pi /y=\pm tx\pi /y+m\pi \mathrm{,}m\in \mathbb{Z}\right)$ (11)

$\Updownarrow$

$\left(sx=\pm tx+my\mathrm{,}m\in \mathbb{Z}\right)$ (12)

$\Updownarrow$

$\left(\frac{s\mp t}{m}x=y\mathrm{,}m\in \mathbb{Z}\right)\mathrm{.}$ (13)

The last equality (13) is a consequence of $\left(s\mp t\ne 0\Rightarrow m\ne 0\right)$. Hence, we can suppose that there exist $a$ and $b$, fulfilling

$\frac{a}{b}x=y\text{,}\text{with}a\mathrm{,}b\in \mathbb{N}\text{and}gcd\left(a\mathrm{,}b\right)=1.$ (14)

The case $f\left(sx\right)=y/2$ is equivalent to

$sx=2ky+y/2\mathrm{,}k\in \mathbb{N}\mathrm{.}$ (15)

Similarly, we conclude that there exist $a$ and $b$, fulfilling,

$\frac{a}{b}x=y\text{,}\text{with}a\mathrm{,}b\in \mathbb{N}\text{and}gcd\left(a\mathrm{,}b\right)=1.$ (16)

From (16), we obtain

$\tan \left(a\angle \frac{nx}{b}\right)=\tan \left(\angle a\frac{nx}{b}\right)=\tan \left(n\pi \right)=\mathrm{0,}n\in \mathbb{N}\mathrm{.}$ (17)

Let $A=\left\{\mathrm{1,2,}\cdots \mathrm{,}\lfloor \left(a-1\right)/2\rfloor \right\}$. It is easy to verify that,

1) $n\in A\Rightarrow \left(\tan \left(\angle \left(nx/b\right)\right)\ne 0\wedge \tan \left(\angle \left(nx/b\right)\right)\ne \infty \right),$

2) $\left(n,m\in A\wedge n\ne m\right)\Rightarrow {\tan }^2\left(\angle \left(nx/b\right)\right)\ne {\tan }^2\left(\angle \left(mx/b\right)\right),$

and,

$P_a\left(\tan \left(\angle \left(nx/b\right)\right)\right)=\mathrm{0,}n\in A\mathrm{.}$ (18)

The set of equalities (18) can be written as

${\displaystyle \underset{k=0}{\overset{\lfloor \left(a-1\right)/2\rfloor }{\sum }}}{\left(-1\right)}^k\left(\begin{array}{c}a\\ 2k+1\end{array}\right){\left(\tan \left(\angle \left(nx/b\right)\right)\right)}^{2k+1}=0,n\in A.$ (19)

Dividing each equation by $\tan \left(\angle \left(nx/b\right)\right)\ne 0$, we get

${\displaystyle \underset{k=0}{\overset{\lfloor \left(a-1\right)/2\rfloor }{\sum }}}{\left(-1\right)}^k\left(\begin{array}{c}a\\ 2k+1\end{array}\right){\left({\tan }^2\left(\angle \left(nx/b\right)\right)\right)}^k=0.$ (20)

Denoting $x_k={\left(-1\right)}^k\left(\begin{array}{c}a\\ 2k+1\end{array}\right)$, we have,

${\displaystyle \underset{k=0}{\overset{\lfloor \left(a-1\right)/2\rfloor }{\sum }}}{\left({\tan }^2\left(\angle \left(nx/b\right)\right)\right)}^k{x}_k=0,n\in A.$ (21)

We can interpret the set of equalities (21) as a system of linear equations with unknown variables $\left\{x_k\right\}$. This is a system where the number of variables exceeds by one the number of equations.

We now observe that, if for some $m\in A$ we have

$\tan \left(\angle \left(mx\right)\right)\ne 0\wedge \tan \left(\angle \left(mx\right)\right)\ne \infty$ (22)

and

${\tan }^2\left(\angle \left(mx\right)\right)\ne {\tan }^2\left(\angle \left(nx/b\right)\right)\mathrm{,}\text{for}\text{all}n\in A\mathrm{,}$ (23)

we also have

$P_a\left(\tan \left(\angle mx\right)\right)=\tan \left(a\angle \left(mx\right)\right)=\tan \left(\angle \left(amx\right)\right)=\tan \left(bm\pi \right)=0.$ (24)

Then, we would have the square system,

${\displaystyle \underset{k=0}{\overset{\lfloor \left(a-1\right)/2\rfloor }{\sum }}}{\left({\tan }^2\left(\angle \left(nx/b\right)\right)\right)}^k{x}_k=0,n\in A,$ (25)

${\displaystyle \underset{k=0}{\overset{\lfloor \left(a-1\right)/2\rfloor }{\sum }}}{\left({\tan }^2\left(\angle \left(mx\right)\right)\right)}^k{x}_k=0,$ (26)

whose determinant is equal to a non-null Vandermonde determinant. This is a contradiction due to the existence of the non-null solution $\left\{x_k\right\}$.

Let us examine what is failing. Checking (22),

$\left(\tan \left(\angle \left(mx\right)\right)=0\vee \tan \left(\angle \left(mx\right)\right)=\infty \right)\Rightarrow mx=ky/2\mathrm{,}k\in \mathbb{Z}$ (27)

$\Rightarrow 2mb=ka,k\in \mathbb{Z}.$

The last equality in (27) implies that $a$ divides $\text{2}m$. This is impossible because $m\in A$. Hence, the only possibility is that (23) fails. In other words, for each $m\in A$, there exist $n\in A$ fulfilling,

${\tan }^2\left(\angle \left(mx\right)\right)={\tan }^2\left(\angle \left(nx/b\right)\right)\mathrm{.}$ (28)

Also, it is easy to check that the values $\left\{{\tan }^2\left(\angle \left(mx\right)\right)\mathrm{<mo>\; /\; </mo>}m\in A\right\}$ are different,

${\tan }^2\left(\angle \left(mx\right)\right)={\tan }^2\left(\angle \left(m_{1}x\right)\right)\Rightarrow mx=\pm m_{1}x+ky$ (29)

$\Rightarrow b\left(m\mp m_1\right)=ka\mathrm{.}$

From (29), we have that $m\mp m_1=0$, which clearly implies $m=m_1$. Therefore, by the Pigeonhole Principle, there exists a bijective function $f$ such that

$f\mathrm{<mo>\; :\; </mo>}A\to A$ (30)

$n\to m_n\mathrm{,}$

is defined by the property,

${\tan }^2\left(\angle \left(m_{n}x\right)\right)={\tan }^2\left(\angle \left(nx/b\right)\right)\mathrm{.}$ (31)

Now, we observe that,

$k=\text{Cardinality}\left(A\right)=\lfloor \frac{a-1}{2}\rfloor =(\begin{array}{l}\left(a-2\right)/2\text{with}a\text{even}\\ \left(a-1\right)/2\text{with}a\text{odd}\mathrm{,}\end{array}$ (32)

and $d=x/b$, so the first five points of the theorem are straightforward. Recapitulating,

1) The set $\left\{f\left(mx\right)\mathrm{<mo>\; :\; </mo>}m\in \left[\mathrm{0,}k\right]\right\}$ corresponds to the set of steps in the first quadrant $\left\{{\tilde{x}}_m\right\}$, and this last set corresponds to the angles $\left\{\angle \left(nx/b\right)\mathrm{<mo>\; :\; </mo>}n\in A\right\}$.

2) $d=x/b$ is the arc length between contiguous points of the array. Furthermore,

$a\left(\frac{x}{b}\right)=y\wedge b\left(\frac{x}{b}\right)=x.$ (33)

3) When $a$ is even, the maximum of the array of steps is

$\left(\frac{a-2}{2}\right)\left(\frac{x}{b}\right)=\left(\frac{1}{2}\right)\left(\frac{a}{b}\right)x-d=\left(\frac{y}{2}\right)-d.$ (34)

And when $a$ is odd, the maximum is

$\left(\frac{a-1}{2}\right)\left(\frac{x}{b}\right)=\left(\frac{1}{2}\right)\left(\frac{a}{b}\right)x-\frac{d}{2}=\left(\frac{y}{2}\right)-\frac{d}{2}.$ (35)

4) The equality $bd=x$ is a consequence of item 2. Additionally, when $a$ is even,

$\left(\frac{a-2}{2}\right)=k,$ (36)

and $y=ad=\left(2k+2\right)d$. When $a$ is odd,

$\left(\frac{a-1}{2}\right)=k,$ (37)

and $y=ad=\left(2k+1\right)d$.

5) In the case $a$ is even,

$\frac{a}{b}=\frac{2k+2}{b}=SF\left(y/x\right).$ (38)

And when $a$ is odd,

$\frac{a}{b}=\frac{2k+1}{b}=SF\left(y/x\right).$ (39)

Finally, let us prove item 6,

${\tan }^2\left(\angle \left(m_{i}x\right)\right)={\tan }^2\left(\angle \left(ix/b\right)\right)$ (40)

$\Downarrow$

$m_{i}x=\pm \left(ix/b\right)+my,m\in \mathbb{Z}$ (41)

$\Downarrow$

$m_i\frac{by}{a}\mp i\frac{y}{a}=my,m\in \mathbb{Z}$ (42)

$\Downarrow$

$m_{i}b\mp i=ma,m\in \mathbb{Z}.$ (43)

The previous sequence of implications (40)-(43) finishes the proof of the theorem. □

Note that the equality (43) is equivalent to

$m_{i}x\mp i\frac{x}{b}=my,m\in \mathbb{Z},$ (44)

and this last equality (44) justifies that the $swa$ provides a complete arithmetic in $x\mathbb{Z}/y\mathbb{Z}$, as stated in the introduction.

3. Implementation and Examples

In this section, we show the process of the algorithm described in Section 2 as a pseudocode. The examples and figures were implemented using the python programming language. In the figures, we mark the steps corresponding to each complete path of $\left[0,y/2\right]$ on different segments of a polygonal curve. See Figures 1-3. The geometrical behavior displayed in the plots change with the two numbers, x and y, in the Algorithm 1 and with the number of iterations $N$.

Algorithm 1. Steady walk algorithm.

Example 1: The steady walk algorithm ( $swa$ ) for two integers, $x=143$ and $y=847$, with $N=200$ iterations. As seen in Figure 1, the algorithm stops at the iteration (847/2)/11. In this case the Euclidean algorithm for $gcd$ only needs two divisions and the $swa$ obtains two footprints, 286 and 275, with difference equal to the $gcd$ after two sums and two differences.

Figure 1. Output of $swa$ for $x=143$ and $y=847$. The plot shows the steps $P\left[n\right]$ vs. the iteration number $n$. The table lists the numerical values of all points.

Figure 1. Output of $swa$ for $x=143$ and $y=847$. The plot shows the steps $P\left[n\right]$ vs. the iteration number $n$. The table lists the numerical values of all points.

Example 2: The $swa$ for the numbers $x=1$ and the irrational $y=\pi$, with $N=55$ iterations. These two numbers $x$ and $y$ are incommensurable. We choose this particular number of iterations $N$ so that it shows interesting regular patterns (see Figure 2).

Figure 2. Output of $swa$ for $x=1$ and $y=\pi$. The plot shows the steps $P\left[n\right]$ vs. the iteration number $n$. The table lists the numerical values of all points.

Example 3: Figure 3 shows the $swa$ for two irrational numbers, $x=\sqrt{2}$ and $y=\text{e}$, with $N=200$ iterations.

Figure 3. Output of $swa$ for $x=\sqrt{2}$ and $y=\text{e}$. The plot shows the steps $P\left[n\right]$ vs. the iteration number n.

4. Conclusion

The full Euclidean algorithm that we present in this paper has advantages in several aspects. As a result of its graphical output, it can be a very useful tool in the mathematical explanations about incommensurability, irrationality, great common divisor, solution of the Diophantine Equation (4) and arithmetic in the ring $\mathbb{Z}a$, of residue classes modulo $a$. Another advantage is the improvement of the extended Euclidean algorithm. The process can be expedited since the difference between any two footprints is a new candidate to redirect the algorithm toward a shorter path. In fact, to begin with $y/2$, instead of $y$, is already a clear improvement. The last aspect we would like to mention is the study of irrationality. The distribution of footprints in $\left[0,y/2\right]$, when the number of steps increases, is a promising tool in the understanding of different kinds and grades of irrationality, and the Diophantine approximation. Some related results can be found in [13]. Finally, $swa$ is conceptually easier than the extended and classic Euclidean algorithms, allowing many shortcuts that improve its efficiency.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Lehmer, D.H. (1938) Euclid’s Algorithm for Large Numbers. The American Mathematical Monthly, 45, 227-233. https://doi.org/10.1080/00029890.1938.11990797
[2]	Durand, A. (1998) Efficient Ways to Implement Elliptic Curve Exponentiation on a Smart Card. International Conference on Smart Card Research and Advanced Applications, Springer, Berlin, 357-365. https://doi.org/10.1007/10721064_33
[3]	Mordell, L.J. (1969) Diophantine Equations. Academic Press, London, New York.
[4]	Childs, L.N. (2009) A Concrete Introduction to Higher Algebra. ch. The Chinese Remainder Theorem. Springer-Verlag, New York, 253-281. https://doi.org/10.1007/978-0-387-74725-5
[5]	Khinchin, A.Y. (1997) Continued Fractions, Russian ed. Dover Publications, New York.
[6]	Lamé, G. (1844) Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Acad. Sci., Paris.
[7]	Heiberg, J.L. (2007) Euclid’s Elements. Richard Fitzpatrick, TX, USA.
[8]	Nikolic, M. (1974) The Relation between Eudoxus’ Theory of Proportions and Dedekind’s Theory of Cuts. In: Cohen, R.S., Stachel, J.J. and Wartofsky, M.W., Eds., For Dirk Struik, Springer, Dordrecht, 225-243. https://doi.org/10.1007/978-94-010-2115-9_19
[9]	Knuth, D.E. (2014) Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional, Boston.
[10]	Ramachandran, P. (2006) Use of Extended Euclidean Algorithm in Solving a System of Linear Diophantine Equations with Bounded Variables. In: Hess, F., Pauli, S. and Pohst, M., Eds., Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, Vol 4076. Springer, Berlin, Heidelberg, 182-192. https://doi.org/10.1007/11792086_14
[11]	Rankin, S. (2013) The Euclidean Algorithm and the Linear Diophantine Equation ax + by = gcd (a,b). The American Mathematical Monthly, 120, 562-564. https://doi.org/10.4169/amer.math.monthly.120.06.562
[12]	Iliev, A. and Kyurkchiev, N. (2018) The Faster Euclidean Algorithm. Collection of Scientific Works from Conference, Pamporovo, Bulgaria, 28-30.
[13]	Niven, I. (1956) Irrational Numbers. (Carus Mathematical Monographs, Series Number 11). John Wiley and Sons, Inc., New York. https://doi.org/10.5948/9781614440116