On the use of the Euclid algorithm for finding the the greatest common divisor of two numbers

Tiberiu Popoviciu
(original), Algebra, paper

Abstract

Authors

T. Popoviciu
Institutul de Calcul

Keywords

?

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).

PDF

https://ictp.acad.ro/scm/journal/article/view/239/239

About this paper

Journal

Studii si Cercetari Stiintifice (Cluj)

Publisher Name

Academy of the Republic of S.R.

DOI

https://ictp.acad.ro/scm/journal/article/view/239

Print ISSN
Online ISSN

google scholar link

??

Paper (preprint) in HTML form

scm,+1953-Popoviciu2
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

TIBERIU POPOVICIUCorresponding member of the RPR Academy

Communication presented at the meeting of September 24, 1952 of the Cluj Branch of the RPR Academy
    • Whether a , b a , b a,ba, ba,b, two natural numbers. To find their gcd, we apply Euclid's algorithm, which consists of performing successive divisions
b = q a + r , a = q 1 r + r 1 , r = q 2 r 1 + r 2 , (1) ⋯ ⋯ ⋯ ⋯ ⋯ r n − 2 = q n r n − 1 + r n , r n − 1 = q n + 1 r n . b = q a + r , a = q 1 r + r 1 , r = q 2 r 1 + r 2 , (1) ⋯ ⋯ ⋯ ⋯ ⋯ r n − 2 = q n r n − 1 + r n , r n − 1 = q n + 1 r n . {:[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*}b=qa+r,a=q1r+r1,r=q2r1+r2,(1)⋯⋯⋯⋯⋯rn−2=qnrn−1+rn,rn−1=qn+1rn.
We can assume b > a b > a b > ab>ab>aThe floors q , q 1 , … , q n + 1 q , q 1 , … , q n + 1 q,q_(1),dots,q_(n+1)q, q_{1}, \ldots, q_{n+1}q,q1,…,qn+1are positive integers, and the remainders r , r 1 , … … , r n r , r 1 , … … , r n r,r_(1),dots dots,r_(n)r, r_{1}, \ldots \ldots, r_{n}r,r1,……,rnare also integers and positive and check inequalities
a > r > r 1 > … > r n > 0 a > r > r 1 > … > r n > 0 a > r > r_(1) > dots > r_(n) > 0a>r>r_{1}>\ldots>r_{n}>0a>r>r1>…>rn>0
To find cmmdc r n r n r_(n)r_{n}rnof numbers a , b a , b a,ba, ba,b, must, according to table (1), be carried out n + 2 n + 2 n+2n+2n+2division 1 1 ^(1){ }^{1}1). The number of divisions can be interestingly delimited according to the smallest of the numbers a a aaaand b b bbb(i.e. a a aaa). 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 have q i ≧ 1 , i = 1 , 2 , … , n + 1 q i ≧ 1 , i = 1 , 2 , … , n + 1 q_(i) >= 1,i=1,2,dots,n+1q_{i} \geqq 1, i=1,2, \ldots, n+1qi≧1,i=1,2,…,n+1and, taking into account r n − 1 ≥ r n r n − 1 ≥ r n r_(n-1) >= r_(n)r_{n-1} \geq r_{n}rn−1≥rnwe even deduce q n + 1 ≧ 2 q n + 1 ≧ 2 q_(n+1) >= 2q_{n+1} \geqq 2qn+1≧2. Formulas (1) then give us
(2)
a ≧ r + r 1 r ≧ r 1 + r 2 r 1 ≧ r 2 + r 3 ⋯ ⋯ ⋯ ⋯ r n − 2 ≧ r n − i + r n r n − i ≧ 2 r n a ≧ r + r 1 r ≧ r 1 + r 2 r 1 ≧ r 2 + r 3 ⋯ ⋯ ⋯ ⋯ r n − 2 ≧ r n − i + r n r n − i ≧ 2 r n {:[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}a≧r+r1r≧r1+r2r1≧r2+r3⋯⋯⋯⋯rn−2≧rn−i+rnrn−i≧2rn
Taking into account (5) and (7) we therefore deduce
a > 11 n + 1 5 a > 11 n + 1 5 a > 11^((n+1)/(5))a>11^{\frac{n+1}{5}}a>11n+15
If k k kkkis the number of digits of written in the base 11 number system, we have a < 11 k a < 11 k a < 11^(k)a<11^{k}a<11k, so n + 1 < 5 k n + 1 < 5 k n+1 < 5kn+1<5 kn+1<5k, that is n + 2 ≦ 5 k n + 2 ≦ 5 k n+2 <= 5kn+2 \leqq 5 kn+2≦5kWe 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.
Whether l l llla natural number and calculate on [ α l α l alpha^(l)\alpha^{l}al], that is, the whole part of α l , α α l , α alpha l,alpha\alpha l, \alphaal,abeing the positive root of equation (6). It is easily proven, by complete induction, that
α l = u l − 1 α + u l − 2 α l = u l − 1 α + u l − 2 alpha^(l)=u_(l-1)alpha+u_(l-2)\alpha^{l}=u_{l-1} \alpha+u_{l-2}al=inl−1a+inl−2
from where
(9) [ α l ] = [ u l − 1 α ] + u l − 2 . (9) α l = u l − 1 α + u l − 2 . {:(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*}(9)[al]=[inl−1a]+inl−2.
We now have
LEM 2. - If α is the positive root of equation (6) and u n u n u_(n)u_{n}innterms of the series (3), we have
(10) [ u n α ] = u n + 1 − 1 − ( − 1 ) n 2 , n = 0 , 1 , … (10) u n α = u n + 1 − 1 − ( − 1 ) n 2 , n = 0 , 1 , … {:(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*}(10)[inna]=inn+1−1−(−1)n2,n=0,1,…
(6)
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , … … 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , … … 1,1,2,3,5,8,13,21,dots dots1,1,2,3,5,8,13,21, \ldots \ldots1,1,2,3,5,8,13,21,……
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)
u o = u 1 = 1 , u m = u m − 1 + u m − 2 , m i ′ = 2 , 3 , … u o = u 1 = 1 , u m = u m − 1 + u m − 2 , m i ′ = 2 , 3 , … 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, \ldotsinthe=in1=1,inm=inm−1+inm−2,mi′=2,3,…
Taking into account (4) and eliminating r , r 1 , … , r n − 1 r , r 1 , … , r n − 1 r,r_(1),dots,r_(n-1)r, r_{1}, \ldots, r_{n-1}r,r1,…,rn−1from inequalities (2), we deduce a ≧ u n + 2 i n a ≧ u n + 2 i n a >= u_(n+2)i_(n)a \geqq u_{n+2} i_{n}a≧inn+2inso
(5)
a ≧ u n + 2 . a ≧ u n + 2 . a >= u_(n+2).a \geqq u_{n+2} .a≧inn+2.
This inequality delimits the n n nnndepending on a a aaa.
We now have the following
LEMMA 1. - If a is the positive root of the equation ( α = 1 + 5 2 ) α = 1 + 5 2 (alpha=(1+sqrt5)/(2))\left(\alpha=\frac{1+\sqrt{5}}{2}\right)(a=1+52)
HAVE
x 2 − x − 1 = 0 x 2 − x − 1 = 0 x^(2)-x-1=0x^{2}-x-1=0x2−x−1=0
(7)
u m ≧ α m − 1 , m = 0 , 1 , … u m ≧ α m − 1 , m = 0 , 1 , … u_(m) >= alpha^(m-1),quad m=0,1,dotsu_{m} \geqq \alpha^{m-1}, \quad m=0,1, \ldotsinm≧am−1,m=0,1,…
The proof is easily done by complete induction, taking into account (4).
It is easy to verify that we have
(8)
α > 8 5 . α > 8 5 . alpha > (8)/(5).\alpha>\frac{8}{5} .a>85.
Taking into account equation (6) we deduce
and from (8) it follows that
α 5 = α 4 + α 3 = α 3 ( α + 1 ) = α ( α + 1 ) 2 = α ( 3 α + 2 ) = 5 α + 3 α 5 = α 4 + α 3 = α 3 ( α + 1 ) = α ( α + 1 ) 2 = α ( 3 α + 2 ) = 5 α + 3 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+3a5=a4+a3=a3(a+1)=a(a+1)2=a(3a+2)=5a+3
α 5 > 5 ⋅ 8 5 + 3 = 11 α 5 > 5 ⋅ 8 5 + 3 = 11 alpha^(5) > 5*(8)/(5)+3=11\alpha^{5}>5 \cdot \frac{8}{5}+3=11a5>5⋅85+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 number g g ggg, 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 a l l lllgiven the base of numeration that gives us the best limitation, according to the previous method, is precisely g g gggFor l = 5 l = 5 l=5l=5l=5is found g = 11 g = 11 g=11g=11g=11For the first 15 values ​​of l ( ≧ 2 ) l ( ≧ 2 ) l( >= 2)l(\geqq 2)l(≧2), the base g g gggthe most advantageous is given in the table
l l lll g g ggg l l lll g g ggg l l lll g g ggg
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
l g l g l g 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| $l$ | $g$ | $l$ | $g$ | $l$ | $g$ | | ---: | ---: | ---: | ---: | ---: | ---: | | 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

  1. IM Vinogradov, Osnovî teorii cisel, Moskva-Leningrad, 1949, pag. 22.
  2. 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 numbers a , b ( a < 1 ) a , b ( a < 1 ) a,b(a < 1)a, b(a<1)a,b(a<1), we note that in the classical expression in relation to the short a a aaa, 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 numbers a a aaa, b ( a < b ) b ( a < b ) b(a < b)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 1 ^(1){ }^{1}1) His division r n − 1 r n − 1 r_(n-1)r_{n-1}rn−1by r n r n r_(n)r_{n}rncan be avoided if its divisibility r n − 1 r n − 1 r_(n-1)r_{n-1}rn−1by r n r n r_(n)r_{n}rnis immediately recognized in another way. This always happens when = 1 = 1 =1=1=1.
1953

Related Posts