En büyük ortak böleni - Greatest common divisor

In matematik , büyük ortak böleni ( OBEB iki veya daha fazla) tamsayılar tamamı sıfır değildir, büyük pozitif tamsayı olduğu böler tamsayılar her. İki tamsayı x , y için , x ve y'nin en büyük ortak böleni gösterilir . Örneğin, 8 ve 12'nin GCD'si 4'tür, yani .

"En büyük ortak bölen" adında, "en büyük" sıfatı "en yüksek" ile değiştirilebilir ve "bölen" kelimesi "faktör" ile değiştirilebilir, böylece diğer isimler en yüksek ortak çarpanı ( hcf ), vb. içerir. Tarihsel olarak, aynı kavram için diğer isimler en büyük ortak ölçüyü içermiştir .

Bu kavram polinomlara (bkz. Polinom en büyük ortak bölen ) ve diğer değişmeli halkalara (aşağıdaki § değişmeli halkalarda bakınız) genişletilebilir .

genel bakış

Tanım

Büyük ortak bölen iki sıfırdan farklı bir (GCD) tamsayı , bir ve b büyük olan pozitif bir tam sayı d böyle d a, bölen ikisinin a ve b ; olduğu, tam sayı vardır e ve f , öyle ki , bir = de ve b = df ve d büyük, örneğin tamsayıdır. Arasında elusyonu bir ve b , genel olarak ifade edilmiş olan gcd ( a , b ) .

Bu tanım, a ve b'den biri sıfır olduğunda da geçerlidir . Bu durumda, OBEB sıfır olmayan tamsayının mutlak değeridir: gcd( a , 0) = gcd(0, a ) = | bir | . Bu durum Öklid algoritmasının sonlandırma adımı olarak önemlidir .

Yukarıdaki tanım tanımlamak için kullanılamaz gcd (0, 0) itibaren, 0 x , n = 0 ve sıfır dolayısıyla büyük bölen sahiptir. Bununla birlikte, en büyük bölünebilirlik ilişkisi bağlamında anlaşılırsa sıfır kendi en büyük bölenidir , bu nedenle gcd(0, 0) genellikle 0 olarak tanımlanır. Bu, GCD için olağan kimlikleri ve özellikle Bézout'un kimliğini , yani gcd kimliğini korur. ( a , b ) oluşturur aynı ideali kadar { a , b } . Bu kuralı birçok bilgisayar cebir sistemi takip eder . Bununla birlikte, bazı yazarlar gcd(0, 0)'ı tanımsız bırakır .

Ait OBEB bir ve b onların olduğu büyük pozitif ortak böleni ön sipariş ilişkisi içinde bölünebilme . Bu, a ve b'nin ortak bölenlerinin tam olarak onların GCD'lerinin bölenleri olduğu anlamına gelir . Bu genellikle ya Öklid'in lemması , aritmetiğin temel teoremi ya da Öklid algoritması kullanılarak kanıtlanır . Bu, GCD kavramının genellemelerinde kullanılan "en büyük"ün anlamıdır.

Örnek

54 sayısı iki tam sayının çarpımı olarak birkaç farklı şekilde ifade edilebilir:

Böylece 54'ün tam bölen listesi . Benzer şekilde, 24'ün bölenleri de . Bu iki liste olduğunu numaraları ortak noktası olan ortak bölenler vardır 54 ve 24,

Bunlardan en büyüğü 6'dır, yani en büyük ortak bölendir :

İki sayının tüm bölenlerini bu şekilde hesaplamak, özellikle çok sayıda böleni olan büyük sayılar için genellikle verimli değildir. Çok daha verimli yöntemler § Hesaplama bölümünde açıklanmıştır .

asal sayılar

En büyük ortak bölenleri 1'e eşitse , iki sayı nispeten asal veya asal olarak adlandırılır. Örneğin, 9 ve 28 nispeten asaldır.

Geometrik bir görünüm

"Bir kareler ızgarasına bölünmüş uzun, ince dikdörtgen. Dikdörtgen iki kare genişliğinde ve beş kare uzunluğundadır."
24'e 60'lık bir dikdörtgen on adet 12'ye 12 kare karoyla kaplanır , burada 12, 24 ve 60'ın GCD'sidir. Daha genel olarak, bir a- by- b dikdörtgeni yalnızca kenar uzunluğu c olan kare karolarla kaplanabilir. eğer c ortak bir böleni olan bir ve b .

Örneğin, 24'e 60 dikdörtgen alan bir ızgaraya bölünebilir: 1'e 1 kareler, 2'ye 2 kareler, 3'e 3 kareler, 4'e 4 kareler, 6'ya -6 kare veya 12'ye 12 kare. Bu nedenle, 12, 24 ve 60'ın en büyük ortak bölenidir. 24'e 60 dikdörtgen bir alan, böylece, bir kenar boyunca iki kare (24/12 = 2) ve 12'ye 12 kareden oluşan bir ızgaraya bölünebilir ve diğer boyunca beş kare (60/12 = 5).

Uygulamalar

kesirleri azaltmak

En büyük ortak bölen, kesirleri en düşük terimlere indirgemek için kullanışlıdır . Örneğin, gcd(42, 56) = 14, bu nedenle,

En küçük ortak Kat

En büyük ortak bölen biliniyorsa, iki sayının en küçük ortak katını bulmak için en büyük ortak bölen kullanılabilir.

Hesaplama

Asal çarpanlara ayırma

En büyük ortak bölenler , iki sayının asal çarpanlarına ayrılarak ve çarpanları karşılaştırarak hesaplanabilir . Örneğin, gcd(48, 180) hesaplamak için, 48 = 2 4  · 3 1 ve 180 = 2 2  · 3 2  · 5 1 asal çarpanlarına ayırmalarını buluruz ; O halde OBEB, Venn şemasında gösterildiği gibi 2 dak(4,2)  · 3 dak(1,2)  · 5 dak(0,1) = 2 2  · 3 1  · 5 0 = 12'dir . Karşılık gelen LCM daha sonra 2 maks(4,2)  · 3 maks(1,2)  · 5 maks(0,1) = 2 4  · 3 2  · 5 1 = 720'dir.

En az yaygın çoklu.svg

Pratikte, bu yöntem yalnızca küçük sayılar için uygundur, çünkü asal çarpanlara ayırma işlemi çok uzun sürer.

Öklid'in algoritması

Tarafından sunulan yöntem Öklid büyük ortak bölenler hesaplanması için iki pozitif tamsayılar verilen gerçeğine dayanır bir ve b , öyle ki , bir > b , yaygın bölenler bir ve b yaygın bölenler aynıdır bir - b ve b .

Bu nedenle, Öklid'in iki pozitif tamsayının en büyük ortak bölenini hesaplama yöntemi, daha büyük sayıyı sayıların farkıyla değiştirmek ve bunu iki sayı eşit olana kadar tekrar etmekten oluşur: bu onların en büyük ortak bölenidir.

Örneğin, gcd(48,18) hesaplamak için aşağıdaki gibi hareket edilir:

Yani gcd(48, 18) = 6 .

Bir sayı diğerinden çok daha büyükse bu yöntem çok yavaş olabilir. Bu nedenle, aşağıdaki varyant genellikle tercih edilir.

Öklid algoritması

62 ve 36'nın en büyük ortak bölenini, yani 2'yi bulmak için Öklid algoritmasının bir uygulamasını gösteren animasyon.

Daha verimli bir yöntem Öklid algoritması , iki sayının farkı olan bir varyantı , bir ve b ile ikame edilir kalanı arasında Öklid bölümü (aynı zamanda geri kalan bölümü arasında) bir tarafından b .

Bu kalan gösteren bir mod b , algoritma yerine geçer ( bir , b ) ile ( b , bir mod b ) çifti kadar art arda ( d , 0) , d büyük ortak bölenin.

Örneğin, gcd(48,18) hesaplamak için hesaplama aşağıdaki gibidir:

Bu yine gcd(48, 18) = 6 değerini verir .

Lehmer'in GCD algoritması

Lehmer'in algoritması, Euclid'in algoritması tarafından üretilen ilk bölümlerin yalnızca ilk birkaç basamağa dayalı olarak belirlenebileceği gözlemine dayanır; bu, bir bilgisayar sözcüğünden daha büyük sayılar için kullanışlıdır . Özünde, tipik olarak bir veya iki bilgisayar sözcüğü oluşturan ilk basamakları çıkarır ve bölümlerin orijinal sayılarla elde edilecek olanlarla aynı olduğu garanti edildiği sürece, Öklid'in algoritmalarını bu daha küçük sayılar üzerinde çalıştırır. Bu bölümler , orijinal sayıları azaltmak için hepsini bir kerede kullanmak için küçük bir 2'ye 2 dönüşüm matrisinde (yani tek kelimelik tam sayıların bir matrisi) toplanır . Bu işlem, sayılar ikili algoritmanın (aşağıya bakınız) daha verimli olması için yeterince küçük olana kadar tekrarlanır.

Bu algoritma hızı artırır, çünkü çok büyük sayılardaki işlem sayısını azaltır ve çoğu işlem için donanım aritmetiğini kullanabilir. Aslında, bölümlerin çoğu çok küçüktür, bu nedenle Öklid algoritmasının oldukça fazla adımı 2'ye 2 tek kelimelik tamsayılar matrisinde toplanabilir. Lehmer'in algoritması çok büyük bir bölümle karşılaştığında , büyük sayıların bir Öklid bölümü ile Öklid algoritmasının bir yinelemesine geri dönmelidir .

İkili GCD algoritması

İkili OBEB algoritması sadece çıkarma ve 2'ye bölmeyi kullanır. Yöntem şu şekildedir: a ve b negatif olmayan iki tam sayı olsun. d tamsayısı 0 olsun. Beş olasılık vardır:

  • bir = b .

gcd( a , a ) = a olarak , istenen GCD a × 2 d'dir ( diğer durumlarda a ve b değiştirildiğinden ve d , a ve b'nin bir sonraki seferde kaç kez 2'ye bölündüğünü kaydeder. adımda, ilk çiftin GCD'si a ve 2 d )' nin çarpımıdır .

  • Hem a hem de b çifttir.

O zaman 2 ortak bölendir. Her iki bölün a ve b , 2 ile, artım d 1 ile 2 ortak bölen ve devam sayısını kaydetmek için kullanılır.

  • a çifttir ve b tektir.

O zaman 2 ortak bölen değildir. Divide bir 2 oranında ve devam edin.

  • a tek, b çifttir.

O zaman 2 ortak bölen değildir. b'yi 2'ye bölün ve devam edin.

  • Hem a hem de b tektir.

Gcd (de bir , b ) = gcd ( b , bir ), eğer bir < b sonra alışverişi bir ve b . Sayı C = bir - b pozitif ve daha küçük olan bir . a ve b'yi bölen herhangi bir sayı aynı zamanda c'yi de bölmelidir, böylece a ve b'nin her ortak böleni aynı zamanda b ve c'nin ortak böleni olur . Benzer şekilde, a = b + c ve b ve c'nin her ortak böleni aynı zamanda a ve b'nin ortak bölenidir . Yani ( a , b ) ve ( b , c ) iki çifti aynı ortak bölenlere sahiptir ve dolayısıyla gcd( a , b ) = gcd( b , c ). Ayrıca, a ve b'nin ikisi de tek olduğundan, c çift ​​olduğundan , OBEB'yi değiştirmeden ( a , b ) çifti yerine daha küçük sayılar ( c /2, b ) ile işleme devam edilebilir .

Yukarıdaki adımların her biri, a ve b'den en az birini azaltırken, onları negatif olmayan bırakır ve bu nedenle yalnızca sınırlı sayıda tekrarlanabilir. Böylece sonunda süreç , durma durumu olan a = b ile sonuçlanır . O halde OBEB bir × 2 d'dir .

Örnek: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; orijinal GCD bu nedenle 2 d = 2 1 ve a = b = 3'ün 6 çarpımıdır .

İkili GCD algoritmasının ikili bilgisayarlarda uygulanması özellikle kolaydır. Onun hesaplama karmaşıklığı olduğunu

Hesaplama karmaşıklığı genellikle girdinin uzunluğu n cinsinden verilir . Burada, bu uzunluk ve karmaşıklık böylece

.

Diğer yöntemler. Diğer metodlar

veya Thomae'nin işlevi. Alttaki tarama , elipsleri gösterir (yani, aşırı yüksek yoğunluktan dolayı noktaların atlanması).

Eğer bir ve B her ikisi de sıfır olmayan, en büyük ortak böleni olan bir ve b kullanılarak hesaplanabilir az ortak katı arasında (LCM) , bir ve  b :

,

ancak daha yaygın olarak LCM, GCD'den hesaplanır.

Thomae'nin f fonksiyonunu kullanarak ,

a ve b rasyonel sayılara veya ölçülebilir gerçek sayılara genelleme yapar .

Keith Slavin, tek a  ≥ 1 için şunu göstermiştir :

bu, b kompleksi için değerlendirilebilecek bir fonksiyondur . Wolfgang Schramm göstermiştir ki

Bir olan tüm işlev değişken olarak b tüm pozitif tamsayılar için bir yerde C d ( k ) 'dir Ramanujan toplamı .

karmaşıklık

En büyük ortak bölenlerin hesaplanmasının hesaplama karmaşıklığı geniş çapta incelenmiştir. Kullanıyorsa Öklid algoritma ve çarpma ve bölme için temel algoritmalar, en fazla iki tamsayılar büyük ortak bölücü hesaplama n bit olan büyük ortak bölücü hesaplama sabit bir faktör kadar, sahip olduğu, aynı Bu araçlar çarpım olarak karmaşıklık.

Bununla birlikte, hızlı bir çarpma algoritması kullanılıyorsa, karmaşıklığı geliştirmek için Öklid algoritması değiştirilebilir, ancak en büyük ortak bölenin hesaplanması çarpmadan daha yavaş olur. Daha doğrusu, n bitlik iki tamsayının çarpımı bir T ( n ) zamanını alıyorsa , en büyük ortak bölen için bilinen en hızlı algoritmanın bir karmaşıklığı vardır. Bu, bilinen en hızlı algoritmanın bir karmaşıklığa sahip olduğu anlamına gelir.

Önceki karmaşıklıklar, olağan hesaplama modelleri , özellikle çok bantlı Turing makineleri ve rastgele erişimli makineler için geçerlidir .

Bu nedenle, en büyük ortak bölenlerin hesaplanması, yarı-doğrusal zamanda çözülebilen problemler sınıfına aittir . A fortiori , karşılık gelen karar problemi , polinom zamanında çözülebilen problemlerin P sınıfına aittir . GCD sorununun NC'de olduğu bilinmiyor ve bu nedenle onu verimli bir şekilde paralelleştirmenin bilinen bir yolu yok ; ne de P-complete olduğu bilinmemektedir , bu da GCD hesaplamasını verimli bir şekilde paralelleştirmenin mümkün olmadığı anlamına gelir. Shallcross ve ark. ilgili bir problemin (EUGCD, Öklid algoritması sırasında ortaya çıkan kalan diziyi belirleme) iki değişkenli tamsayılı doğrusal programlama problemine NC eşdeğeri olduğunu gösterdi ; problemlerden biri NC'deyse veya P-tamamlandıysa , diğeri de öyledir. Bu yana Kuzey Carolina içeren NL , GCD'yı hesaplanması için bir alanı etkin bir algoritma nondeterministic Turing makineleri için, var olup olmadığını da bilinmemektedir.

Sorunun NC'de olduğu bilinmemekle birlikte , Öklid algoritmasından asimptotik olarak daha hızlı paralel algoritmalar mevcuttur; Bilinen en hızlı deterministik algoritma, ( CRCW-PRAM modelinde) sorunu O ( n /log n ) zamanında n 1+ε işlemci ile çözebilen Chor ve Goldreich'a aittir . Rastgele algoritmalar , sorunu işlemcilerde O ((log n ) 2 ) zamanında çözebilir (bu süperpolinomdur ).

Özellikler

  • a ve b'nin her ortak böleni, gcd( a , b )' nin bir bölenidir .
  • gcd ( a , b ) , bir ve B en küçük pozitif tam sayı olarak hem de sıfır değildir, alternatif olarak ve eşdeğer tanımlanabilir d şekilde yazılabilir d = birp + bq , s ve q vardır tamsayılar. Bu ifadeye Bézout'un kimliği denir . Bunun gibi p ve q sayıları , genişletilmiş Öklid algoritması ile hesaplanabilir .
  • gcd( a , 0) = | bir | İçin bir ≠ 0 herhangi bir sayı, 0 bir bölen olduğunu ve en büyük böleni beri, bir olduğunu | bir |. Bu genellikle Öklid algoritmasında temel durum olarak kullanılır.
  • Eğer bir böler ürün Bc ve gcd ( a , b ) = D , daha sonra bir / d bölme c .
  • Eğer m , negatif olmayan bir tam sayı olduğu, daha sonra (GCD'nın mbir , mb ) = m ⋅gcd ( a , b ) .
  • Eğer m, daha sonra herhangi bir tam sayı olduğu GCD'nın ( bir + mb , b ) = gcd ( a , b ) .
  • Eğer m olumlu bir ortak böleni olan bir ve b , daha sonra (GCD'nın bir / m , b / m ) = gcd ( a , b ) / m .
  • OBEB şu anlamda bir çarpımsal fonksiyondur : a 1 ve a 2 göreceli olarak asal ise, o zaman gcd( a 1a 2 , b ) = gcd( a 1 , b )⋅gcd( a 2 , b ) . Özellikle, OBAB'nin pozitif tamsayı değerli bir fonksiyon olduğunu hatırlayarak, gcd( a , bc ) = 1 olduğunu ancak ve ancak gcd( a , b ) = 1 ve gcd( a , c ) = 1 ise elde ederiz .
  • OBEB değişmeli bir fonksiyondur: gcd( a , b ) = gcd( b , a ) .
  • OBEB bir ilişkisel fonksiyondur: gcd( a , gcd( b , c )) = gcd(gcd( a , b ), c ) . Böylece gcd( a , b , c , ...) birden çok argümanın GCD'sini belirtmek için kullanılabilir.
  • gcd ( a , b ) ile yakından ilişkili olduğu en sık birden LCM ( a , b ) : Elimizdeki
    gcd( a , b )⋅lcm( a , b ) = | birb | .
Bu formül genellikle en küçük ortak katları hesaplamak için kullanılır: önce Öklid'in algoritması ile GCD hesaplanır ve ardından verilen sayıların çarpımı GCD'lerine bölünür.
  • Aşağıdaki dağıtım sürümleri geçerlidir:
    gcd( a , lcm( b , c )) = lcm(gcd( a , b ), gcd( a , c ))
    lcm( a , gcd( b , c )) = gcd(lcm( a , b ), lcm( a , c )) .
  • a = p 1 e 1 p 2 e 2 ⋅⋅⋅ p m e m ve b = p 1 f 1 p 2 f 2 ⋅⋅⋅ p m f m'nin benzersiz asal çarpanlarına sahipsek, burada e ben ≥ 0 ve f i 0 ≥ , daha sonra GCD'yı bir ve b olan
    gcd( a , b ) = p 1 dak( e 1 , f 1 ) p 2 dak( e 2 , f 2 ) ⋅⋅⋅ p m min( e m , f m ) .
  • Bazen gcd(0, 0) = 0 ve lcm(0, 0) = 0'ı tanımlamak yararlıdır , çünkü o zaman doğal sayılar , GCD'nin buluşma ve LCM'nin birleştirme işlemi olarak tam bir dağıtım örgüsü haline gelir . Tanımın bu uzantısı, aşağıda verilen değişmeli halkalar için genelleme ile de uyumludur.
  • Bir de Kartezyen koordinat sistemi , gcd ( a , b ) düz yekpare koordinatları ile nokta arasındaki parçaların sayısı olarak yorumlanabilir çizgi parçası noktalarını birleştiren (0, 0) ve ( a , b ) .
  • a ve b'nin her ikisinin de sıfır olmadığı negatif olmayan a ve b tam sayıları için , n tabanında Öklid algoritması dikkate alınarak kanıtlanabilir  :
    gcd( n bir − 1, n b − 1) = n gcd( bir , b ) − 1 .
  • Euler'in totient işlevini içeren bir kimlik :

Olasılıklar ve beklenen değer

1972'de James E. Nymann , {1, ..., n } arasından bağımsız ve düzgün bir şekilde seçilen k tamsayının,  n sonsuza giderken 1/ ζ ( k ) olasılıkla eş asal olduğunu gösterdi; burada ζ , Riemann zeta'yı ifade eder. işlev . (Bkz asal türetilmesi için). Bu sonuç, göstermek için 1987 yılında uzadığı olasılığı k rasgele tamsayılar büyük ortak bölen sahip d isimli d -k / ζ ( k ).

Bu bilgileri kullanarak, beklenen değer büyük ortak böleni fonksiyonu zaman var olmayan için (gayri) görülebilir k  = Bu durumda: 2. olasılık OBEB eşittir d is d -2 / ζ (2), ve o zamandan beri Ç (2) = π 2 /6 elimizde

Bu son toplama , birbirinden ayrılan harmonik seridir . Ancak, k  ≥ 3 olduğunda, beklenen değer iyi tanımlanmıştır ve yukarıdaki argümana göre,

İçin k  = 3, bu 1.3684 yaklaşık olarak eşittir. İçin k  = 4, yaklaşık 1,1106 olduğunu.

OBEB'nin bir argümanı bir değere sabitlenirse , diğer değişkende çarpımsal bir fonksiyon haline gelecek ve gösterilebilir ki

Burada, tüm asal güçler üzerinde ürünü ifade eder öyle ki ancak

değişmeli halkalarda

En büyük ortak bölen kavramı daha genel olarak keyfi bir değişmeli halkanın elemanları için tanımlanabilir , ancak genel olarak her eleman çifti için bir tane olması gerekmez.

Eğer R, değişmeli halkadır ve bir ve b olan , R , o zaman bir eleman d ait R bir adlandırılan ortak bölen bir bir ve b her iki böler ise a ve b elemanları varsa, bir ( x ve y de R öyle ki d · x  =  a ve d · y  =  b ). Eğer d bir ortak böleni olan bir ve b ve her ortak böleni bir ve b böler d , ardından d bir denir büyük ortak böleni ait bir ve b .

Bu tanımla, iki eleman a ve b pek çok en büyük ortak bölenlere sahip olabilir veya hiç olmayabilir. Eğer R bir integral alan ise, o zaman a ve b'nin herhangi iki GCD'si ortak elemanlar olmalıdır , çünkü tanım gereği birinin diğerini bölmesi gerekir; gerçekten de bir GCD varsa, onun ortaklarından herhangi biri de bir GCD'dir. Bir GCD'nin varlığı, keyfi integral alanlarda garanti edilmez. Bununla birlikte, R, a, tek çarpanlama , daha sonra herhangi bir iki eleman bir GCD'yı, ve daha genel olarak, bu doğrudur GCD'yı etki . Eğer R, a, Öklid alan Öklides bölme algoritmik olarak verildiği (örneğin olduğu gibi olduğunda R, = F [ X ] F a, alan , veya R ' halkasıdır Gauss tamsayı ), daha sonra en büyük ortak bölenler olabilir bölme prosedürüne dayalı bir Öklid algoritması formu kullanılarak hesaplanır.

Aşağıda, GCD'si olmayan iki elemanlı bir integral alan örneği verilmiştir:

2 ve 1 +  −3 öğeleri iki maksimal ortak bölendir (yani, 2'nin katı olan herhangi bir ortak bölen 2 ile ilişkilendirilir, aynısı 1 + −3 için de geçerlidir  , ancak ilişkili değildirler, yani a ve  b'nin en büyük ortak böleni değildir .

Bezout özelliğine karşılık gelen biz, bir değişmeli halkada, bir şekilde elemanların toplama düşünebilir pa  +  QB , p ve q, halka üzerinde aralığında. Bu, a ve b tarafından oluşturulan idealdir ve basitçe ( ab ) ile gösterilir. Tüm idealleri asal olan bir halkada (bir asal ideal alan veya PID), bu ideal bazı halka elemanlarının d katları kümesiyle aynı olacaktır ; o zaman bu d , a ve b'nin en büyük ortak bölenidir . Ancak ideal ( ab ) a ve b'nin en büyük ortak böleni olmadığında bile faydalı olabilir . (Aslında Ernst Kummer , Fermat'ın Son Teoremi'ni ele alırken bir GCD'nin yerine bu ideali kullandı , ancak bunu bazı varsayımsal veya ideal halka elemanı d' nin katları olarak tasavvur etmesine rağmen , halka teorik terimi buradan gelmektedir.)

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma