asal tamsayılar - Coprime integers

Gelen sayılar teorisi , iki tamsayılar $bir$ ve $b$ olan aralarında asal , aralarında asal veya karşılıklı olarak asal bir tek pozitif tamsayı ise bölen her ikisi herhangi Sonuç 1'dir asal sayı böler birini olduğu $bir$ veya $b$ diğer bölmek yok . Bu onların eşdeğerdir büyük ortak bölen biri de diyor 1. olma (gcd) $bir$ etmek asal olduğunu $b$ veya $bir$ ile aralarında asal olan $b$ .

İndirgenmiş bir kesrin payı ve paydası aralarında asaldır. Tek ortak böleni 1 olduğundan 14 ve 25 sayıları aralarında asaldır. Öte yandan 14 ve 21, ikisi de 7'ye bölünebildiği için aralarında asal değildir.

Notasyon ve test

Göreceli olarak $a$ ve $b$ asal tam sayıları için standart gösterimler şunlardır: $gcd(a, b) = 1$ ve $(a, b) = 1$ . Onların 1989 ders kitabında, Ronald Graham , Donald Knuth ve Ören Patashnik notasyonu önerdi olduğunu belirtmek için kullanılacak $bir$ ve $b$ aralarında asal olan ve (içinde terimi asal yerine "asal" kullanılması $bir$ olan asal için $b$ ) . ${\görüntüleme stili a\perp b}$

İki sayının asal olup olmadığını belirlemenin hızlı bir yolu, Öklid algoritması ve ikili GCD algoritması veya Lehmer'in GCD algoritması gibi daha hızlı varyantları tarafından verilmektedir .

1 ile $n$ arasında pozitif bir $n$ tamsayısıyla birlikte asal tamsayıların sayısı, Euler'in phi işlevi olarak da bilinen $φ$ $($ $n$ $)$ Euler'in totient işlevi tarafından verilir .

Bir dizi onun unsurları tamsayılar kümesi 1. Daha güçlü bir koşul dışında hiçbir ortak olumlu faktör paylaşıyorsanız tamsayılar da aralarında asal çağrılabilir demek olduğunu İkili aralarında asal olduğu $bir$ ve $b$ her çifti için aralarında asal olan $(a, b)$ farklı kümedeki tam sayılar. ${2, 3, 4$ } kümesi asaldır, ancak 2 ve 4 görece asal olmadığından ikili asal değildir.

Özellikler

1 ve -1 sayıları, her tamsayı ile asal olan tek tam sayılardır ve 0 ile asal olan tek tam sayılardır.

Bir dizi koşul, $a$ ve $b'nin$ aralarında asal olmasına eşdeğerdir :

Hiçbir asal sayı böler hem $bir$ ve $b$ .
Tamsayı var $X$ ve $Y$ bu şekilde $ax + tarafından = 1$ (bkz Bezout kimlik ).
Tam sayı $b$ bir sahiptir çarpımsal ters modülo $bir$ tamsayı var olduğu anlamına gelir, $y$ şekilde $tarafından \equiv 1 (mod a)$ . Halka teorik dilinde, $b$ a, birim olarak halka $Z / bir Z$ arasında tamsayılar modulo $bir$ .
$x$ $\equiv$ $k$ $(mod$ $a$ $)$ ve $x$ $\equiv$ $m$ $(mod$ $b$ $)$ biçimindeki bilinmeyen bir $x$ tamsayı için her çift uyum bağıntısının bir çözümü vardır ( Çince kalan teoremi ); aslında çözümler tek bir uyum ilişkisi modulo $ab ile tanımlanır$ .
En sık birden ait $bir$ ve $b$ kendi ürün eşittir $ab$ örneğin, $sm (bir, b) = ab$ .

Üçüncü noktanın bir sonucu olarak, eğer a ve b asal ise ve br ≡ bs ( mod a ), o zaman r ≡ s ( mod a ) olur. Yani, modulo a çalışırken " b'ye bölebiliriz " . Ayrıca, eğer b ₁ ve b ₂ ile her ikisi de aralarında asal olan bir , o zaman da bir ürün B ₁b ₂ (yani modülo bir bir tersinir elemanların ürün ve bu nedenle tersinirdir); Bu aynı zamanda Öklid'in lemmasının ilk noktasından da çıkar ; bu, eğer bir asal sayı p , bir bc ürününü bölerse , o zaman p , b , c faktörlerinden en az birini böler .

Birinci noktanın bir sonucu olarak, eğer a ve b asal ise, o zaman a ^k ve b ^m kuvvetleri de öyledir .

Eğer bir ve b göreceli asal ve vardır bir ürün bölme bc daha sonra, bir bölme c . Bu, Öklid'in lemmasının bir genellemesi olarak görülebilir.

Şekil 1. 4 ve 9 sayıları aralarında asaldır. Bu nedenle, 4 × 9 kafesin köşegeni diğer kafes noktalarıyla kesişmez.

İki a ve b tamsayıları , ancak ve ancak bir Kartezyen koordinat sisteminde koordinatları ( a , b ) olan nokta orijinden (0,0) "görünürse", yani tamsayı koordinatları olan hiçbir nokta olmadığında aralarında asaldır. orijin ve ( a , b ) arasındaki doğru parçası üzerinde . (Bkz. şekil 1.)

Kesinleştirilebilecek bir anlamda, rastgele seçilen iki tamsayının asal olma olasılığı 6/π ^2'dir (bkz. pi ), bu da yaklaşık %61'dir. Aşağıya bakınız.

İki doğal sayı a ve b , ancak ve ancak 2 ^a − 1 ve 2 ^b − 1 sayıları aralarında asal ise aralarında asaldır. Kolayca Aşağıda, bu bir genelleme olarak Öklid algoritma içinde baz n > 1:

\gcd \sol(n^{a}-1,n^{b}-1\sağ)=n^{\gcd(a,b)}-1.

Kümelerde eş birincillik

Bir dizi tamsayılar S = { bir ₁ , bir ₂ , .... bir _n } de çağrılabilir göreceli asal veya setwise göreceli asal olmadığını büyük ortak böleni kümesinin elemanlarının her Örneğin 1'dir, tam sayılar 6, 10, 15 asaldır çünkü 1 hepsini bölen tek pozitif tam sayıdır.

Bir tamsayı kümesindeki her bir çift asal ise, o zaman kümeye ikili asal (veya ikili göreli asal , karşılıklı asal veya karşılıklı olarak göreli asal ) denir . İkili eş eşlilik, kümesel eş eşlilikten daha güçlü bir durumdur; her ikili asal sonlu küme aynı zamanda setsel asaldır, ancak bunun tersi doğru değildir. Örneğin, tam sayı 4, 5, 6 bulunmaktadır (setwise) göreceli asal (bölünmesi sadece pozitif tam sayıdır, çünkü , tüm bunların 1), ancak değildir ikili göreceli asal (nedeniyle gcd (4, 6) = 2).

Çiftli eş-biçimlilik kavramı, Çin kalan teoremi gibi sayı teorisindeki birçok sonuç için bir hipotez olarak önemlidir .

Sonsuz bir tamsayı kümesinin ikili asal olması mümkündür. Dikkate değer örnekler, tüm asal sayılar kümesini, Sylvester dizisindeki öğeler kümesini ve tüm Fermat sayılarının kümesini içerir .

Halka ideallerinde eş birincillik

Değişmeli R halkasındaki iki ideal A ve B , eğer A + B = R ise, koprime (veya komaksimal ) olarak adlandırılır . Bu, Bézout'un özdeşliğini genelleştirir : bu tanımla, Z tamsayıları halkasındaki ( a ) ve ( b ) iki temel ideal , ancak ve ancak a ve b aralarında asal ise , aralarında asaldır. Eğer idealleri A ve B arasında , R olan göreceli asal, daha sonra AB = A ∩ B ; Ayrıca, eğer Cı bu tip üçüncü bir ideal bir içermektedir BC , daha sonra bir içermektedir Cı . Çinli kalanlar teoremi göreceli asal idealleri kullanılarak, herhangi değişmeli halkasına genelleştirilebilir.

Koprimallik olasılığı

Rastgele seçilmiş iki a ve b tamsayısı verildiğinde, a ve b'nin asal olma olasılığının ne kadar olduğunu sormak mantıklıdır . Bu belirlemede, ancak ve ancak her ikisini de bölen bir asal sayı yoksa , a ve b'nin aralarında asal olduğu karakterizasyonunu kullanmak uygundur (bkz . aritmetiğin temel teoremi ).

Gayri, herhangi bir sayıda (ya da aslında, herhangi bir tam sayı) bir asal bölünemeyen bir olasılığı olan ; örneğin, her 7. tamsayı Bu nedenle iki sayı hem bölünebilir ihtimali 7. bölünemeyen bir p olan bunların en az bir adet olan olmadığını ve olasılık . Farklı asal sayılarla ilişkili herhangi bir sonlu bölünebilirlik olayı koleksiyonu karşılıklı olarak bağımsızdır. Örneğin, iki olay söz konusu olduğunda, bir sayı ancak ve ancak pq ile bölünebiliyorsa, p ve q asal sayılarına bölünebilir ; ikinci olay 1/ pq olasılığına sahiptir . Bu tür bir akıl yürütmenin sonsuz sayıda bölünebilirlik olayına genişletilebileceğine dair buluşsal varsayımda bulunulursa, iki sayının aralarında asal olma olasılığının tüm asal sayılar üzerinde bir çarpım tarafından verildiğini tahmin etmeye yönlendiriliriz. ${\görüntüleme stili p}$ ${\ Displaystyle 1/p}$ $1/p^{2}$ $1-1/p^{2}$

\prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\sağ)=\left(\prod _{{\text{ prime }}p}{\frac {1}{1-p^{-2}}}\sağ)^{-1}={\frac {1}{\zeta (2)}}={\frac { 6}{\pi ^{2}}}\yaklaşık 0,607927102\yaklaşık %61\.

Burada ζ , Riemann zeta fonksiyonuna atıfta bulunur , ürünü asal sayılar üzerinden ζ (2) ile ilişkilendiren özdeşlik , bir Euler çarpımı örneğidir ve ζ (2)'nin π ² /6 olarak değerlendirilmesi, Leonhard tarafından çözülen Basel problemidir. Euler 1735'te.

Her pozitif tamsayı eşit olasılıkla ortaya çıkacak şekilde rastgele bir pozitif tamsayı seçmenin bir yolu yoktur, ancak yukarıdakiler gibi "rastgele seçilmiş tamsayılar" hakkındaki ifadeler, doğal yoğunluk kavramı kullanılarak resmileştirilebilir . Her N pozitif tamsayı için, rasgele seçilen iki sayının aralarında asal olma olasılığı P _N olsun . P _N hiçbir zaman tam olarak eşit olmayacak olsa da , çalışma ile kişi, as limitinde olasılığın 'ye yaklaştığını gösterebilir . $\{1,2,\ldots ,N\}$ $6/\pi ^{2}$ ${\ Displaystyle N\to \infty }$ ${\görüntüleme stili P_{N}}$ $6/\pi ^{2}$

Daha genel olarak, rastgele seçilmiş k tamsayının asal olma olasılığı . $1/{\zeta (k)}$

Tüm asal çiftleri oluşturma

Bu algoritma ile asal çiftlerin oluşturulma sırası. Birinci düğüm (2,1) kırmızı olarak işaretlenir, üç çocuğu turuncu ile gösterilir, üçüncü nesil sarıdır ve bu şekilde gökkuşağı düzeninde devam eder.

Tüm pozitif asal sayı çiftleri ( ile ) iki ayrık tam üçlü ağaçta düzenlenebilir , bir ağaç (çift-tek ve tek-çift çiftleri için) ve diğer ağaç (tek-tek çiftleri için) ile başlar. Her köşenin çocukları aşağıdaki gibi oluşturulur: ${\görüntüleme stili (m,n)}$ ${\ Displaystyle m>n}$ ${\görüntüleme stili (2,1)}$ ${\görüntüleme stili (3,1)}$ ${\görüntüleme stili (m,n)}$

Şube 1: ${\görüntüleme stili (2m-n,m)}$
Şube 2: ${\görüntüleme stili (2m+n,m)}$
Şube 3: ${\görüntüleme stili (m+2n,n)}$

Bu şema kapsamlıdır ve geçersiz üyeler olmadan gereksizdir.

Uygulamalar

Makine tasarımında, birbirine geçen iki dişlinin diş sayıları nispeten asal olacak şekilde seçilerek eşit, düzgün bir dişli aşınması elde edilir. 1:1 dişli oranı istendiğinde, aralarına iki eşit boyutlu dişliye görece asal bir dişli yerleştirilebilir.

Bilgisayar öncesi kriptografide , bazı Vernam şifreleme makineleri, farklı uzunluklardaki birkaç anahtar bandı döngüsünü birleştirdi. Birçok rotor makinesi , farklı sayıda dişe sahip rotorları birleştirir. Bu tür kombinasyonlar en iyi, tüm uzunluk kümesi ikili asal olduğunda çalışır.

Ayrıca bakınız

Notlar

Referanslar

Hardy, GH ; Wright, EM (2008), Sayılar Teorisine Giriş (6. baskı), Oxford University Press , ISBN 978-0-19-921986-5
Niven, İvan; Zuckerman, Herbert S. (1966), Sayılar Teorisine Giriş (2. baskı), John Wiley & Sons
Cevher, Oystein (1988) [1948], Sayı Teorisi ve Tarihi , Dover, ISBN 978-0-486-65620-5
Rosen, Kenneth H. (1992), İlköğretim Sayı Teorisi ve Uygulamaları (3. baskı), Addison-Wesley, ISBN 978-0-201-57889-8

daha fazla okuma

Lord, Nick (Mart 2008), "Bazı sonsuz asal dizilerin tek tip bir yapısı", Mathematical Gazette , 92 : 66-70.

Languages

In other projects