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) 
• xⁿ ≡ yⁿ (mod m) , n Î

Örnek:

2⁵⁷ sayısının 5 ile bölümünden kalanı bulalım.

Çözüm:

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

2⁵⁷ ≡ x (mod 5)

2¹ ≡ 2 (mod 5)

2² ≡ 4 (mod 5)

2³ ≡ 3 (mod 5)

2⁴ ≡ 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ç 2¹ dir.

2⁵⁷ ≡ (2⁴)¹⁴ 2¹ (mod 5)

       ≡ 1¹³.2¹ (mod 5)

       ≡ 1.2¹ (mod 5) 

       ≡ 2 (mod 5) dir.

Örnek:

3³⁴ 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 ,

3³⁴ ≡ x (mod 10) ise x i bulmalıyız.

  3¹ ≡ 3 (mod 10)

  3² ≡ 9 (mod 10)

  3³ ≡ 7 (mod 10)

  3⁴ ≡ 1 (mod 10)  *

 O halde,

3³⁴ ≡ (3⁴)⁸.3² (mod 10)

       ≡ 1⁸.3² (mod 10)

       ≡ 3² (mod 10)

       ≡ 9 (mod 10) bulunur.

x = 9 dur.

Buna göre, 3³⁴ 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

x^m-1 ≡ 1 (mod m) dir.

 Örnek:

  2⁴ ≡ 1 (mod 5)

  3⁶ ≡ 1 (mod 7)

5¹⁰ ≡ 1 (mod 11)

  8⁸ ≡ 1 (mod 9)

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

Örnek:

3¹⁹⁹⁸ ≡ x (mod 5)

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

Çözüm:

Kural gereği

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

3¹⁹⁹⁸ ≡ 3¹⁹⁹⁶.3² (mod 5)

            ≡ (3⁴)⁴⁹⁹.3² (mod 5)

            ≡ 1⁴⁹⁹.4 (mod 5)

            ≡ 1.4 (mod 5)

            ≡ 4 (mod 5)

Buradan x = 4 olur.