Sayılar Teorisinin Temel Kavramları

Bölünebilirlik ve temel özellikleri

Tam sayılar a ve b için, a ≠ 0 olmak üzere, b = ak eşitliğini sağlayan bir tam sayı k varsa a’nın b’yi böldüğü söylenir ve a | b yazılır. Burada a bölen, b bölünen, k ise bölüm rolündedir. Örneğin 4 | 20’dir; çünkü 20 = 4 · 5’tir. Buna karşılık 4, 22’yi bölmez; 22’yi 4’ün tam sayı katı biçiminde yazmak mümkün değildir.

Bölünebilirlik bir ilişki olarak bazı temel özellikler taşır. a | b ve b | c ise a | c olur; çünkü b = ak ve c = bℓ ise c = a(kℓ) biçiminde yazılır. Ayrıca a | b ve a | c olduğunda, herhangi iki tam sayı r ve s için a | (rb + sc) geçerlidir. Bu özellik, ortak bölenleri ve doğrusal tam sayı ifadelerini incelerken önemlidir. Örneğin 6 | 18 ve 6 | 30 olduğundan 6, 2·18 − 30 = 6 ifadesini de böler.

Bölme algoritması her a tam sayısı ve pozitif b tam sayısı için a = bq + r, 0 ≤ r < b biçiminde bir bölüm ve kalan yazılabileceğini söyler. Örneğin 47 = 6·7 + 5 olduğundan 47’nin 6’ya bölümünden kalan 5’tir. Kalanın sıfır olması, b | a koşuluyla aynıdır. Bu nedenle bölünebilirlik, EBOB hesaplamasının ve kongrüansların temelini oluşturur: bir sayının diğerine bölümünde kalan sıfırsa tam bölünme gerçekleşir; kalanlar eşitse de iki sayı aynı modüler sınıfta bulunur.

EBOB, EKOK ve Öklid algoritması

İki veya daha fazla tam sayının ortak bölenleri arasındaki en büyük pozitif sayıya en büyük ortak bölen, yani EBOB denir. Ortak katların en küçüğü ise en küçük ortak kat, yani EKOK’tur. EBOB sayıları aynı anda bölen en büyük yapı taşını, EKOK ise sayıların ortak olarak ulaştığı en küçük pozitif katı gösterir. Örneğin 18’in pozitif bölenleri 1, 2, 3, 6, 9, 18; 24’ün pozitif bölenleri 1, 2, 3, 4, 6, 8, 12, 24 olduğundan EBOB(18,24) = 6’dır. Bu sayıların ortak katları içinde en küçüğü 72 olduğu için EKOK(18,24) = 72’dir.

EBOB’u büyük sayılarda verimli biçimde bulmak için Öklid algoritması kullanılır. Algoritma, bölme işlemindeki kalanların ortak bölenleri koruduğu fikrine dayanır: EBOB(a,b) = EBOB(b,r), burada a = bq + r’dir. Kalan sıfır olana kadar ardışık bölme yapılır; sıfırdan önceki son kalan EBOB’u verir. Örneğin 252 ve 198 için 252 = 1·198 + 54, 198 = 3·54 + 36, 54 = 1·36 + 18, 36 = 2·18 + 0. Dolayısıyla EBOB(252,198) = 18’dir.

Pozitif a ve b sayıları için EBOB ile EKOK arasında a·b = EBOB(a,b)·EKOK(a,b) ilişkisi vardır. Bu nedenle 252 ve 198 için EKOK(252,198) = (252·198)/18 = 2772 bulunur. Hangi kavramın kullanılacağı probleme göre ayırt edilir: ortak bölen veya sadeleştirme aranıyorsa EBOB, iki periyodun birlikte tekrar ettiği ilk değer aranıyorsa EKOK; büyük sayıların EBOB’u isteniyorsa ise Öklid algoritması doğrudan araçtır.

Asal sayılar ve asal çarpanlara ayrılma

1’den büyük ve yalnızca 1’e ve kendisine bölünebilen doğal sayılara asal sayı denir. 2, 3, 5, 7 ve 11 asal sayılara örnektir; 1 asal değildir, çünkü yalnızca bir pozitif böleni vardır. Asal sayılar, daha büyük doğal sayıların çarpımsal yapı taşlarıdır. Asal olmayan ve 1’den büyük sayılar bileşik sayı olarak adlandırılır.

Bir doğal sayıyı asal sayıların çarpımı biçiminde yazmaya asal çarpanlara ayırma denir. Örneğin 360 için ardışık olarak 2, 3 ve 5 ile bölme yapılır: 360 = 2·180 = 2·2·90 = 2·2·2·45 = 2³·3²·5. Aynı asal çarpanların üslerle gruplanması, sayının hangi asal yapı taşlarından oluştuğunu açıkça gösterir. Bir sayının asal olup olmadığını sınamak için, sayının kendisinden küçük bütün sayıları denemek yerine kareköküne kadar olan olası bölenleri kontrol etmek yeterlidir; çünkü daha büyük bir bölen varsa ona eşlik eden daha küçük bir çarpan bulunur.

Aritmetiğin temel teoremine göre 1’den büyük her doğal sayı, asal sayıların çarpımı olarak yazılabilir ve bu yazım çarpanların sırası dışında tektir. Bu teklik, EBOB ve EKOK hesaplarını da açıklar. Örneğin 84 = 2²·3·7 ve 90 = 2·3²·5 ise EBOB, ortak asal çarpanların küçük üsleri alınarak 2·3 = 6; EKOK ise tüm asal çarpanların büyük üsleri alınarak 2²·3²·5·7 = 1260 bulunur. Dolayısıyla asal çarpanlara ayırma, ortak bölen ve ortak kat problemlerinde temel yöntemdir.

Kongrüanslar ve temel modüler aritmetik

İki tam sayının belirli bir pozitif m sayısına bölümünden kalanlar aynıysa bu sayılar m modülünde kongrüenttir. a ≡ b (mod m) gösterimi, m | (a − b) anlamına gelir. Örneğin 38 ≡ 3 (mod 7)’dir; çünkü 38 − 3 = 35 ve 7 | 35’tir. Bu ifade, sayıların eşit olduğu anlamına gelmez; yalnızca 7’ye bölündüklerinde aynı kalanı verdiklerini belirtir.

Kongrüanslar toplama, çıkarma ve çarpma altında korunur. a ≡ b (mod m) ve c ≡ d (mod m) ise a + c ≡ b + d, a − c ≡ b − d ve ac ≡ bd (mod m) olur. Bunun nedeni, iki taraftaki farkların m’nin katı olmasıdır. Örneğin 38 ≡ 3 (mod 7) ve 24 ≡ 3 (mod 7) olduğundan 38 + 24 ≡ 6 (mod 7) ve 38·24 ≡ 3·3 ≡ 2 (mod 7) elde edilir. Büyük üslerde de önceki sonuç modüle göre sadeleştirilebilir: 3⁴ = 81 ≡ 4 (mod 7).

Modüler aritmetik, bölünebilirlik sorularını kalan sorularına dönüştürür. Bir ifadenin m’ye bölünüp bölünmediğini anlamak için o ifadenin m modülündeki kalanını hesaplamak yeterlidir. Ancak bölmede dikkat gerekir: a’nın modül m’de çarpma tersi bulunmadan her iki tarafı a’ya bölmek genel olarak geçerli değildir. Örneğin 2x ≡ 2 (mod 6) denkleminde 2’yi doğrudan sadeleştirmek, modülü değiştirmeden yapılamaz; çünkü 2’nin 6 modülünde çarpma tersi yoktur. Bu nedenle toplama ve çarpma işlemleri güvenli temel araçlar, bölme ise ek koşul gerektiren bir işlemdir.

Çin kalan teoremi ve ileri kongrüans sistemleri, birden fazla modüldeki kalan koşullarını birlikte çözmeyi inceler. Fermat’nın küçük teoremi ve Euler teoremi ise belirli koşullar altında üslerin modüler davranışını sistemleştirir; kuadratik kalanlar ve ikinci dereceden kongrüanslar da bu temel dilin daha ileri uygulamalarıdır.

Bézout özdeşliği ve doğrusal Diofant denklemlerine giriş

Bézout özdeşliği, iki tam sayının EBOB’unun bu sayıların tam sayı katsayılı bir doğrusal birleşimi olarak yazılabileceğini söyler: EBOB(a,b) = ax + by. Bu bağlantı, Öklid algoritmasının yalnızca EBOB’u hesaplamadığını, aynı zamanda uygun katsayıları bulmaya da yardım ettiğini gösterir. Örneğin Öklid adımlarını geriye doğru yerine koyarsak 252 ve 198 için 18 = 4·252 − 5·198 elde edilir; yani x = 4 ve y = −5, Bézout katsayılarından biridir.

Doğrusal Diofant denklemi, katsayıları ve bilinmeyenleri tam sayılar olan ax + by = c biçimindeki denklemdir. Bu denklemin tam sayı çözümü bulunabilmesi için ve ancak EBOB(a,b)’nin c’yi bölmesi gerekir. Çünkü ax + by ifadesi, a ve b’nin her ortak böleni tarafından bölünür; tersine Bézout özdeşliği, EBOB’un uygun bir doğrusal birleşim olduğunu gösterir. Örneğin 15x + 21y = 6 denklemi için EBOB(15,21) = 3 ve 3 | 6 olduğundan çözüm vardır. 5x + 7y = 2 biçimine indirgenen denklemin x = 6, y = −4 çözümü, başlangıç denkleminde 15·6 + 21·(−4) = 6 eşitliğini verir. İleri Diofant denklemleri ise bu temel ölçütün ötesindeki daha karmaşık tam sayı çözüm problemlerini ele alır.