Modüler Aritmetik

Modüler aritmetik, tamsayılarda kullanılan bir hesap yöntemidir. Saatin her on iki saatte bir yinelenmesi gibi modül denen belli bir değere gelindiğinde yeniden sıfıra dönülmesiyle olur.

Birçok eski kültürde insanlar modüler aritmetikte söz etmişlerdir. Çinlilerin kalan teoremi buna örnek verilebilir. Çağdaş gösterimi ile tanımını Carl Friedrich Gauss açıklamıştır.

Çinlilerin kalan teoremi, "3'e bölündüğünde 2, 5'e bölündüğünde 3, 7'ye bölündüğünde 4 kalanını veren sayıyı bulun" tipinden problemleri çözmek için kullanılan teorem. buna göre: 3'e bölündüğünde 2 kalanını veren sayılar 3.k+2 şeklindedir. (2, 5, 8, ...) 5'e bölündüğünde 3 kalanını veren sayılar 5.l+3 şeklindedir. (3, 8, 13, ...) bu durumda sayımız 15m+8 şeklindedir. (8, 23, 38, 53, ...) 7'ye bölündüğünde 4 kalanını veren sayılar 7.n+4 şeklindedir. (4, 11, 18, ..., 46, 53, ...) bu durumda da sayımız 105.p+53 şeklindedir.

n₁, n₂, …, n_k pozitif, çiftli aralarında asal Tamsayı olsun. Bu durumda, Verilen herhangi a₁,a₂, …, a_k,tamsayıları için bir x tamsayısı vardır ki sistemin eşzamanlı uygun bir çözümüdür.

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

Z = {..., -3, -2, -1, 0, 1, 2, 3, ... } kümesinde tanımlanan

β = {(x,y) : m | (x - y), m Î Z+ - {1} ve x, y Î Z}

bağınıtısı denklik bağıntısıdır. β, denklik bağıntısı olduğundan, ∀ (x, y) Î β için x ≡ y (mod m) dir.

Diğer bir ifadeyle, x in m ye bölümünden kalan y ise modül m ye göre x, y ye denktir denir ve x ≡ y (mod m)  şeklinde gösterilir.

Örnek:

25 ≡ 4 (mod 7) ğ 25 in 7 ile bölümünde kalan 4 tür.

35 ≡ 8 (mod 9) ğ 35 in 9 ile bölümünde kalan 8 dir.

38 ≡ 2 (mod 6) ğ 38 in 2 ile bölümünde kalan 6 dır.

Kural:

x ≡ y (mod m) ve z ≡ t (mod m) olsun.

• x + z ≡ y + t (mod m) 
• x - z ≡ y - t (mod m) 
• x.z ≡ y.z (mod m) 
• k.x ≡ k.y (mod m) 
• xn ≡ yn (mod m) , n Î

Örnek:

257 sayısının 5 ile bölümünden kalanı bulalım.

Çözüm:

257 sayısının 5 ile bölümünden kalan x ise 257 ≡ x (mod 5) tir.

257 ≡ x (mod 5)

21 ≡ 2 (mod 5)

22 ≡ 4 (mod 5)

23 ≡ 3 (mod 5)

24 ≡ 1 (mod 5)  *

2 nin 4. kuvveti 1 olduğuna göre, 4 ün katı olan kuvvetlerinde 1 dir.Bunun için üssün 4 e bölümünden kalan bulunur. Buradan sonuca gidilir.

57 = 4.14 + 1 olduğuna göre sonuç 21 dir.

257 ≡ (24)14 21 (mod 5)

       ≡ 113.21 (mod 5)

       ≡ 1.21 (mod 5) 

       ≡ 2 (mod 5) dir.

Örnek:

334 sayısının birler basamağının kaç olduğunu bulalım.

Çözüm:

Bir sayının 10 a bölümünden kalan rakam, o sayının birler basamağındaki rakamdır. Buna göre ,

334 ≡ x (mod 10) ise x i bulmalıyız.

  31 ≡ 3 (mod 10)

  32 ≡ 9 (mod 10)

  33 ≡ 7 (mod 10)

  34 ≡ 1 (mod 10)  *

 O halde,

334 ≡ (34)8.32 (mod 10)

       ≡ 18.32 (mod 10)

       ≡ 32 (mod 10)

       ≡ 9 (mod 10) bulunur.

x = 9 dur.

Buna göre, 334 sayısının birler basamağındaki rakam 9 dur.

Kural:

x, m nin tam katı olmayan pozitif bir tam sayı ve m asal sayı ise

xm-1 ≡ 1 (mod m) dir.

 Örnek:

  24 ≡ 1 (mod 5)

  36 ≡ 1 (mod 7)

510 ≡ 1 (mod 11)

  88 ≡ 1 (mod 9)

Görüldüğü gibi kural ciddi kolaylık sağlamaktadır.

Örnek:

31998 ≡ x (mod 5)

olduğuna göre, x değerini bulalım.

Çözüm:

Kural gereği

      34 ≡ 1 (mod 5) dir. Buna göre,

31998 ≡ 31996.32 (mod 5)

            ≡ (34)499.32 (mod 5)

            ≡ 1499.4 (mod 5)

            ≡ 1.4 (mod 5)

            ≡ 4 (mod 5)

Buradan x = 4 olur.