Кіріспе
Ең үлкен ортақ бөлгіштерді есептеу алгоритмі
Ең үлкен ортақ бөлгіш алгоритмі
an algorithm for the greatest common divisor
Математикада Евклид алгоритмі немесе Евклид алгоритмі – екі бүтін санның (сандардың) ең үлкен ортақ бөлгішін (ЕОБ) есептеудің тиімді әдісі, оларды қалдықсыз бөлетін ең үлкен сан. Ол ежегі грек математигі Евклидтің есімімен аталады, ол алғаш рет өзінің "Элементтер" еңбегінде (шамамен б.з.б. 300 ж.) сипаттаған. Бұл алгоритм – қадамдық процедура, белгілі бір ережелерге сәйкес есептеуді орындау үшін, және ол қазіргі кезде қолданылатын ең көне алгоритмдердің бірі. Оны бөлшектерді ең қарапайым түріне дейін қысқарту үшін де, көптеген басқа сандық теориялық және криптографиялық есептеулерде де пайдалануға болады. Евклид алгоритмі екі санның ең үлкен ортақ бөлгіші үлкен санның кіші саннан айырмасын алмастырғанда өзгермейді деген қағидаға негізделген. Мысалы, 252 мен 105 сандарының ЕОБ-сы 21-ге тең (өйткені 252 = 12 * 21 және 105 = 5 * 21), және 105 пен 15 сандарының ЕОБ-сы да 21-ге тең. Бұл алмастыру екі санның үлкенін кішірейтетіндіктен, осы процесті қайталау екі сан тең болатынша сандардың кішірек жұптарын береді. Осы кезде олар бастапқы екі санның ЕОБ-сы болады. Қадамдарды кері қайтару арқылы немесе кеңейтілген Евклид алгоритмін қолдану арқылы ЕОБ екі бастапқы санның сызықтық комбинациясы ретінде өрнектеле алады, яғни екі санның қосындысы ретінде, әрқайсысы бүтін санмен көбейтілген (мысалы, ). ЕОБ әрқашан осылай өрнектелуі мүмкін деген факт Безу теңдігі деп аталады. Жоғарыда сипатталған Евклид алгоритмінің нұсқасы – Евклидтің бастапқы баяндамасын ұстанатын – егер берілген сандардың бірі екіншісінен әлдеқайда үлкен болса, ЕОБ-ны табу үшін көптеген алу қадамдарын қажет етеді. Алгоритмнің тиімді нұсқасы осы қадамдарды қысқартады, үлкен санды кіші санға бөлгендегі қалдықпен алмастырады (осы нұсқада алгоритм қалдық нөлге жеткенде тоқталады). Бұл жақсарту арқасында алгоритмге кіші бүтін санның цифрларының санынан бес еседен артық қадамдар қажет емес. Бұл 1844 жылы Габриэль Ламе дәлелдеген (Ламе теоремасы), және ол есептеу күрделілігі теориясының бастауын білдіреді. Алгоритмнің тиімділігін арттырудың қосымша әдістері 20 ғасырда жасалды. Евклид алгоритмінің көптеген теориялық және практикалық қолданыстары бар. Ол бөлшектерді ең қарапайым түріне дейін қысқарту үшін және модульдік арифметикада бөлуді орындау үшін қолданылады. Бұл алгоритмді пайдаланатын есептеулер интернет байланысын қамтамасыз ету үшін қолданылатын криптографиялық протоколдардың бөлігін құрайды, сондай-ақ үлкен құрамдас сандарды есепке алу арқылы осы криптожүйелерді бұзу әдістерінде қолданылады. Евклид алгоритмі Диофанти теңдеулерін шешу үшін, мысалы, қытайлық қалдық теоремасы бойынша бірнеше конгруэнцияларды қанағаттандыратын сандарды табу, үздіксіз бөлшектерді құру және нақты сандарға дәл рационалды шамалауларды табу үшін пайдаланылуы мүмкін. Сонымен қатар, оны Лагранждың төрт квадрат теоремасы және жай санның бірегейлігі сияқты сандар теориясындағы теоремаларды дәлелдеудің негізгі құралы ретінде қолдануға болады. Алғашқы алгоритм тек табиғи сандар мен геометриялық ұзындықтар (нақты сандар) үшін сипатталды, бірақ 19 ғасырда алгоритм басқа сандарға, мысалы, Гаусс бүтін сандарына және бір айнымалының полиномдарына жалпыландырылды. Бұл Евклид домендері сияқты қазіргі абстрактіл алгебралық түсініктерге әкелді.
and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as and , and the same number 21 is also the GCD of 105 and Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, ). The fact that the GCD can always be expressed in this way is known as Bézout's identity. The version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century. The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four square theorem and the uniqueness of prime factorizations. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains.
Негізгі мәлімет: ең үлкен ортақ бөлгіш
Евклид алгоритмі a және b екі табиғи санның ең үлкен ортақ бөлгішін (GCD) есептейді. Ең үлкен ортақ бөлгіш g – a мен b-ді қалдықсыз бөлетін ең үлкен табиғи сан. GCD-нің синонимдері ең үлкен ортақ фактор (GCF), ең жоғары ортақ фактор (HCF), ең жоғары ортақ бөлгіш (HCD) және ең үлкен ортақ өлшем (GCM) болып табылады. Ең үлкен ортақ бөлгіш көбінесе gcd(a, b) немесе, қарапайым түрде, (a, b) деп жазылады, бірақ соңғы белгілер екіұшты, сонымен қатар GCD-ге жақын бүтін сандар сақинасындағы идеал сияқты ұғымдар үшін де қолданылады. Егер gcd(a, b) = 1 болса, онда a және b өзара жай (немесе салыстырмалы түрде жай) деп аталады. Бұл қасиет a немесе b жай сан екенін білдірмейді. Мысалы, 6 және 35 сандары 6 = 2 × 3 және 35 = 5 × 7 болып жіктеледі, сондықтан олар жай емес, бірақ олардың жай көбейткіштері әртүрлі, сондықтан 6 және 35 өзара жай, олардың 1-ден басқа ортақ көбейткіштері жоқ. a және b екеуі де g-ға еселі болғандықтан, оларды a = mg және b = ng түрінде жазуға болады, және бұл шындыққа сай келетін G > g үлкен саны жоқ. m және n натуралды сандары өзара жай болуы керек, өйткені кез келген ортақ көбейткішті m және n-ден шығаруға болады, сонда g үлкенірек болады. Осылайша, a мен b-ді де бөлетін кез келген басқа c саны g-ді де бөлуі керек. a және b-нің ең үлкен ортақ бөлгіші g – бұл a және b-нің кез келген басқа ортақ бөлгіші c-ге бөлінетін бірегей (оң) ортақ бөлгіші. Ең үлкен ортақ бөлгішті келесідей бейнелеуге болады. a × b тіктөртбұрышты ауданын және a мен b-ді дәл бөліп тұратын кез келген ортақ бөлгіш c-ді қарастырайық. Тіктөртбұрыштың қабырғаларын ұзындығы c сегменттеріне бөлуге болады, бұл тіктөртбұрышты қабырға ұзындығы c квадраттардың торларына бөледі. GCD g – бұл c-нің ең үлкен мәні, ол үшін бұл мүмкін. Мысалы, 24×60 тіктөртбұрышты аумақты: 1×1 квадраттар, 2×2 квадраттар, 3×3 квадраттар, 4×4 квадраттар, 6×6 квадраттар немесе 12×12 квадраттар торшасына бөлуге болады. Сондықтан 12 – 24 пен 60-тың GCD-сі. 24×60 тіктөртбұрышты аумақты 12×12 квадраттан тұратын торға бөлуге болады, оның бір шетінде екі квадрат, екінші шетінде бес квадрат болады. Екі санның a және b ең үлкен ортақ бөлгіші – бұл екі санның ортақ жай факторларының көбейтіндісі, мұнда әрбір жай фактор a және b екеуін де бөліп жатқандай рет қайталануы мүмкін. Мысалы, 1386 саны 2 × 3 × 3 × 7 × 11-ге, ал 3213 саны 3 × 3 × 3 × 7 × 17-ге бөлінуі мүмкін болғандықтан, 1386 және 3213-тің GCD тең 3 × 3 × 7 = 63, олардың ортақ жай факторларының көбейтіндісі (3-і қайталанатын, өйткені 3 × 3-і екеуін де бөледі). Егер екі санның ортақ жай көбейткіштері болмаса, олардың GCD - 1 (мұнда бос көбейтіндіге мысал ретінде алынған); басқаша айтқанда, олар өзара жай болып табылады. Евклид алгоритмінің басты артықшылығы – ол GCD-ді жай факторларды есептеусіз тиімді таба алады. Үлкен бүтін сандарды жай факторларға жіктеу есептеу жағынан өте қиын мәселе деп саналады, ал көптеген кеңінен қолданылатын криптографиялық протоколдардың қауіпсіздігі оның жүзеге аспауына негізделген. GCD-нің тағы бір анықтамасы жоғары математикада, әсіресе сақиналар теориясында пайдалы, бірақ оны сандар жұптарының GCD-ін қайталап алу арқылы да есептеуге болады. Мысалы, gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b). Осылайша, екі бүтін санның GCD-ін есептейтін Евклид алгоритмі кездейсоқ көптеген бүтін сандардың GCD-ін есептеу үшін жеткілікті.
The greatest common divisor can be visualized as follows. Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly. The sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 4×4 squares, 6×6 squares or 12×12 squares. Therefore, 12 is the GCD of 24 and 60. A 24×60 rectangular area can be divided into a grid of 12×12 squares, with two squares along one edge and five squares along the other
The greatest common divisor of two numbers a and b is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both a and b. For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals , the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility. Another definition of the GCD is helpful in advanced mathematics, particularly ring theory. but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example,
1=gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b). Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.
Процедура
Евклид алгоритмін екі берілген бүтін саннан басталатын теріс емес бүтін сандар тізбегін құрастыру деп қарастыруға болады, ол тізбек ақыр соңында нөл бүтін санымен аяқталады: , мұндағы бүтін сан – ЕББ (GCD) болады және мынаны айтуға болады. Алгоритм алдыңғы жұп сандарды қалдықпен бөлу арқылы аралық қалдықтарды қалай құрастыру керектігін көрсетеді, осы арқылы бүтін сандардың үлесін тауып, тізбектің қатаң түрде кемуін қамтамасыз етеді. Яғни, әрбір және әрбір алдыңғысынан қатаң түрде кіші бүтін сан болғандықтан, нөлден кіші теріс емес бүтін сан ақырында табылмайды, сондықтан алгоритм міндетті түрде аяқталуы керек. Алгоритм әрқашан n-ші қадамда 0-ге тең болатын қалдықпен аяқталады. Мысалы, 1071 және 462 сандарының ЕББ-ін табу керек делік. Тізбек бастапқыда келесідей болады: , және үшін қалдық табу үшін бізге мынадай бүтін сандар және табу қажет:
Because the sequence of non negative integers is strictly decreasing, it eventually must terminate. In other words, since for every , and each is an integer that is strictly smaller than the preceding , there eventually cannot be a non negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n th step with equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find , we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If , the algorithm may continue and trivially find that as the sequence of remainders will be If , then we can also continue since , suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for , and that the sub sequence of non negative integers for is strictly decreasing, therefore excluding from both statements.
Бұл – үлес, себебі. Бұл анықталғаннан кейін тізбек келесідей болады: Келесі қадамда қалдық табу үшін бізге мынадай бүтін сандар және табу қажет:
Because the sequence of non negative integers is strictly decreasing, it eventually must terminate. In other words, since for every , and each is an integer that is strictly smaller than the preceding , there eventually cannot be a non negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n th step with equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find , we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If , the algorithm may continue and trivially find that as the sequence of remainders will be If , then we can also continue since , suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for , and that the sub sequence of non negative integers for is strictly decreasing, therefore excluding from both statements.
Бұл – үлес, себебі. Бұл анықталғаннан кейін тізбек келесідей болады: Келесі қадамда қалдық табу үшін бізге мынадай бүтін сандар және табу қажет:
Because the sequence of non negative integers is strictly decreasing, it eventually must terminate. In other words, since for every , and each is an integer that is strictly smaller than the preceding , there eventually cannot be a non negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n th step with equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find , we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If , the algorithm may continue and trivially find that as the sequence of remainders will be If , then we can also continue since , suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for , and that the sub sequence of non negative integers for is strictly decreasing, therefore excluding from both statements.
Бұл – үлес, себебі. Бұл анықталғаннан кейін тізбек келесідей толықтырылады: , өйткені одан кіші теріс емес бүтін сан табу мүмкін емес. Сондықтан, сұралған ЕББ – соңғы қалдық:
Because the sequence of non negative integers is strictly decreasing, it eventually must terminate. In other words, since for every , and each is an integer that is strictly smaller than the preceding , there eventually cannot be a non negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n th step with equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find , we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If , the algorithm may continue and trivially find that as the sequence of remainders will be If , then we can also continue since , suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for , and that the sub sequence of non negative integers for is strictly decreasing, therefore excluding from both statements.
Біз бастапқы екі мәннің ретіне қатысты талапты алып тастап, сәл жалпылауға болады. Егер , онда алгоритм жалғасуы мүмкін және тізбек қалдықтары ретінде жалғасады. Егер , онда да жалғасуға болады, себебі , яғни келесі қалдық өзі болуы керек, ал тізбек қалыпты жағдайда бұрынғы талапты бұзуы мүмкін еді, бірақ қазір құрылымдық түрде орындалады, сондықтан талап автоматты түрде қанағаттандырылады және Евклид алгоритмі қалыпты түрде жалғаса алады. Демек, алғашқы екі бүтін санның арасындағы реттің жойылуы тізбектің міндетті түрде аяқталуы керек деген тұжырымға әсер етпейді, өйткені келесі қалдық әрқашан орындалады және жоғарыда айтылғандарға сәйкес жалғасады. Тек қана үшін ғана өзгеріс қажет, және теріс емес бүтін сандар тізбегі қатаң түрде кемуі керек, сондықтан екі жағдайда да осы сандарды ескермеу керек.
Because the sequence of non negative integers is strictly decreasing, it eventually must terminate. In other words, since for every , and each is an integer that is strictly smaller than the preceding , there eventually cannot be a non negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the n th step with equal to zero. To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially and in order to find , we need to find integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is now The next step is to continue the sequence to find by finding integers and such that:
This is the quotient since This determines and so the sequence is completed as as no further non negative integer smaller than can be found. The penultimate remainder is therefore the requested GCD:
We can generalize slightly by dropping any ordering requirement on the initial two values and If , the algorithm may continue and trivially find that as the sequence of remainders will be If , then we can also continue since , suggesting the next remainder should be itself, and the sequence is Normally, this would be invalid because it breaks the requirement but now we have by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy and everything continues as above. The only modifications that need to be made are that only for , and that the sub sequence of non negative integers for is strictly decreasing, therefore excluding from both statements.
Көрнекілендіру
Евклид алгоритмін жоғарыда келтірілген ең үлкен ортақ бөлгіштің мозаикалық аналогиясы арқылы түсіндіруге болады. Екі санның үлкені a болса, a×b тіктөртбұрышын дәл шаршы плиткалармен жабуды көздесек. Алдымен b×b шаршы плиткалармен жабуға тырысамыз; бірақ бұл r0×b қалдық тіктөртбұрышын жабылмаған қалдырады, мұнда r0 < b. Содан кейін қалған тіктөртбұрышты r0×r0 шаршы плиткалармен жабуға тырысамыз. Бұл r1×r0 екінші қалдық тіктөртбұрышын қалдырады, оны r1×r1 шаршы плиткалармен және т.с.с. жабуға тырысамыз. Қалдық тіктөртбұрыш болмағанда тізбе аяқталады, яғни шаршы плиткалар алдыңғы қалдық тіктөртбұрышты толық жабады. Ең кішкентай шаршы плитка қабырғасының ұзындығы бастапқы тіктөртбұрыштың өлшемдерінің ЕОБ-і (GCD) болып табылады. Мысалы, жанындағы суреттегі ең кішкентай шаршы плитка 21×21 (қызыл түспен көрсетілген), ал 21 – 1071 және 462 сандарының ЕОБ-і (GCD), бастапқы тіктөртбұрыштың өлшемдері (жасыл түспен көрсетілген).
Тарихи дамуы
Евклид алгоритмі – жалпы қолданыстағы ең көне алгоритмдердің бірі. Ол Евклидтің «Элементтер» еңбегінде (б.з.д. шамамен 300 ж.) кездеседі, атап айтқанда 7-кітапта (1–2-шаруалар) және 10-кітапта (2–3-шаруалар). 7-кітапта алгоритм бүтін сандар үшін, ал 10-кітапта сызық сегменттерінің ұзындықтары үшін жасалған. (Қазіргі қолданыста оны нақты сандар үшін жасалған деп айтуға болады. Бірақ ұзындық, аудан және көлем, қазіргі заманғы нақты сандар ретінде көрсетілгенде, бірдей бірліктермен өлшенбейді және ұзындық, аудан немесе көлем үшін табиғи бірлік жоқ; нақты сандар туралы түсінік сол кезде белгісіз болды.) Соңғы алгоритм геометриялық. Екі ұзындықтың ең үлкен ортақ бөлгіші (ЕҮОБ) a және b, a және b екеуін де қалдықсыз бөлетін ең үлкен ұзындық g-ге сәйкес келеді; яғни, a және b ұзындықтары g ұзындығының еселігі болып табылады. Алгоритмді Евклид өзі ашпаған болуы мүмкін, өйткені ол «Элементтер» еңбегінде одан бұрынғы математиктердің нәтижелерін жинақтаған. Математик және тарихшы Б. Л. ван дер Вэрден 7-кітаптың Пифагор мектебінің математиктері жазған сандар теориясы бойынша оқулықтан алынғанын болжайды. Алгоритмді, мүмкін, Евдокс Книдский (шамамен б.з.д. 375 ж.) білген. Алгоритм тіпті Евдоксқа дейін де пайда болған болуы мүмкін, Эвклид пен Аристотельдің еңбектеріндегі ἀνθυφαίρεσις (антифирезис, өзара алу) терминінің қолданылуына қарағанда. Ғасырлар өткен соң, Евклид алгоритмі Үндістанда да, Қытайда да тәуелсіз түрде ашылды, негізінен астрономияда туындаған Диофанти теңдеулерін шешу және дәл күнтізбе жасау үшін. 5-ғасырдың соңында үнді математигі және астрономы Арьябхата алгоритмді «ұнтақтағыш» деп сипаттады, мүмкін оның Диофанти теңдеулерін шешудегі тиімділігіне байланысты. Қытайлық қалдық теоремасының ерекше жағдайы «Суньцзы Суаньцзин» кітабында сипатталған болса да, жалпы шешімін Цинь Цзюшао 1247 жылғы «Шушу Цзючжан» кітабында жариялады (數書九章 Mathematical Treatise in Nine Sections). Евклид алгоритмі алғаш рет сандық түрде сипатталды және 1624 жылы жарық көрген Bachet's Problèmes plaisants et délectables (Қызықты және әдемі мәселелер) еңбегінің екінші басылымында Еуропада танымал болды. Ол оны Роджер Коутспен үздіксіз бөлшектерді тиімді есептеу әдісі ретінде байланыстырды. 19-ғасырда Евклид алгоритмі Гаусс бүтін сандары және Эйзенштейн бүтін сандары сияқты жаңа сандар жүйелерін жасауға әкелді. 1815 жылы Карл Гаусс Евклид алгоритмін Гаусс бүтін сандарының бірегей факторлануын көрсету үшін қолданды, бірақ оның жұмысы алғаш рет 1832 жылы жарияланды. Лежун Дирихлет сандар теориясының көптеген нәтижелері, мысалы, бірегей факторлау, Евклид алгоритмін қолдануға болатын кез келген сандар жүйесі үшін дұрыс болатынын атап өтті. Лежун Дирихлеттің сандар теориясы бойынша дәрістерін Рихард Дедекинд өңдеп, кеңейтті, ол Евклид алгоритмін алгебралық бүтін сандарды, сандардың жаңа жалпы түрін зерттеу үшін қолданды. Мысалы, Дедекинд Гаусс бүтін сандарының бірегей факторлануын пайдалана отырып, Ферманың екі квадрат теоремасын алғаш рет дәлелдеді. Дедекинд сонымен қатар Евклид домені деген ұғымды анықтады, яғни Евклид алгоритмінің жалпыланған нұсқасын анықтауға болатын сандық жүйе (төменде сипатталғандай). 19-ғасырдың соңғы онжылдықтарында Евклид алгоритмі Дедекиндтің идеалдардың жалпы теориясымен біртіндеп көлеңкеленді. "[Евклид алгоритмі] барлық алгоритмдердің атасы, өйткені ол бүгінгі күнге дейін сақталған ең көне тривиальды емес алгоритм". Дональд Кнут, Компьютерлік бағдарламалау өнері, 2-том: Seminumerical Algorithms, 2-басылым (1981), 318-бет. Евклид алгоритмінің басқа қолданбалары 19-ғасырда жасалды. 1829 жылы Чарльз Штурм алгоритмнің Штурм тізбегі әдісінде кез келген берілген аралықтағы көпмүшелердің нақты түбірлерін санау үшін пайдалы екенін көрсетті. Евклид алгоритмі – бірінші бүтін сандық қатынас алгоритмі, ол тең дәрежедегі нақты сандар арасындағы бүтін сандық қатынастарды табу әдісі. Бірнеше жаңа бүтін сандық қатынас алгоритмі жасалды, мысалы, Хеламан Фергюсон мен Р. В. Форкадтың (1979) алгоритмі және LLL алгоритмі. 1969 жылы Коул мен Дэви Евклид алгоритміне негізделген екі ойыншы ойынын жасады, оны «Евклид ойыны» деп атады, оның оңтайлы стратегиясы бар. Ойыншылар екі үйірменді a және b таспен бастайды. Ойыншылар үлкен үйірден кіші үйірдің m еселенгенін алып тастауға кезегімен өтеді. Осылайша, егер екі үйір x және y тастардан тұрса, онда x, y-ден үлкен болса, келесі ойыншы үлкен үйірді x тастардан x - my тастарға дейін азайта алады, егер соңғысы теріс емес бүтін сан болса. Бір үйірден нөлге дейін тастарды азайтатын бірінші ойыншы жеңімпаз болады.
The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (about 375 BC). The algorithm may even pre date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle. Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). who attributed it to Roger Cotes as a method for computing continued fractions efficiently. In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals. "[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day." Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318. Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval. The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed, such as the algorithm of Helaman Ferguson and R. W. Forcade (1979) and the LLL algorithm. In 1969, Cole and Davie developed a two player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy. The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.
Негізгі идеалдар мен оларға байланысты проблемалар
Безо сәйкестігі екі санның – a және b – ең үлкен ортақ бөлгіші g-нің тағы бір анықтамасын береді. U және v кез келген екі бүтін сан болғанда, ua + vb түріндегі барлық сандар жиынтығын қарастырайық. a және b екеуі де g-ға бөлінетіндіктен, жиынтықтағы әрбір сан g-ға бөлінеді. Басқаша айтқанда, жиынтықтағы әрбір сан g-нің бүтін сан еселігі болып табылады. Бұл a және b-нің кез келген ортақ бөлгіші үшін де дұрыс. Дегенмен, басқа ортақ бөлгіштерден айырмашылығы, ең үлкен ортақ бөлгіш осы жиынның мүшесі болады; Безо сәйкестігі бойынша, u = s және v = t деп таңдасақ, нәтижесінде g шығады. Кішірек ортақ бөлгіш жиынның мүшесі бола алмайды, себебі жиынның әрбір мүшесі g-ға бөлінуі керек. Керісінше, g-ның кез келген еселігі m-ді u = ms және v = mt деп таңдау арқылы алуға болады, мұнда s және t – Безо сәйкестігіндегі бүтін сандар. Бұл Безо сәйкестігін m-ге көбейту арқылы көруге болады: 1 = mg = msa + mtb. Демек, ua + vb түріндегі барлық сандар жиыны g-ның m еселіктері жиынымен тең. Басқаша айтқанда, екі санның (a және b) бүтін сан еселіктерінің барлық мүмкін қосындылары жиыны gcd(a, b) еселіктері жиынымен тең. Ең үлкен ортақ бөлгіш (GCD) a және b идеалдарының генераторы деп аталады. Осы GCD анықтамасы қазіргі абстрактілі алгебрада басты идеал (бір элементпен құрылған идеал) және басты идеалдық домен (әр идеал басты идеал болатын домен) деген ұғымдарға әкелді. Осы нәтижені пайдаланып белгілі бір мәселелерді шешуге болады. Мысалы, көлемі a және b болатын екі өлшеуіш тостағанды қарастырайық. Бірінші тостағаннан u еселік мөлшерін және екінші тостағаннан v еселік мөлшерін қосу/азайту арқылы ua + vb көлемін өлшеуге болады. Бұл көлемдердің барлығы g = gcd(a, b) еселіктері болады.
1=mg = msa + mtb. Therefore, the set of all numbers ua + vb is equivalent to the set of multiples m of g. In other words, the set of all possible sums of integer multiples of two numbers (a and b) is equivalent to the set of multiples of gcd(a, b). The GCD is said to be the generator of the ideal of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain in which every ideal is a principal ideal). Certain problems can be solved using this result. For example, consider two measuring cups of volume a and b. By adding/subtracting u multiples of the first cup and v multiples of the second cup, any volume ua + vb can be measured out. These volumes are all multiples of g = gcd(a, b).
Көбейту инверстері және RSA алгоритмі
Шекті өріс – төрт жалпыланған операциясы бар сандар жиынтығы. Операциялар қосу, алу, көбейту және бөлу деп аталады және олардың қалыпты қасиеттері бар, мысалы, коммутативтілік, ассоциативтілік және дистрибутивтілік. Шекті өріс мысалы – модульдік арифметика қолданылатын {0, 1, 2, …, 12} жиынтығынан тұратын 13 сан. Бұл өрісте кез келген математикалық операцияның (қосу, алу, көбейту немесе бөлу) нәтижесі 13 модулі бойынша қысқартылады; яғни, 13-ке еселенген сандар 0–12 диапазонына дейін жеткізіледі. Мысалы, 5 × 7 = 35 mod 13 = 9. Мұндай шекті өрістер кез келген жай сан p үшін анықталуы мүмкін; ал күрделірек анықтамалар қолданылса, жай сан p-нің кез келген m дәрежесі үшін де анықталуы мүмкін. Шекті өрістер көбінесе Галуа өрістері деп аталады және GF(p) немесе GF(p^m) деп белгіленеді. Мұндай m саннан тұратын өрісте, әрбір нөлдік емес элементтің a бірегей модульдік көбейтуге кері шамасы a⁻¹ болады, мұнда 1 = aa⁻¹ = a⁻¹a ≡ 1 (mod m). Бұл кері шама ax ≡ 1 (mod m) конгруенциялық теңдеуін немесе эквивалентті сызықтық Диофант теңдеуін шешу арқылы табылады: 1 = ax + my = 1. Бұл теңдеуді жоғарыда сипатталғандай Евклид алгоритмімен шешуге болады. Көбейтуге кері шаманы табу – RSA алгоритмінің маңызды қадамы, ол электрондық коммерцияда кеңінен қолданылады; атап айтқанда, бұл теңдеу хабарды шифрлауға қолданылатын бүтін санды анықтайды. RSA алгоритмі өрістердің орнына сақиналарды қолданса да, Евклид алгоритмін кері шама бар болған жағдайда табу үшін пайдалануға болады. Евклид алгоритмінің қателерді түзету кодтарында да басқа қолданыстары бар; мысалы, оны Галуа өрістеріне негізделген BCH және Reed-Solomon кодтарын кодтау үшін Berlekamp-Massey алгоритміне балама ретінде қолдануға болады.
1=ax + my = 1. This equation can be solved by the Euclidean algorithm, as described above. Finding multiplicative inverses is an essential step in the RSA algorithm, which is widely used in electronic commerce; specifically, the equation determines the integer used to decrypt the message. Although the RSA algorithm uses rings rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in error correcting codes; for example, it can be used as an alternative to the Berlekamp–Massey algorithm for decoding BCH and Reed–Solomon codes, which are based on Galois fields.
Факторлау алгоритмдері
Ең үлкен ортақ бөлгішті есептеу, Поллардтың ро алгоритмі, Шор алгоритмі, Диксонның факторлау әдісі және Ленстра эллиптік қисық факторлау сияқты бірнеше бүтін сандарды факторлау алгоритмдеріндегі қажетті қадам болып табылады. Осы ЕҮО-ны тиімді табу үшін Евклид алгоритмін қолдануға болады. Жалғастырылған бөлшектерді факторлауда Евклид алгоритмі арқылы анықталатын жалғастырылған бөлшектер пайдаланылады.
Баламалы әдістер
Евклид алгоритмі өзінің қарапайымдылығына байланысты тәжірибеде, әсіресе кіші сандар үшін кеңінен қолданылады. Салыстыру үшін Евклид алгоритміне баламалардың тиімділігін анықтау мүмкін. Екі табиғи сан a және b-нің ең үлкен ортақ бөлгішін табудың бір тиімсіз тәсілі – олардың барлық ортақ бөлгіштерін есептеу; ең үлкен ортақ бөлгіш – бұл ең үлкен ортақ бөлгіш. Ортақ бөлгіштерді екі санды да 2-ден бастап кішірек сан b-ге дейінгі тізбектелген бүтін сандарға бөлу арқылы табуға болады. Бұл әдістің қадамдарының саны b-мен сызықтық түрде немесе цифрлар санымен экспоненциалды түрде өседі. Тағы бір тиімсіз тәсіл – бір немесе екі санның алғашқы көбейткіштерін табу. Жоғарыда айтылғандай, ең үлкен ортақ бөлгіш екі сан a және b-нің ортақ алғашқы көбейткіштерінің көбейтіндісіне тең. Алайда, бұл балама да O(h²) сияқты масштабталады. Ол, әдетте, Эвклид алгоритмінен жылдам, тіпті ол бірдей масштабта болса да. Қосымша тиімділікті тек a және b сандарының бастапқы цифрларын қарастыру арқылы алуға болады. Бинарлық алгоритмді басқа негіздерге (k-дық алгоритмдер) жылдамдықты бес есеге дейін арттыра отырып, кеңейтуге болады. Лемердің ең үлкен ортақ бөлгіш алгоритмі екілік алгоритммен бірдей жалпы принципті пайдаланып, ең үлкен ортақ бөлгіш есептеулерін кез келген негізде жылдамдатады. Өте үлкен бүтін сандарға (25 000-нан астам цифрлы) рекурсивті тәсіл Шенхаге, Штеле және Циммерманн сияқты квазилинейлік бүтін сандар ең үлкен ортақ бөлгіш алгоритмдеріне әкеледі. Бұл алгоритмдер жоғарыда келтірілген Евклид алгоритмінің 2×2 матрицалық түрін пайдаланады. Бұл квазилинейлік әдістер жалпы алғанда…