Modüler Aritmetik: Kalan, Denklik ve Modüler Denklemler

Kalanı doğru aralıkta belirleme: bölüm, bölen ve modül

Bir a tam sayısı ve pozitif bir n modülü için bölüm algoritması şu biçimde yazılır: a = n q + r. Burada q bölüm, r ise kalandır ve standart kalan seçimiyle 0 ≤ r < n koşulu sağlanır. Bu koşul, kalanların n'den küçük ve negatif olmayan değerler arasından seçileceğini gösterir.

Örneğin 38 = 5 · 7 + 3 olduğundan 38'in 5'e bölümünden kalan 3'tür. Bu nedenle 38 ≡ 3 (mod 5) yazılır. n = 5 olduğu için mümkün standart kalanlar yalnızca 0, 1, 2, 3, 4 değerleridir.

Negatif sayılarda da aynı aralık kuralı kullanılır. -17 için -17 = 4 · (-5) + 3 yazılabildiğinden -17 ≡ 3 (mod 4) olur. Burada -17'yi 4'e bölerken kullanılan bölüm -5, standart kalan ise 3'tür. Bilgisayar programlarında bazı diller negatif sayılarda farklı kalan gösterimleri üretebildiği için matematik sorularında 0 ≤ r < n koşulunu esas almak gerekir.

Bir sayının modüle göre kalanını bulurken, yalnızca 0 ≤ a < n koşulunu sağlayan negatif olmayan sayılarda sonuç doğrudan sayının kendisidir; genel durumda kalan, 0 ≤ r < n aralığına göre belirlenir. Sayı modülün katıysa kalan 0'dır. Örneğin 42 ≡ 0 (mod 7) ve 12 ≡ 2 (mod 5) ifadeleri bu iki özel durumu gösterir.

Denklik işaretinin iki eşdeğer anlamı

a ≡ b (mod n) ifadesi iki şekilde kontrol edilebilir:

1. a ve b sayıları n ile bölündüğünde aynı kalanı veriyorsa,
2. a - b farkı n'nin tam katıysa.

Formül olarak:

a ≡ b (mod n) ⇔ n | (a - b)

Örneğin 41 ≡ 5 (mod 12) doğrudur; çünkü 41 - 5 = 36 ve 36 = 12 · 3'tür. Aynı sonucu kalanlarla da görebiliriz: 41 sayısının 12'ye bölümünden kalan 5'tir.

Bu gösterimde modül olan n pozitif tam sayı seçilir. Aynı denklik, a = b + kn biçiminde de yazılabilir; burada k herhangi bir tam sayıdır. Buna göre 5 sayısına 12'nin herhangi bir tam katı eklenirse 12 modülüne göre yine 5'e denk bir sayı elde edilir: ..., -19, -7, 5, 17, 29, ....

Denklik ile eşitliği karıştırmamak gerekir. 17 ≡ 5 (mod 12) doğru olsa da 17 = 5 yanlıştır. Modüler ifade, yalnızca seçilen modül açısından aynı davranışı anlatır.

Toplama, çıkarma ve çarpmanın modüle göre sadeleştirilmesi

Aynı modüle göre denk sayılarla toplama, çıkarma ve çarpma yapılabilir. Eğer a ≡ b (mod n) ve c ≡ d (mod n) ise:

a + c ≡ b + d (mod n)

a - c ≡ b - d (mod n)

a · c ≡ b · d (mod n)

Bu özellik, büyük sayıları önce küçük kalanlarla değiştirmeyi mümkün kılar. Örneğin 38 · 27 (mod 5) hesaplanırken 38 ≡ 3 (mod 5) ve 27 ≡ 2 (mod 5) alınır. Böylece 38 · 27 ≡ 3 · 2 = 6 ≡ 1 (mod 5) bulunur.

Üs alma da tekrarlı çarpma nedeniyle bu sadeleştirmeyle uyumludur. Örneğin 23^4 (mod 6) yerine 23 ≡ 5 (mod 6) yazılıp 5^4 incelenebilir. Ancak üs çok büyükse doğrudan açılım yapmak yerine tekrar eden kalan örüntüsü aranmalıdır.

Bölme için aynı rahatlık geçerli değildir. Bir denklikte iki tarafı bir sayıya bölmeden önce o sayının modül içinde çarpma tersi olup olmadığı kontrol edilmelidir. Bir c sayısının n modülüne göre tersi bulunabilmesi için gerekli koşul gcd(c,n)=1 olmasıdır. Örneğin mod 7'de 3'ün tersi vardır; çünkü 3 ile 7 aralarında asaldır. Buna karşılık mod 6'da 2'nin tersi yoktur; çünkü gcd(2,6)=2'dir. Bu nedenle 2x ≡ 2 (mod 6) ifadesinde iki tarafı doğrudan 2'ye bölmek, bütün çözümleri korumayabilir.

Modüler denklemlerde çözüm kümesini yazma

Bir modüler denklemde amaç, bilinmeyenin hangi kalan sınıfına ait olduğunu bulmaktır. Örneğin x ≡ 5 (mod 7) denkleminin tek bir doğal sayı cevabı yoktur. Çözüm kümesi x = 5 + 7k biçimindedir; burada k ∈ Z olur. Standart kalan aralığında çözüm 5 olarak gösterilir, fakat tam sayı çözümleri ..., -9, -2, 5, 12, 19, ... şeklinde devam eder.

Daha genel olarak ax ≡ b (mod n) denklemi için d = gcd(a,n) hesaplanır. Eğer d, b'yi bölmüyorsa denklem çözümsüzdür. Eğer d, b'yi bölüyorsa çözümler vardır; fakat çözümün nasıl yazılacağı, katsayı ve modül sadeleştirildikten sonra belirlenir. Bu nedenle katsayıyı modül içinde ters çevirmeden önce ortak bölen kontrolü yapılmalıdır.

Basit bir durumda, katsayının modüle göre tersi bulunabilir. 3x ≡ 6 (mod 7) denkleminde 3'ün 7'ye göre tersi 5'tir; çünkü 3 · 5 = 15 ≡ 1 (mod 7). İki taraf 5 ile çarpılır: x ≡ 30 ≡ 2 (mod 7). Sonuç, x'in 7'ye bölümünden kalanının 2 olduğu anlamına gelir; yalnızca x = 2 demek tüm tam sayı çözümünü ifade etmez.

Denklik sınıfları neden bir kümeleme oluşturur?

Bir modül seçildiğinde tam sayılar, aynı kalanı veren gruplara ayrılır. Mod 3 için üç sınıf vardır:

[0] = {..., -6, -3, 0, 3, 6, ...}

[1] = {..., -5, -2, 1, 4, 7, ...}

[2] = {..., -4, -1, 2, 5, 8, ...}

Buradaki köşeli gösterim, aynı sınıftaki sayıların 3 modülüne göre denk olduğunu anlatır. Standart temsilciler 0, 1, 2 olduğundan her tam sayı bu üç sınıftan birine girer. Modül n olduğunda standart temsilci sayısı n'dir: 0, 1, ..., n-1.

Bu sınıflandırma, soruda önemli olan bilgiyi ayıklar. Örneğin mod 3 açısından 100 ile 1 arasında fark yoktur; çünkü 100 - 1 = 99, 3'ün katıdır. Ancak bu, 100 ile 1'in her matematiksel işlemde aynı olduğu anlamına gelmez; benzerlik yalnızca mod 3 bağlamında geçerlidir.

Tekrarlayan örüntülerde modül seçme stratejisi

Modüler aritmetikte başarı çoğu zaman doğru modülü seçmeye bağlıdır. Bir olay her n adımda bir tekrarlanıyorsa, adım sayısı n'ye göre incelenir. Saat sorularında 12 veya 24, haftanın günlerinde 7 kullanılır; ancak bunlar olayın nasıl tanımlandığına göre seçilmelidir.

Örneğin bir haftanın günleri için 100 gün sonrasını bulurken 100 sayısını 7'ye böleriz: 100 = 7 · 14 + 2. Bu nedenle başlangıç gününden iki gün ileri gidilir. Başlangıç günü Salı ise iki gün sonrası Perşembe'dir. Burada 100'ün tamamını gün gün saymak yerine yalnızca kalan 2 kullanılmıştır.

Üslü ifadelerde ise modülün yanı sıra kalanların döngüsü izlenir. Bir tabanın ardışık kuvvetleri aynı kalanları tekrar etmeye başladığında, üs döngünün uzunluğuna göre ancak ilgili üsler döngünün başladığı aralıkta bulunuyorsa ve döngü konumları doğru eşleştiriliyorsa azaltılabilir. Taban modülle aralarında asalsa üs, periyot üzerinden daha doğrudan indirgenebilir; aksi durumda kuvvetlerin döngüye girmesinden önceki geçiş dönemi ayrıca dikkate alınmalıdır.