Modüler Aritmetiğe Giriş
Sayılar konusunda gördüğümüz reel sayılar ve sayı doğrusu ilişkisi hakkında birkaç bilgiyi hatırlayalım:
- Pozitif ya da negatif her reel sayı farklı bir büyüklük ifade eder ve sayı doğrusu üzerinde farklı bir noktaya karşılık gelir.
- Bir sayıyı sıfırdan farklı bir sayı ile toplarsak (ya da çıkarırsak), öncekinden farklı bir sayı ve bu sayının karşılık geldiği yeni bir nokta elde ederiz.
- İki sayı sayı doğrusu üzerinde aynı noktaya karşılık geliyorsa, bu sayılar sadece eşit olabilir.
Standart aritmetik diyebileceğimiz sistemin parçası olan bu prensipler, matematikte ve günlük hayatta karşımıza çıkan problemlerin çoğu için geçerlidir. Ancak sayıların ve olayların belirli bir periyotta kendini tekrarladığı durumlar daha farklı bir aritmetik sistemini gerekli kılmaktadır. Bu tip durumlara aşağıdaki gibi birkaç örnek verebiliriz:
- Günün saatleri: Saat 20'ye 24 saat eklersek, 44 değil yine saat 20'yi elde ederiz.
- Haftanın günleri: Bir pazartesi gününden 100 gün sonrasının 101. gün olmasından ziyade, bir çarşamba günü olduğunu bilmemiz çoğu zaman daha önemlidir.
- Yılın ayları: Yılın 11. ayından 9 ay sonrası 20. ay değil, yılın 8. ayıdır.
Bu tip tekrarlayan sayılarla ilgilenen ve modüler aritmetik adı verilen sistemde, sayıların doğrusal değil dairesel bir sayı doğrusu üzerinde bulunduğunu düşünebiliriz. Haftanın günleri örneğini kullanarak, tüm tam sayıları tekrarlı bir şekilde haftanın günlerine karşılık gelecek şekilde sayı doğrusu üzerinde işaretlediğimizi varsayalım.
Bu sayı doğrusunu haftanın aynı günleri üst üste gelecek şekilde "yuvarladığımızı" düşünürsek, aşağıdaki gibi dairesel bir sayı doğrusu elde ederiz.
Bu dairesel sayı doğrusu üzerinde, daha önce farklı birer sayısal büyüklüğe ve noktaya karşılık gelen -14, -7, 0, 7, 14 sayılarının aynı noktaya (ve haftanın aynı gününe) karşılık geldiğini görmekteyiz. Dolayısıyla, normal aritmetik sisteminde birbirinden farklı olan sayıların bu yeni sistemde çakıştığını ve aralarında bir (önümüzdeki bölümde isimlendireceğimiz şekliyle) denklik ilişkisinin oluştuğunu söyleyebiliriz.
Mod İşlemi (\( a \bmod{n} \))
Dört temel aritmetik işlem olan toplama, çıkarma, çarpma ve bölme gibi bir işlem olan mod işlemi, bir \( a \) tam sayısının \( n \) tam sayısına bölümünden kalanı verir ve "\( a \bmod{n} \)" şeklinde ifade edilir.
\( a, k, n, r \in \mathbb{Z}, \quad n \gt 1, \quad 0 \le r \lt n \) olmak üzere,
\( a = k \cdot n + r \)
eşitliğini sağlayan \( r \) değeri, \( a \)'nın \( n \)'ye bölümünden kalandır ve aşağıdaki şekilde ifade edilir.
\( r = a \bmod{n} \)
\( a \) ve \( n \) sayıları arasında yukarıdakine benzer şekilde sonsuz sayıda eşitlik yazabiliriz, ancak bize mod işleminin sonucunu veren bu eşitliklerden sadece biridir ve \( r \) kalanının \( [0, n) \) aralığında kaldığı eşitliktir. Bu ayrım aşağıda \( 73 \)'ün \( 7 \)'ye bölüm örneği üzerinde gösterilmiştir.
\( 73 = 8 \cdot 7 + 17 \)
\( 73 = 9 \cdot 7 + 10 \)
\( \textcolor{red}{73 = 10 \cdot 7 + 3} \)
\( 73 = 11 \cdot 7 - 4 \)
\( 73 = 12 \cdot 7 - 11 \)
Yukarıdaki beş eşitlik de matematiksel açıdan doğrudur, ancak sadece ortadaki bize mod işleminin sonucu olan kalan değerini vermektedir.
\( 73 \bmod{7} = 3 \)
Elde ettiğimiz \( 7 \) modülündeki bu 3 kalanını şu şekilde de yorumlayabiliriz: Yukarıdaki dairesel sayı doğrusu üzerinde \( 0 \) noktasından (Pazar günü) başlayarak saat yönünde \( 73 \) basamak ilerlersek, \( 10 \) tam tur sonunda tekrar Pazar gününe geliriz, bu noktadan sonra mod işleminin kalanı olan \( 3 \) basamak daha ilerlersek \( 73 \) sayısının karşılık geldiği \( 3 \) noktasına ulaşırız.
\( 7 \bmod{4} = 3 \)
\( 27 \bmod{10} = 7 \)
\( 35 \bmod{5} = 0 \)
\( (-4) \bmod{7} = 3 \)
Son örnekteki negatif sayının mod işlem değerini yorumlamak için yine yukarıdaki dairesel sayı doğrusuna dönelim: Sıfır noktasından başlayarak saat yönünün tersi (negatif) yönde \( 4 \) basamak ilerlersek, \( 3 \) noktasına ulaşırız.
Mod İşlemi ile İşlemler
İki sayı arasındaki toplama, çıkarma ve çarpma işlemlerinin \( n \) modülünde sonucu sayıların aynı modülde modlarının işlem sonucuna eşittir. Her üç işlemde de ikinci kez mod almamızın sebebi birinci mod işleminin sonucunun işlemin modülünden büyük olabilmesidir.
\( (a + b) \bmod{n} = ((a \bmod{n}) \) \( + (b \bmod{n})) \bmod{n} \)
\( (a - b) \bmod{n} = ((a \bmod{n}) \) \( - (b \bmod{n})) \bmod{n} \)
\( (ab) \bmod{n} = ((a \bmod{n}) \) \( \cdot (b \bmod{n})) \bmod{n} \)
\( (10436 + 85639) \bmod{10} \) \( = ((10436 \bmod{10}) \) \( + (85639 \bmod{10})) \bmod{10} \) \( = (6 + 9) \bmod{10} \) \( = 15 \bmod{10} = 5 \)
\( (10436 \cdot 85639) \bmod{10} \) \( = ((10436 \bmod{10}) \) \( \cdot (85639 \bmod{10})) \bmod{10} \) \( = (6 \cdot 9) \bmod{10} \) \( = 54 \bmod{10} = 4 \)
Benzer bir işlemi üs işlemi için de tanımlayabiliriz.
\( a^b \bmod{n} = (a \bmod{n})^b \bmod{n} \)
\( 12^8 \bmod{10} = (12 \bmod{10})^8 \bmod{10} \) \( = 2^8 \bmod{10} \) \( = 6 \)
Böler Önermesi (\( n \mid a \))
Modüler aritmetiğe giriş bölümünde bahsetmek istediğimiz ikinci konu böler önermesidir.
Bir \( a \) tam sayısının sıfırdan farklı bir \( n \) tam sayısına bölümünden kalan sıfırsa, \( n \) sayısı \( a \) sayısının bir bölenidir (ve \( a \) sayısı \( n \) sayısının bir katıdır).
\( n, a \in \mathbb{Z}, \quad n \ne 0 \) olmak üzere,
\( a \bmod{n} = 0 \Longrightarrow n \mid a \)
\( 28 \bmod{7} = 0 \Longrightarrow 7 \mid 28 \)
Bir diğer tanıma göre, sıfırdan farklı bir \( n \) tam sayısı ile çarpımının sonucu bir \( a \) tam sayısı olacak şekilde bir \( k \) tam sayısı bulabiliyorsak, \( n \) sayısı \( a \) sayısının bir bölenidir (ve \( a \) sayısı \( n \) sayısının bir katıdır).
\( n, a, k \in \mathbb{Z}, \quad n \ne 0 \) olmak üzere,
\( a = k \cdot n \Longrightarrow n \mid a \)
\( 28 = 4 \cdot 7 \Longrightarrow 7 \mid 28 \)
Yukarıdaki gösterimde "\( n \mid a \)" ifadesi \( n \) sayısının \( a \) sayısını kalansız böldüğünü gösterir ve "\( n \), \( a \)'yı böler" şeklinde okunur. Bu ifadede kullanılan "\( \mid \)" işareti bölmede kullanılan "/" işaretinden farklıdır.
Bir sayının pozitif ve negatif tüm bölenleri için "böler" ifadesini kullanabiliriz. Aşağıdakilerin her biri doğruluk değeri "1" olan birer mantıksal önermedir.
\( 6 \)'nın bölenleri \( = \{ -6, -3, -2, -1, 1, 2, 3, 6 \} \)
\( 6 \mid 6 \), \( \quad -6 \mid 6 \)
\( 3 \mid 6 \), \( \quad -3 \mid 6 \)
\( 2 \mid 6 \), \( \quad -2 \mid 6 \)
\( 1 \mid 6 \), \( \quad -1 \mid 6 \)
Bölme Kuralları
Yukarıdaki formülü \( a = 0 \) olacak şekilde sıfırdan farklı tüm \( n \) tam sayıları için yazabileceğimiz için, sıfırdan farklı tüm tam sayılar sıfırı böler.
\( n \in \mathbb{Z}, \quad n \ne 0 \) olmak üzere,
\( n \mid 0 \)
\( 7 \mid 0, \quad -3 \mid 0 \)
Yukarıdaki formülü \( n = 1 \) ya da \( n = -1 \) olacak şekilde tüm tam sayılar için yazabileceğimiz için, \( 1 \) ve \( -1 \) sayıları sıfır dahil tüm tam sayıları böler.
\( a \in \mathbb{Z} \) olmak üzere,
\( 1 \mid a \)
\( -1 \mid a \)
\( 1 \mid 5, \quad 1 \mid -8, \quad 1 \mid 0 \)
\( -1 \mid 5, \quad -1 \mid -8, \quad -1 \mid 0 \)
Yukarıdaki formülü \( n = a \) ya da \( n = -a \) olacak şekilde sıfırdan farklı tüm tam sayılar için yazabileceğimiz için, sıfırdan farklı tüm tam sayılar kendisini ve negatifini böler.
\( a \in \mathbb{Z}, \quad a \ne 0 \) olmak üzere,
\( a \mid a \)
\( a \mid -a \)
\( 10 \mid 10, \quad 10 \mid -10 \)
\( -10 \mid 10, \quad -10 \mid -10 \)
Bir \( a \) sayısı \( b \) sayısını, \( b \) sayısı da \( c \) sayısını bölüyorsa, \( a \) sayısı \( c \) sayısını böler.
\( (a \mid b) \) ve \( (b \mid c) \) \( \Longrightarrow a \mid c \)
\( (3 \mid 12) \) ve \( (12 \mid 72) \) \( \Longrightarrow 3 \mid 72 \)
Bir \( a \) sayısı \( b \) sayısını, \( b \) sayısı da \( a \) sayısını bölüyorsa, bu sayılar ya eşittir ya da birbirinin ters işaretlisidir.
\( (a \mid b) \) ve \( (b \mid a) \) \( \Longrightarrow (a = b) \) ya da \( (a = -b) \)
Bir \( a \) sayısı \( b \) ve \( c \) sayılarını bölüyorsa, \( (b + c) \) ve \( (b - c) \) sayılarını da böler.
\( (a \mid b) \) ve \( (a \mid c) \) \( \Longrightarrow a \mid (b + c) \)
\( (a \mid b) \) ve \( (a \mid c) \) \( \Longrightarrow a \mid (b - c) \)
\( (7 \mid 63) \) ve \( (7 \mid 14) \) \( \Longrightarrow 7 \mid (63 + 14) \)
\( (6 \mid 72) \) ve \( (6 \mid 24) \) \( \Longrightarrow 6 \mid (72 - 24) \)