Ең үлкен ортақ бөлгіш

Кіріспе

Берілген бүтін сандарды бөлетін ең үлкен бүтін сан. Математикада екі немесе одан көп нөл емес бүтін санның ең үлкен ортақ бөлгіші (GCD) – бұл бүтін сандардың әрқайсысын бөлетін ең үлкен оң бүтін сан. Екі бүтін сан x және y үшін, x пен y-тің ең үлкен ортақ бөлгіші осылай белгіленеді. Мысалы, 8 және 12 сандарының GCD-сі 4-ке тең, яғни gcd(8, 12) = 4. "Ең үлкен ортақ бөлгіш" атауында "ең үлкен" деген сөзін "ең жоғары" деп алмастыруға болады, ал "бөлгіш" сөзін "фактор" деп алмастыруға болады, сондықтан басқа атаулардың ішінде ең үлкен ортақ фактор да бар. Тарихи тұрғыдан алғанда, осы ұғымды білдіретін басқа атаулар да болған, мысалы, ең үлкен ортақ өлшем. Бұл ұғым көпмүшелерге (көпмүшелердің ең үлкен ортақ бөлгішіне қараңыз) және басқа коммутативтік сақиналарға да қолданылады (төменде қараңыз).

Анықтама

Екі бүтін санның a және b ең үлкен ортақ бөлгіші (ЕОБ), олардың кем дегенде біреуі нөлден өзгеше болса, – a және b екеуінің де бөлгіші болатын ең үлкен оң бүтін сан d; яғни, e және f бүтін сандары бар, онда a = de және b = df, және d – мұндай ең үлкен сан. a және b-нің ЕОБ-і әдетте gcd(a, b) деп белгіленеді. Кейбір авторлар (a, b) белгісін де қолданады, бұл конвенция көптеген компьютерлік алгебра жүйелерінде қолданылады. Дегенмен, кейбір авторлар gcd(0, 0) анықталмаған деп қалдырады. a және b-нің ЕОБ-і – бөлгіштік алдын ала реттік қатынасындағы олардың ең үлкен оң ортақ бөлгіші. Бұл a және b-нің ортақ бөлгіштері олардың ЕОБ-інің ғана бөлгіштері болады дегенді білдіреді. Бұл көбінесе Евклид леммасын, арифметиканың негізгі теоремасын немесе Евклид алгоритмін қолдану арқылы дәлелденеді. Осы мағынада "ең үлкен" сөзі ЕОБ түсінігінің жалпылаулары үшін қолданылады.

Копрималық сандар

Екі санның ең үлкен ортақ бөлгіші 1-ге тең болса, олар өзара жай немесе тең жай сандар деп аталады. Мысалы, 9 және 28 өзара жай сандар.

Геометриялық көрініс

Мысалы, 24х60 тіктөртбұрышты аумақты мынадай торларға бөлуге болады: 1х1 квадраттар, 2х2 квадраттар, 3х3 квадраттар, 4х4 квадраттар, 6х6 квадраттар немесе 12х12 квадраттар. Сондықтан 12 – 24 пен 60 сандарының ең үлкен ортақ бөлгіші. Осылайша, 24х60 тіктөртбұрышты аумақты 12х12 квадраттардан тұратын торға бөлуге болады, бір қабырғасы бойынша екі квадрат (24/12 = 2) және екінші қабырғасы бойынша бес квадрат (60/12 = 5) болады.

Кішірейтуші бөлшектер

Ең үлкен ортақ бөлгіш бөлшектерді ең қарапайым түріне келтіруге көмектеседі. Мысалы, ЕҮОБ(42, 56) = 14, сондықтан

Лемердің GCD алгоритмі

Лемер алгоритмі Евклид алгоритмімен алынған бастапқы бөлінділерді тек алғашқы бірнеше цифрлар негізінде анықтауға болатындығына негізделген; бұл компьютерлік сөзден үлкен сандар үшін пайдалы. Негізінде, бастапқы цифрлар ізделіп алынып, әдетте бір немесе екі компьютерлік сөзді құрайды, содан кейін Евклид алгоритмі осы кішірек сандарға қолданылады, егер бұл бөлінділер бастапқы сандар үшін алынған бөлінділермен сәйкес келетініне кепілдік берілсе. Бөлінділер бастапқы сандарды қысқарту үшін кішкентай 2x2 түрлендіру матрицасына (бір сөздік бүтін сандар матрицасы) жиналады. Бұл процесс сандар бинарлық алгоритм (төменде қараңыз) тиімдірек болатынша қайталанады. Бұл алгоритм жылдамдықты арттырады, себебі ол өте үлкен сандармен операциялардың санын азайтады және көптеген операциялар үшін аппараттық арифметиканы пайдалануға мүмкіндік береді. Шындығында, көптеген бөлінділер өте кішкентай болады, сондықтан Евклид алгоритмінің көптеген қадамдарын бір сөздік бүтін сандардың 2x2 матрицасында жинақтауға болады. Лемер алгоритмі тым үлкен бөліндіге тап болғанда, ол үлкен сандарды Евклидтік бөлу арқылы Евклид алгоритмінің бір итерациясына қайта оралуы керек.

Күрделілігі

Ең үлкен ортақ бөлгіштерді есептеудің есептеу күрделілігі кеңінен зерттелді. Егер Евклид алгоритмі және көбейту мен бөлуге арналған элементар алгоритмдер қолданылса, ең көп дегенде n битті екі бүтін санның ең үлкен ортақ бөлгішін есептеу O(n²). Бұл ең үлкен ортақ бөлгішті есептеудің, тұрақты факторға дейін, көбейтумен бірдей күрделілікке ие екенін білдіреді. Дегенмен, егер жылдам көбейту алгоритмі қолданылса, күрделілікті жақсарту үшін Евклид алгоритмін өзгертуге болады, бірақ ең үлкен ортақ бөлгішті есептеу көбейтуден баяу болады. Нақтырақ айтқанда, егер n биттік екі бүтін санды көбейту T(n) уақытын алса, онда ең үлкен ортақ бөлгіштің ең жылдам белгілі алгоритмі O(T(n) log n) күрделілігіне ие. Бұл ең жылдам белгілі алгоритмнің күрделілігі O(n (log n)²) екенін білдіреді. Бұрынғы күрделіктер есептеудің стандартты модельдері үшін жарамды, атап айтқанда, көп таспалы Тьюринг машиналары және кездейсоқ кіру машиналары. Сондықтан, ең үлкен ортақ бөлгіштерді есептеу квазисызықтық уақытта шешілетін проблемалар класына жатады. Сәйкес шешім проблемасы, тиісінше, полиномиалдық уақытта шешілетін проблемалардың P класына жатады. GCD проблемасының NC класында екені белгісіз, сондықтан оны тиімді түрде параллельдеудің белгілі жолы жоқ; сондай-ақ, ол P-толық екені белгісіз, бұл GCD есептеуін тиімді түрде параллельдеудің мүмкін еместігін білдіретін болар еді. Шалкросс және басқалар, байланысты проблеманың (Евклид алгоритмі кезінде туындайтын қалдық тізбегін анықтау – EUGCD) екі айнымалысы бар бүтін сандардың сызықтық бағдарламалау мәселесімен NC эквивалентті екенін көрсетті; егер кез келген мәселе NC класында немесе P-толық болса, екіншісі де солай болады. NC класы NL класын қамтитындықтан, GCD-ні есептеу үшін кеңістікке тиімді алгоритмнің бар-жоқтығы да белгісіз, тіпті детерминистік емес Тьюринг машиналары үшін де. Мәселе NC класында екені белгісіз болғанымен, Евклид алгоритмінен асимптотикалық жағынан жылдам параллель алгоритмдер бар; ең жылдам белгілі детерминистік алгоритм – Чор мен Голдрейхтің алгоритмі, ол (CRCW PRAM моделінде) мәселені O(n/log n) уақытында n^(1+ε) процессорлармен шеше алады. Рандомизацияланған алгоритмдер процессорларда O((log n)²) уақытында мәселені шеше алады (бұл суперполиномиалды).

The computational complexity of the computation of greatest common divisors has been widely studied. If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most n bits is O(n^(2)). This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication. However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication. More precisely, if the multiplication of two integers of n bits takes a time of T(n), then the fastest known algorithm for greatest common divisor has a complexity O(T(n) log n). This implies that the fastest known algorithm has a complexity of O(n (log n)^(2)). Previous complexities are valid for the usual models of computation, specifically multitape Turing machines and random access machines. The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time. A fortiori, the corresponding decision problem belongs to the class P of problems solvable in polynomial time. The GCD problem is not known to be in NC, and so there is no known way to parallelize it efficiently; nor is it known to be P complete, which would imply that it is unlikely to be possible to efficiently parallelize GCD computation. Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC equivalent to the problem of integer linear programming with two variables; if either problem is in NC or is P complete, the other is as well. Since NC contains NL, it is also unknown whether a space efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines. Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist; the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW PRAM model) can solve the problem in O(n/log n) time with n^(1+ε) processors. Randomized algorithms can solve the problem in O((log n)^(2)) time on processors (this is superpolynomial).

Ықтималдықтар мен күтілетін құн

1972 жылы Джеймс Э. Ниманн k бүтін санды, тәуелсіз және біркелкі таңдап алғанда, n шексізге жақындағанда, олардың өзара жай болу ықтималдығы 1/ζ(k) тең екенін көрсетті, мұнда ζ – Риманның зетта функциясын білдіреді. (Дәлелдеме үшін өзара жай сандарға қараңыз.) Бұл нәтиже 1987 жылы k кездейсоқ санның ең үлкен ортақ бөлгіші d-ге тең болу ықтималдығы d^(−k)/ζ(k) екенін көрсету үшін кеңейтілді. Осы ақпаратты пайдаланып, ең үлкен ортақ бөлгіш функциясының күтілетін мәні 1=k=2 болғанда (бейресми түрде) жоқ екенін көруге болады. Бұл жағдайда GCD d-ге тең болу ықтималдығы d^(−2)/ζ(2) тең, ал 1=ζ(2) = π^(2)/6 болғандықтан, бізде:

Бұл соңғы қосынды – гармоникалық қатар, ол шексізке жуықтайды. Алайда, k ≥ 3 болғанда, күтілетін мән анықталған, және жоғарыдағы дәлелдеме бойынша, ол:

1=k=3 үшін бұл шамамен 1.3684-ке тең. 1=k=4 үшін шамамен 1.1106-қа тең.