Sayılar Teorisi: Bölünebilirlikten Modüler Aritmetiğe

Bölünebilirlik tanımından EBOB ve EKOK’a geçiş

Tam sayılar a ve b için a ≠ 0 olmak üzere a | b yazımı, b = ak olacak şekilde bir k tam sayısının bulunması anlamına gelir. Örneğin 4 | 20 doğrudur çünkü 20 = 4·5; 4 | 22 yanlıştır çünkü 22/4 tam sayı değildir. Bu tanımda bölümün tam sayı olması gerekir; kesirli bir bölüm, bölünebilirlik için yeterli değildir.

EBOB(a,b), hem a’yı hem b’yi bölen pozitif tam sayılar içinde en büyük olanıdır. Bu değer, iki sayıyı aynı anda bölen en büyük ölçüyü verir. EKOK(a,b) ise hem a’nın hem b’nin katı olan pozitif tam sayılar içinde en küçük olanıdır. Aralarında asal iki sayıda EBOB 1 olur; ancak bu durum sayılardan birinin asal olduğu anlamına gelmez. Örneğin 8 ve 15 aralarında asaldır, fakat ikisi de asal değildir.

Pozitif a ve b için asal çarpan gösterimleri biliniyorsa EBOB’da ortak asal çarpanların küçük üsleri, EKOK’ta görülen tüm asal çarpanların büyük üsleri alınır. Ayrıca şu ilişki geçerlidir: EBOB(a,b)·EKOK(a,b) = a·b. Bu ilişki pozitif tam sayılar için kullanılmalıdır.

EBOB hesaplamada daha hızlı yöntem Öklid algoritmasıdır. a = bq + r biçiminde yazıldığında EBOB(a,b) = EBOB(b,r) olur. Kalan sıfıra ulaşıldığında, sıfır olmayan son kalan EBOB’dur. Bu yöntem, sayıları asal çarpanlarına ayırmadan ortak böleni bulmayı sağlar.

Asal çarpanlar ve sayıların yapısını okuma

1’den büyük ve yalnızca 1’e ve kendisine bölünebilen pozitif tam sayılara asal sayı denir. 1 asal değildir; çünkü iki farklı pozitif böleni yoktur. Asal sayılar, pozitif tam sayıların çarpan yapısını çözümlemede temel yapı taşlarıdır.

Aritmetiğin Temel Teoremi’ne göre 1’den büyük her pozitif tam sayı, asal sayıların çarpımı olarak yazılabilir ve bu gösterim, çarpanların sırası dışında tektir. Örneğin 360 = 2³·3²·5’tir. Bu gösterimden yalnızca sayının kendisi değil, bölenleri hakkında da bilgi çıkarılır.

Bir sayının pozitif bölen sayısı, n = p₁ üzeri a₁ · p₂ üzeri a₂ · ... · pᵣ üzeri aᵣ biçimindeyse τ(n) = (a₁+1)(a₂+1)...(aᵣ+1) ile bulunur. Çünkü her bölen için pᵢ’nin üssü 0’dan aᵢ’ye kadar seçilebilir. Aynı örnekte 360 = 2³·3²·5 olduğundan τ(360) = 4·3·2 = 24’tür.

Bölenlerin toplamı için σ(n) = (1+p₁+...+p₁ üzeri a₁) çarpı ... çarpımı kullanılır. 360 için σ(360) = (1+2+4+8)(1+3+9)(1+5) = 15·13·6 = 1170 olur. Bu formüller, asal çarpan gösterimi elde edildikten sonra uygulanır; sayı asal çarpanlarına ayrılmadan doğrudan kullanılamaz.

Kalan sorularında modüler aritmetiği doğru kullanma

a ≡ b (mod n) ifadesi, n’nin a-b’yi bölmesi demektir. Başka bir ifadeyle a ve b, n’ye bölündüğünde aynı kalanı verir. Örneğin 38 ≡ 8 (mod 10), çünkü 38-8 = 30 ve 10 | 30’dur. Modül n pozitif bir tam sayı olarak alınır.

Kongrüanslarda toplama, çıkarma ve çarpma yapılabilir: a ≡ b (mod n) ve c ≡ d (mod n) ise a+c ≡ b+d, a-c ≡ b-d ve ac ≡ bd (mod n) sonuçları elde edilir. Üs alma da çarpmanın tekrarı olduğundan kongrüans korunur. Ancak bölme, normal eşitlikteki gibi otomatik yapılamaz. ax ≡ ay (mod n) ifadesinden x ≡ y (mod n) sonucu ancak sadeleştirme için gerekli ortak bölen koşulları incelendiğinde çıkarılabilir.

Bir sayıyı mod n’ye göre küçültmek, özellikle büyük üslerde işlem yükünü azaltır. Örneğin 7² ≡ 2 (mod 5) olduğundan 7⁴ ≡ 2² ≡ 4 (mod 5) yazılabilir. Kalan 0 ise sayı modüle tam bölünür; kalan 1 ise sayı modülle aralarında asal olabilir, fakat bu tek başına her durumda yeterli bir kanıt değildir.

Euler Teoremi yalnızca gcd(a,n)=1, yani a ile n’nin aralarında asal olması koşulunda a üzeri φ(n) ≡ 1 (mod n) sonucunu verir. Burada φ(n), 1’den n’ye kadar olan sayılardan n ile aralarında asal olanların sayısıdır; eşdeğer olarak 1 ≤ k ≤ n ve gcd(k,n)=1 koşulunu sağlayan k’lerin sayısıdır. n asal p ise φ(p)=p-1 olur. Fermat’ın Küçük Teoremi de p asal ve p, a’yı bölmüyorsa a üzeri (p-1) ≡ 1 (mod p) biçiminde uygulanır. Koşul sağlanmıyorsa bu teoremler doğrudan kullanılamaz.

Aritmetik fonksiyonlarda sonucu yorumlama

Aritmetik fonksiyon, pozitif tam sayılara sayı-teorik bir özellik atayan fonksiyondur. τ(n), pozitif bölenlerin sayısını; σ(n), pozitif bölenlerin toplamını; φ(n) ise n ile aralarında asal olan ve 1 ile n arasındaki sayıların adedini verir.

Bu değerlerin ne anlama geldiği, sorunun karar kuralını belirler. Pozitif n>1 için τ(n)=24 ise n bileşiktir; ancak bu bilgi n’nin asal çarpanlarını veya kendisini tek başına belirlemeye yetmez. Eğer n asal ise τ(n)=2’dir. σ(n)=n+1 olması, n’nin asal olduğunu gösteren kullanışlı bir durumdur; fakat bu eşitlik, pozitif bölenler ve n>1 bağlamında değerlendirilmelidir.

φ(n)=n-1 olması, n’nin asal olduğu durumda doğrudur. Ancak bu eşitlik bazı bileşik sayılarda da görülebilir mi sorusu ayrıca incelenmelidir; bu nedenle φ değerini yorumlarken yalnızca tek bir örnekten genelleme yapılmamalıdır. Aralarında asal m ve n için φ(mn)=φ(m)φ(n) çarpımsallığı kullanılabilir. Bu koşul yoksa formül doğrudan uygulanmaz.

Bir fonksiyonun çarpımsal olması, her m ve n için değil, özellikle gcd(m,n)=1 koşulunda çarpımın fonksiyon değerlerinin çarpımına eşit olması demektir. Bu ayrım, aritmetik fonksiyon sorularında en sık gözden kaçan koşullardan biridir.

Çözümlü örnekler: EBOB ve modüler üs hesabı

Örnek 1 — Verilenler: 252 ve 198 sayılarının EBOB’unu bulalım.

1. adım: Büyük sayıyı küçük sayıya bölelim: 252 = 198·1 + 54.
2. adım: 198’i 54’e bölelim: 198 = 54·3 + 36.
3. adım: 54’ü 36’ya bölelim: 54 = 36·1 + 18.
4. adım: 36’yı 18’e bölelim: 36 = 18·2 + 0.
5. adım: Sıfır olmayan son kalan 18 olduğundan EBOB(252,198)=18’dir.

Kontrol: 252/18=14 ve 198/18=11 tam sayıdır. Ayrıca 18’den büyük bir ortak bölen bulunmadığı Öklid algoritmasının son adımından anlaşılır.

Örnek 2 — Verilenler: 3 üzeri 20 mod 7 değerini bulalım.

1. adım: 7 asal ve gcd(3,7)=1 olduğundan Fermat’ın Küçük Teoremi uygulanabilir: 3 üzeri 6 ≡ 1 (mod 7).
2. adım: 20’yi 6’nın katı ve kalan biçiminde yazalım: 20 = 6·3 + 2.
3. adım: 3 üzeri 20 = (3 üzeri 6) üzeri 3 · 3 üzeri 2 olduğundan kongrüansla 3 üzeri 20 ≡ 1 üzeri 3 · 9 (mod 7).
4. adım: 9 ≡ 2 (mod 7).

Sonuç: 3 üzeri 20’nin 7’ye bölümünden kalan 2’dir. Burada teoremin kullanılabilmesinin nedeni taban 3 ile modül 7’nin aralarında asal olmasıdır.

Sık yapılan hatalar ve karıştırılan sınır durumları

1. 1’i asal sanmak: 1’in yalnızca bir pozitif böleni vardır; bu nedenle asal tanımını karşılamaz.

2. Bölünebilirliği kesirli bölümle karıştırmak: a | b için b/a oranının tam sayı olması gerekir. 3/2’nin bir sayı olması, 2 | 3 anlamına gelmez.

3. EBOB ile EKOK’ta üsleri ters seçmek: Asal çarpan gösteriminde EBOB için küçük üs, EKOK için büyük üs alınır.

4. Modüler aritmetikte bölme yapmak: Kongrüanslarda çarpan sadeleştirme, normal eşitlikteki kadar serbest değildir. Sadeleştirilen çarpanın modülle aralarında asal olup olmadığı kontrol edilmelidir.

5. Fermat veya Euler teoremini koşulsuz uygulamak: Fermat için modülün asal olması ve tabanın modülü bölmemesi; Euler için taban ile modülün aralarında asal olması gerekir.

6. EBOB’un 1 olmasını sayıların asal sanmak: EBOB(8,15)=1 olmasına rağmen 8 ve 15 bileşiktir.

7. Asal çarpanlara ayırmadan bölen sayısı formülünü kullanmak: τ(n) ve σ(n) formüllerindeki üsler, asal çarpan gösteriminden gelir.

8. Asal Sayı Teoremi’ni kesin sayım formülü sanmak: π(x) ~ x/ln(x), x büyürken yaklaşık/asimptotik davranışı ifade eder; belirli küçük bir x için asal sayıların tam sayısını doğrudan vermez.

Sayılar teorisinin ileri bağlantıları ve uygulama sınırı

Analitik sayı teorisi, asal sayıların dağılımı gibi sorulara analiz ve karmaşık analiz araçlarıyla yaklaşır. Riemann zeta fonksiyonu, uygun yakınsaklık koşulları altında ζ(s)=Σ 1/n üzeri s serisiyle ifade edilir ve asal sayılarla bağlantılı sonuçların incelenmesinde kullanılır. Asal Sayı Teoremi, π(x) yaklaşık olarak x/ln(x) davranışını x sonsuza giderken açıklar. Bu ifade, sonlu bir aralıkta tam asal sayısı değildir.

Cebirsel sayı teorisi, tam sayılar dışındaki cebirsel tam sayıları ve bunların oluşturduğu cebirsel yapıları inceler. Cebirsel tam sayı, tamsayı katsayılı monik bir polinomun kökü olarak tanımlanır. Bu alanda halka ve ideal kavramları önemli araçlardır; ancak her halka, tam sayılar halkasıyla aynı özelliklere sahip değildir.

Diophantine denklemleri, çözümleri tam sayılarda veya kimi zaman doğal sayılarda aranan denklemlerdir. x²+y²=z², bu tür problemlere örnektir. Bir denklemin reel çözümünün bulunması, tam sayı çözümünün bulunduğunu göstermez; çözüm kümesinin hangi sayı kümesinde arandığı mutlaka belirtilmelidir.

Kriptografide asal sayılar ve modüler aritmetik kullanılır. RSA örneğinde iki asal sayının çarpımıyla oluşturulan bir sayının çarpanlarına ayrılmasının hesaplama açısından zor olması fikrinden yararlanılır. Ancak bu açıklama, belirli bir uygulamanın güvenliğini tek başına kanıtlamaz; anahtar boyutu, algoritma uygulaması ve tehdit modeli gibi teknik ayrıntılar da önemlidir. Sonlu cisimler üzerindeki işlemler ise hata düzeltme kodları ve bazı kriptografik yapıların matematiksel temelini oluşturur.