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.