Modüler Aritmetik

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 6 ile bölümünde kalan 2 dir.

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.