Yazan : Şadi Evren ŞEKER

Sayı teorisinde (Number theory) kullanılan bu terim aşağıdaki formülasyona uyan yapılara verilen isimdir:

ax ≡ b mod p , (p>0 ve a ve b sabit sayılar, x ise değişken)

Yukarıdaki bu tanıma göre bir tabanda (modulo), bir sayının tersini tanımlamak mümkündür. Buna göre

aâ ≡ 1 mod p

, tanımı yapılırsa a ile â birbirinin tersi olarak tanımlanabilir. Burada a sayısı ile p sayısılarının aralarında asal olması gerekmektedir. Şayet bu durum sağlanırsa gerçekte bir â sayısı bulunabilir ve hatta bu sayıdan sadece bir tane vardır.

Bu aşağıdaki şekilde ispatlanabilir:

gcd ( a,p ) = 1 ise (yani a ve p sayılarının ortak böleni 1 ise (bu aralarında asal tanımından gelmektedir) )

sa + tp = 1 tanımı yapılabilir. (Uzatılmış Öklit Bağlantısına göre (Extended Eculidean))

Yukarıdaki tanımda s veya t değerlerinden birisinin negatif olduğunu düşünülmelidir.

Bu bağlantıdan yola çıkarak

sa + tp ≡ 1 mod p

yazılması da doğrudur. Buradaki tp terimi mod p için 0 olduğundan

sa ≡ 1 mod p

yazılabiilr. İşte buradaki s terimi a terimini tersi olan â ‘dır.

Doğrusal ahenk sınıfının bulunması (Solving linear congruence)

Yukarıdaki tanımlardan anlaşıldığı üzere şayet gcd ( a,n ) > 0 ise ve mesela bu sayı d ise , yani gcd (a,n) = d ise x gibi bir sonuç bulunabilir ve bu sonuca göre ra + sn = d yazılabilir. Buradaki x değeri x = rb/d olur.

Yani şayet aralarında asal olmayan iki sayı için doğrusal bir ahenk sınıfı oluşturulmak isteniyorsa bu durumda sistemi çözen sayılar rb/d formülünden bulunabilir.

Örnek üzerinde görelim:

12 x = 20 (mod 28)

sistemini çözen x değerlerini bulmak isteyelim. Öncelikle sistemin 4 çözümü olduğunu biliyoruz çünkü gcd(12,28) = 4′tür ve 20′yi böler. Uzatılmış öklit algoritmasından (-2) * 12 + 1 * 28 = 4 sonucu bulunabilir. Buradaki r = -2 ve s = 1 ‘dir. Yani -2 değeri 12′nin mod 28 deki tersidir. Dolayısıyla x = -2 * 20 /4 = -10 bulunur ve gerçetekn -10 mod 7 = 4′tür. . Bu sayıdan başlanarak oluşturulan ahenk sınıfında ise (her defasında 7 arttırılarak ( 7 sayısı n/d yani 28 / 4 ile bulunur) elde edilen seridir (sequence). dolayısıyla x = { 4,11,18,25} olarak bulunur.

49 views