Abstract
Authors
T. Popoviciu
Keywords
Euclid’s algorithm; greatest common divisor; number of divisions; Fibonacci sequence; numeration base
Paper coordinates
T. Popoviciu, Asupra aplicării algoritmului lui Euclid pentru aflarea c.m.m.d.c. a două numere, Studii și cercetări științifice (Cluj), 4 (1953) nos. 1-2, pp. 59-63 (in Romanian).
About this paper
Journal
Studii si Cercetari Stiintifice (Cluj)
Publisher Name
Editura Academiei Republicii Populare Române
Print ISSN
Online ISSN
google scholar link
??
Paper (preprint) in HTML form
Original text
Rate this translation
Your feedback will be used to help improve Google Translate
ON THE APPLICATION OF EUCLID'S ALGORITHM TO FIND THE GCD OF TWO NUMBERS
Communication presented at the meeting of September 24, 1952 of the Cluj Branch of the RPR Academy
-
- Whethera,ba, b, two natural numbers. To find their gcd, we apply Euclid's algorithm, which consists of performing successive divisions
{:[b=qa+r","],[a=q_(1)r+r_(1)","],[r=q_(2)r_(1)+r_(2)","],[(1) cdots cdots cdots cdots cdots],[r_(n-2)=q_(n)r_(n-1)+r_(n)","],[r_(n-1)=q_(n+1)r_(n).]:}\begin{align*}
& b=q a+r, \\
& a=q_{1} r+r_{1}, \\
& r=q_{2} r_{1}+r_{2}, \\
& \cdots \cdots \cdots \cdots \cdots \tag{1}\\
& r_{n-2}=q_{n} r_{n-1}+r_{n}, \\
& r_{n-1}=q_{n+1} r_{n} .
\end{align*}
We can assumeb > ab>aThe floorsq,q_(1),dots,q_(n+1)q, q_{1}, \ldots, q_{n+1}are positive integers, and the remaindersr,r_(1),dots dots,r_(n)r, r_{1}, \ldots \ldots, r_{n}are also integers and positive and check inequalities
a > r > r_(1) > dots > r_(n) > 0a>r>r_{1}>\ldots>r_{n}>0
To find cmmdcr_(n)r_{n}of numbersa,ba, b, must, according to table (1), be carried outn+2n+2division^(1){ }^{1}). The number of divisions can be interestingly delimited according to the smallest of the numbersaaandbb(i.e.aa). We have in this regard the following well-known result: [1].
THEOREM 1. - The number of divisions that must be performed to find the gcd of two positive integers is at most equal to 5 times the number of digits of the smallest of these numbers.
A simple proof of this theorem was given by PL C eb â ş ev [2]. In the following we will show that C eb âşev's method allows us to specify Theorem 1 a little.
2. - We haveq_(i) >= 1,i=1,2,dots,n+1q_{i} \geqq 1, i=1,2, \ldots, n+1and, taking into accountr_(n-1) >= r_(n)r_{n-1} \geq r_{n}we even deduceq_(n+1) >= 2q_{n+1} \geqq 2. Formulas (1) then give us
(2)
2. - We haveq_(i) >= 1,i=1,2,dots,n+1q_{i} \geqq 1, i=1,2, \ldots, n+1and, taking into accountr_(n-1) >= r_(n)r_{n-1} \geq r_{n}we even deduceq_(n+1) >= 2q_{n+1} \geqq 2. Formulas (1) then give us
(2)
{:[a >= r+r_(1)],[r >= r_(1)+r_(2)],[r_(1) >= r_(2)+r_(3)],[ cdots cdots cdots cdots],[r_(n-2) >= r_(n-i)+r_(n)],[r_(n-i) >= 2r_(n)]:}\begin{aligned}
& a \geqq r+r_{1} \\
& r \geqq r_{1}+r_{2} \\
& r_{1} \geqq r_{2}+r_{3} \\
& \cdots \cdots \cdots \cdots \\
& r_{n-2} \geqq r_{n-i}+r_{n} \\
& r_{n-i} \geqq 2 r_{n}
\end{aligned}
Taking into account (5) and (7) we therefore deduce
a > 11^((n+1)/(5))a>11^{\frac{n+1}{5}}
Ifkkis the number of digits of written in the base 11 number system, we havea < 11^(k)a<11^{k}, son+1 < 5kn+1<5 k, that isn+2 <= 5kn+2 \leqq 5 kWe can, however, state the following property:
THEOREM 2. - The number of divisions that must be performed to find the common denominator of two positive integers is at most equal to 5 times the number of digits of the smallest of these numbers, written in the base 11 number system.
3. - The previous result can be generalized a little further.
3. - The previous result can be generalized a little further.
Whetherlla natural number and calculate on [alpha^(l)\alpha^{l}], that is, the whole part ofalpha l,alpha\alpha l, \alphabeing the positive root of equation (6). It is easily proven, by complete induction, that
alpha^(l)=u_(l-1)alpha+u_(l-2)\alpha^{l}=u_{l-1} \alpha+u_{l-2}
from where
{:(9)[alpha^(l)]=[u_(l-1)alpha]+u_(l-2).:}\begin{equation*}
\left[\alpha^{l}\right]=\left[u_{l-1} \alpha\right]+u_{l-2} . \tag{9}
\end{equation*}
We now have
LEM 2. - If α is the positive root of equation (6) andu_(n)u_{n}terms of the series (3), we have
LEM 2. - If α is the positive root of equation (6) andu_(n)u_{n}terms of the series (3), we have
{:(10)[u_(n)alpha]=u_(n+1)-(1-(-1)^(n))/(2)","quad n=0","1","dots:}\begin{equation*}
\left[u_{n} \alpha\right]=u_{n+1}-\frac{1-(-1)^{n}}{2}, \quad n=0,1, \ldots \tag{10}
\end{equation*}
(6)
1,1,2,3,5,8,13,21,dots dots1,1,2,3,5,8,13,21, \ldots \ldots
Let us now consider the sequence of numbers
(3)
where the first term is equal to the sum of the two preceding terms. The sequence (3) is therefore defined by the recurrence relation.
(4)
(3)
where the first term is equal to the sum of the two preceding terms. The sequence (3) is therefore defined by the recurrence relation.
(4)
u_(o)=u_(1)=1,quadu_(m)=u_(m-1)+u_(m-2),quadm_(i)^(')=2,3,dotsu_{o}=u_{1}=1, \quad u_{m}=u_{m-1}+u_{m-2}, \quad m_{i}^{\prime}=2,3, \ldots
Taking into account (4) and eliminatingr,r_(1),dots,r_(n-1)r, r_{1}, \ldots, r_{n-1}from inequalities (2), we deducea >= u_(n+2)i_(n)a \geqq u_{n+2} i_{n}so
(5)
(5)
a >= u_(n+2).a \geqq u_{n+2} .
This inequality delimits thenndepending onaa.
We now have the following
LEMMA 1. - If a is the positive root of the equation(alpha=(1+sqrt5)/(2))\left(\alpha=\frac{1+\sqrt{5}}{2}\right)
HAVE
We now have the following
LEMMA 1. - If a is the positive root of the equation(alpha=(1+sqrt5)/(2))\left(\alpha=\frac{1+\sqrt{5}}{2}\right)
HAVE
x^(2)-x-1=0x^{2}-x-1=0
(7)
u_(m) >= alpha^(m-1),quad m=0,1,dotsu_{m} \geqq \alpha^{m-1}, \quad m=0,1, \ldots
The proof is easily done by complete induction, taking into account (4).
It is easy to verify that we have
(8)
(8)
alpha > (8)/(5).\alpha>\frac{8}{5} .
Taking into account equation (6) we deduce
and from (8) it follows that
and from (8) it follows that
alpha^(5)=alpha^(4)+alpha^(3)=alpha^(3)(alpha+1)=alpha(alpha+1)^(2)=alpha(3alpha+2)=5alpha+3\alpha^{5}=\alpha^{4}+\alpha^{3}=\alpha^{3}(\alpha+1)=\alpha(\alpha+1)^{2}=\alpha(3 \alpha+2)=5 \alpha+3
alpha^(5) > 5*(8)/(5)+3=11\alpha^{5}>5 \cdot \frac{8}{5}+3=11
THEOREM 3. - The number of divisions that must be performed to find the gcc of two positive integers is at most equal to l times the number of digits of the smallest of these numbers written in a number system with a base at most equal to the numbergg, that the formula (11).
In this statement, we also took into account the fact that the number of digits of a number decreases when the base in which this number is written increases.
For allgiven the base of numeration that gives us the best limitation, according to the previous method, is preciselyggForl=5l=5is foundg=11g=11For the first 15 values ​​ofl( >= 2)l(\geqq 2), the baseggthe most advantageous is given in the table
| ll | gg | ll | gg | ll | gg |
| 2 | 2 | 7 | 29 | 12 | 321 |
| 3 | 4 | 8 | 46 | 13 | 521 |
| 4 | 6 | 9 | 76 | 14 | 842 |
| 5 | 11 | 10 | 122 | 15 | 1364 |
| 6 | 17 | 11 | 199 | 16 | 2205 |
Faculty of Mathematics and Physics of the "V. Babeș" University of Chuj
BIBLIOGRAPHY
- IM Vinogradov, Osnovî teorii cisel, Moskva-Leningrad, 1949, pag. 22.
- D. Seliwanoff, Textbook of Differential Calculus, 1904, pp. 91-92.
SUMMARY
On the application of Euclidean algorithm to find the greatest common divisor of two numbers
tiveriu ps covic
A little catch-up method by P. L. Chebashev for finding the pure divisions necessary to determine the greatest common divisor of two natural numbersa,b(a < 1)a, b(a<1), we note that in the classical expression in relation to the shortaa, which must be taken, the base 10 of the numerical system can be replaced by 11. Considering a slightly more general problem, we find that base 11 is in some sense the most intuitive.
SUMMARY.
On determining the greatest common divisor (GCD) of two numbers using Euclid's algorithm.
by
TIBERIU POPOVICIU
By slightly expanding on PL Cebàşev's method for determining the number of divisions needed to obtain the greatest common divisor (GCD) of two natural numbersaa, b(a < b)b(a<b)We note that in the well-known statement, relating to the multiple of a that we must take, the base 10 of the number system can be replaced by 11. By examining a slightly more general problem, we find that the base 11, in a certain sense, is the best.
- ^(1){ }^{1}) His divisionr_(n-1)r_{n-1}byr_(n)r_{n}can be avoided if its divisibilityr_(n-1)r_{n-1}byr_(n)r_{n}is immediately recognized in another way. This always happens when=1=1.