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 topladığımızda (ya da çıkardığımızda) ö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, sonraki 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ı ve 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} \)
\( 7 \bmod{4} = 3 \)
\( 27 \bmod{10} = 7 \)
\( 35 \bmod{5} = 0 \)
\( 0 \bmod{12} = 0 \)
\( 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 \( 0 \le r \lt n \) koşulunu sağlayan eşitliktir.
\( 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 sonucunu verir.
\( 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 ilerlediğimizde \( 10 \) tam tur sonunda tekrar Pazar gününe geliriz. Bu noktadan sonra mod işleminin kalanı olan \( 3 \) basamak daha ilerlediğimizde \( 73 \) sayısının karşılık geldiği \( 3 \) noktasına ulaşırız.
Negatif sayıların mod değerini bulmak için dairesel sayı doğrusunda saat yönünün tersi yönde hareket ettiğimizi düşünebiliriz.
\( (-4) \bmod{7} = 3 \)
\( (-14) \bmod{7} = 0 \)
Mod İşlemi ile İşlemler
İki sayının toplamının/farkının modu, sayıların modlarının toplamına/farkına eşittir. İşlem sonucunun tekrar modunun alınmasının sebebi işlem 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} \)
\( (1436 + 8639) \bmod{10} \) \( = ((1436 \bmod{10}) + (8639 \bmod{10})) \bmod{10} \)
\( = (6 + 9) \bmod{10} \)
\( = 15 \bmod{10} = 5 \)
İSPATI GÖSTER
\( (a + b) \bmod{n} = ((a \bmod{n}) + (b \bmod{n})) \bmod{n} \)
Eşitliğin sol ve sağ taraflarını ayrı ayrı inceleyelim.
\( a \) ve \( b \) sayılarını aşağıdaki şekilde yazabiliriz.
\( 0 \le r_1, r_2 \lt n \) olmak üzere,
\( a = nq_1 + r_1 \)
\( b = nq_2 + r_2 \)
Bu değerleri eşitliğin sol tarafında yerine yazalım.
\( (a + b) \bmod{n} = (nq_1 + r_1 + nq_2 + r_2) \bmod{n}\)
\( = (n(q_1 + q_2) + r_1 + r_2) \bmod{n}\)
Bir sayının modunu alırken sayı içindeki \( n \)'nin katlarını çıkarabiliriz.
\( = (r_1 + r_2) \bmod{n}\)
Eşitliğin sağ tarafını inceleyelim.
\( ((a \bmod{n}) + (b \bmod{n})) \bmod{n} \)
Tanım gereği mod işlemi bir sayının \( n \)'ye bölümünden kalanı verir.
\( = (r_1 + r_2) \bmod{n} \)
Buna göre verilen eşitliğin iki tarafı birbirine eşittir.
\( (r_1 + r_2) \bmod{n} = (r_1 + r_2) \bmod{n} \)
Benzer şekilde; iki sayının çarpımının modu, sayıların modlarının çarpımına eşittir.
\( (a \cdot b) \bmod{n} = ((a \bmod{n}) \) \( \cdot (b \bmod{n})) \bmod{n} \)
\( (1436 \cdot 8639) \bmod{10} \) \( = ((1436 \bmod{10}) \cdot (8639 \bmod{10})) \bmod{10} \)
\( = (6 \cdot 9) \bmod{10} \)
\( = 54 \bmod{10} = 4 \)
İSPATI GÖSTER
\( (a \cdot b) \bmod{n} = ((a \bmod{n}) \cdot (b \bmod{n})) \bmod{n} \)
Eşitliğin sol ve sağ taraflarını ayrı ayrı inceleyelim.
\( a \) ve \( b \) sayılarını aşağıdaki şekilde yazabiliriz.
\( 0 \le r_1, r_2 \lt n \) olmak üzere,
\( a = nq_1 + r_1 \)
\( b = nq_2 + r_2 \)
Bu değerleri eşitliğin sol tarafında yerine yazalım.
\( (a \cdot b) \bmod{n} = ((nq_1 + r_1) \cdot (nq_2 + r_2)) \bmod{n}\)
\( = (n^2q_1q_2 + nq_1r_2 + nq_2r_1 + r_1r_1) \bmod{n}\)
\( = (n(nq_1q_2 + q_1r_2 + q_2r_1) + r_1r_1) \bmod{n}\)
Bir sayının modunu alırken sayı içindeki \( n \)'nin katlarını çıkarabiliriz.
\( = (r_1 \cdot r_1) \bmod{n}\)
Eşitliğin sağ tarafını inceleyelim.
\( ((a \bmod{n}) \cdot (b \bmod{n})) \bmod{n} \)
Tanım gereği mod işlemi bir sayının \( n \)'ye bölümünden kalanı verir.
\( = (r_1 \cdot r_2) \bmod{n} \)
Buna göre verilen eşitliğin iki tarafı birbirine eşittir.
\( (r_1 \cdot r_2) \bmod{n} = (r_1 \cdot r_2) \bmod{n} \)
Benzer bir işlem üs işlemi için de tanımlanabilir.
\( a^b \bmod{n} = (a \bmod{n})^b \bmod{n} \)
\( 442^8 \bmod{10} = (442 \bmod{10})^8 \bmod{10} \)
\( = 2^8 \bmod{10} \)
\( = 256 \bmod{10} = 6 \)
Böler Bağıntısı (\( n \mid a \))
Modüler aritmetiğe giriş bölümünde bahsetmek istediğimiz ikinci konu böler bağıntısıdır.
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 \)
\( n \) sayısı \( a \) sayısını kalansız bölmüyorsa iki sayı arasında "\( \not\mid \)" sembolü kullanılır.
\( 4 \not\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 \)
İSPATI GÖSTER
\( a = k \cdot n \Longrightarrow n \mid a \)
\( 0 = 0 \cdot n \Longrightarrow n \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 \)
İSPATI GÖSTER
\( a = k \cdot n \Longrightarrow n \mid a \)
\( a = a \cdot 1 \Longrightarrow 1 \mid a \)
\( a = (-a) \cdot (-1) \Longrightarrow -1 \mid a \)
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 \)
İSPATI GÖSTER
\( a \ne 0 \) olmak üzere,
\( a = k \cdot n \Longrightarrow n \mid a \)
\( a = 1 \cdot a \Longrightarrow a \mid a \)
\( -a = (-1) \cdot a \Longrightarrow a \mid -a \)
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 \)
İSPATI GÖSTER
\( a \mid b \Longrightarrow b = k_1 \cdot a \)
\( b \mid c \Longrightarrow c = k_2 \cdot b \)
İkinci ifadedeki \( b \) yerine birinci ifadedeki karşılığını yazalım.
\( c = k_2 \cdot k_1 \cdot a \)
\( a \) ile çarpımının sonucu \( c \) olacak şekilde bir \( k_2 \cdot k_1 \) tam sayısı bulduğumuz için, \( a \) sayısı \( c \)'yi böler.
\( a \mid c \)
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) \)
İSPATI GÖSTER
\( a \mid b \Longrightarrow b = k_1 \cdot a \)
\( a \mid c \Longrightarrow c = k_2 \cdot a \)
İki eşitliği taraf tarafa toplayalım.
\( (b + c) = (k_1 + k_2) \cdot a \)
\( a \) ile çarpımının sonucu \( (b + c) \) olacak şekilde bir \( (k_1 + k_2) \) tam sayısı bulduğumuz için, \( a \) sayısı \( (b + c) \)'yi böler.
\( a \mid (b + c) \)
Benzer bir ispat \( (b - c) \) için de verilebilir.