12 Kongrüans Kavramı
Bölme algoritması her tam sayıya bir kalan iliştiriyordu. Şimdi bu fikri bir adım öteye taşıyacağız: aynı kalanı veren sayıları birbirinden ayırt etmeyeceğiz. Ortaya çıkan dil — kongrüans dili — sayılar teorisinin en güçlü hesap aracıdır; büyük sayılarla yapılan bölünebilme hesaplarını çoğu zaman birkaç satıra indirir.
12.1 Tanım
Tanım 12.1 (Kongrüans) \(n\) sabit bir pozitif tam sayı ve \(a, b \in \mathbb{Z}\) olsun. Eğer \(n\) sayısı \(a - b\) farkını bölerse, yani
\[a - b = kn\]
olacak biçimde bir \(k\) tam sayısı varsa, “\(a\) ve \(b\) tam sayıları modülo \(n\) kongrüdür” denir ve
\[a \equiv b \pmod{n}\]
yazılır. Aksi hâlde \(a \not\equiv b \pmod{n}\) yazılır. \(n\) sayısına modül denir.
Örnek 12.1 (İlk Örnekler) \(n = 7\) olsun.
\[20 \equiv 6 \pmod 7, \qquad -22 \equiv 13 \pmod 7, \qquad -108 \equiv -101 \pmod 7\]
çünkü sırasıyla \(20 - 6 = 14\), \(-22 - 13 = -35\) ve \(-108 - (-101) = -7\) sayılarının hepsi \(7\) ile bölünür.
Buna karşılık
\[18 \not\equiv 5 \pmod 7\]
çünkü \(18 - 5 = 13\) sayısı \(7\) ile bölünmez.
Herhangi iki tam sayı daima modülo \(1\) kongrüdür; çünkü \(1\) her farkı böler. Bu yüzden \(n = 1\) hiçbir bilgi taşımaz ve bundan sonra \(n > 1\) olduğunu varsayacağız.
12.2 Temel Özellikler
Kongrüans bağıntısı, eşitliğe çok benzer biçimde davranır: yansıma, simetri ve geçişme özelliklerini taşır; ayrıca iki tarafı toplayabilir, çıkarabilir, çarpabilir ve kuvvet alabiliriz. Aşağıdaki teorem bu benzerliğin sınırlarını çizer.
Teorem 12.1 (Kongrüansın Temel Özellikleri) \(1 < n\) sabit bir tam sayı olmak üzere, her \(a, b, c, d\) tam sayısı için aşağıdakiler geçerlidir.
(a) \(a \equiv a \pmod n\).
(b) \(a \equiv b \pmod n\) ise \(b \equiv a \pmod n\).
(c) \(a \equiv b \pmod n\) ve \(b \equiv c \pmod n\) ise \(a \equiv c \pmod n\).
(d) \(a \equiv b \pmod n\) ve \(c \equiv d \pmod n\) ise
\[a + c \equiv b + d \pmod n \qquad \text{ve} \qquad ac \equiv bd \pmod n\]
(e) \(a \equiv b \pmod n\) ise \(a + c \equiv b + c \pmod n\) ve \(ac \equiv bc \pmod n\).
(f) \(a \equiv b \pmod n\) ise her \(k\) pozitif tam sayısı için \(a^{k} \equiv b^{k} \pmod n\).
İspat
(a) \(a - a = 0 = n \cdot 0\) olduğundan \(n \mid a - a\)’dır.
(b) \(n \mid a - b\) olsun. Teorem 3.1 (13) gereği \(n \mid -(a-b) = b - a\)’dır.
(c) \(n \mid a - b\) ve \(n \mid b - c\) olsun. Teorem 3.1 (7) gereği \(n\) toplamı da böler:
\[n \ \mid \ (a - b) + (b - c) = a - c\]
(d) \(n \mid a - b\) ve \(n \mid c - d\) olsun.
Toplam için:
\[(a + c) - (b + d) = (a - b) + (c - d)\]
Sağ taraftaki her iki terim \(n\) ile bölündüğünden toplamları da bölünür.
Çarpım için: İfadeye \(bc\) terimini ekleyip çıkararak parçalayalım:
\[ \begin{aligned} ac - bd &= ac - bc + bc - bd \\ &= c(a - b) + b(c - d) \end{aligned} \]
\(n \mid a - b\) olduğundan \(n \mid c(a-b)\); \(n \mid c - d\) olduğundan \(n \mid b(c-d)\)’dir. Teorem 3.1 (7) gereği \(n\) toplamı, yani \(ac - bd\)’yi böler.
(e) (d) özelliğinde \(c \equiv c \pmod n\) alınırsa (bu (a) gereği doğrudur) istenen elde edilir.
(f) \(k\) üzerinden tümevarım yapalım. \(k = 1\) için iddia hipotezdir. \(a^k \equiv b^k \pmod n\) olduğunu varsayalım. Elimizde
\[a^{k} \equiv b^{k} \pmod n \qquad \text{ve} \qquad a \equiv b \pmod n\]
vardır; (d) özelliğinin çarpım kısmı gereği
\[a^{k} \cdot a \equiv b^{k} \cdot b \pmod n \qquad \text{yani} \qquad a^{k+1} \equiv b^{k+1} \pmod n\]
Tümevarım gereği iddia her \(k\) için doğrudur.
\(\blacksquare\)
Listede toplama, çıkarma, çarpma ve kuvvet alma var — ama bölme yok. Bu bir unutkanlık değildir: kongrüanslarda sadeleştirme her zaman serbest değildir. Örneğin
\[2 \cdot 3 \equiv 2 \cdot 6 \pmod 6\]
doğrudur (her iki taraf da \(\equiv 0\)), ama \(2\)’yi sadeleştirip \(3 \equiv 6 \pmod 6\) yazamayız; bu yanlıştır.
Sadeleştirmenin hangi koşulda serbest olduğunu birazdan göreceğiz.
12.3 Aynı Kalanı Verme Ölçütü
Kongrüansın sezgisel anlamı, tanımdaki fark koşulundan daha açıktır.
Teorem 12.2 (Kongrüans, Aynı Kalanı Vermektir) \(1 < n\) sabit bir tam sayı ve \(a, b \in \mathbb{Z}\) olsun. \(a \equiv b \pmod n\) olabilmesi için gerek ve yeter koşul, \(a\) ile \(b\)’nin \(n\) ile bölündüklerinde aynı kalanı vermesidir.
İspat
Bölme algoritmasına göre
\[a = n q_1 + r_1, \qquad b = n q_2 + r_2, \qquad 0 \leq r_1, r_2 < n\]
yazalım.
(\(\Leftarrow\)) \(r_1 = r_2\) olsun. Farkı hesaplayalım:
\[a - b = n q_1 + r_1 - n q_2 - r_2 = n\left( q_1 - q_2 \right)\]
O hâlde \(n \mid a - b\), yani \(a \equiv b \pmod n\)’dir.
(\(\Rightarrow\)) \(a \equiv b \pmod n\) olsun; \(n \mid a - b\)’dir. Farkı yukarıdaki gibi yazalım:
\[a - b = n\left( q_1 - q_2 \right) + \left( r_1 - r_2 \right)\]
\(n\) sayısı hem \(a - b\)’yi hem de \(n(q_1 - q_2)\)’yi böldüğünden, farklarını da böler:
\[n \ \mid \ r_1 - r_2\]
Öte yandan \(0 \leq r_1, r_2 < n\) olduğundan
\[-n < r_1 - r_2 < n \qquad \text{yani} \qquad |r_1 - r_2| < n\]
\(n\) ile bölünen ve mutlak değeri \(n\)’den küçük olan tek tam sayı \(0\)’dır. O hâlde \(r_1 = r_2\)’dir.
\(\blacksquare\)
Ölçüt, kongrüans hesabını “kalan hesabına” çevirir. Bir sayının \(n\) ile bölümünden kalanı bulmak istiyorsak, o sayıyı modülo \(n\) mümkün olduğunca küçük bir sayıya indirgeriz; elde ettiğimiz \(0 \leq r < n\) değeri doğrudan aranan kalandır.
Aşağıdaki örnekler bu stratejinin uygulamalarıdır.
12.4 Büyük Kuvvetlerle Hesap
Örnek 12.2 (\(3^{10}\) Sayısının \(41\) ile Bölümünden Kalan) a) \(41\) sayısının \(3^{10} - 9\) sayısını böldüğünü gösteriniz.
b) \(3^{10}\) sayısının \(41\) ile bölümünden elde edilen kalanı bulunuz.
Çözüm
a) Kuvveti doğrudan hesaplamak yerine küçük bir kuvvetten başlayalım:
\[3^4 = 81 = 2 \cdot 41 - 1\]
O hâlde
\[3^4 \equiv -1 \pmod{41}\]
Şimdi Teorem 12.1 (f) gereği her iki tarafın karesini alalım:
\[3^{8} \equiv (-1)^2 = 1 \pmod{41}\]
Son olarak \(3^{10} = 3^8 \cdot 3^2\) olduğundan, (d) özelliğiyle çarpalım:
\[3^{10} \equiv 1 \cdot 3^2 = 9 \pmod{41}\]
Bu, tanım gereği \(41 \mid 3^{10} - 9\) demektir.
b) \(3^{10} \equiv 9 \pmod{41}\) bulduk ve \(0 \leq 9 < 41\)’dir. Teorem 12.2 gereği aranan kalan \(9\)’dur.
\(\blacksquare\)
Yukarıdaki hesabın püf noktası, \(3^4 \equiv -1\) eşitliğini fark etmekti. Kuvvet hesaplarında modülo \(n\)’de \(1\) veya \(-1\) değerini veren bir kuvvet bulmak, geri kalan her şeyi çözer: o kuvvetten sonrası periyodik olarak tekrarlanır.
Bu yüzden strateji şudur: \(a^1, a^2, a^3, \dots\) değerlerini modülo \(n\) hesaplayın ve ilk kez \(\pm 1\) göründüğü yerde durun.
Örnek 12.3 (\(3^{405}\) Sayısının \(17\) ile Bölümünden Kalan) \(3^{405}\) sayısının \(17\) ile bölümünden elde edilen kalanı bulunuz.
Çözüm
Önce \(3\)’ün küçük kuvvetlerini modülo \(17\) hesaplayalım:
\[3^1 \equiv 3, \qquad 3^2 \equiv 9, \qquad 3^3 \equiv 27 \equiv 10, \qquad 3^4 \equiv 30 \equiv 13 \pmod{17}\]
Devam edelim:
\[3^{8} \equiv 13^2 = 169 = 9 \cdot 17 + 16 \equiv 16 \equiv -1 \pmod{17}\]
\(-1\)’i bulduk. Karesini alalım:
\[3^{16} \equiv (-1)^2 = 1 \pmod{17}\]
Şimdi üssü \(16\)’ya bölelim:
\[405 = 16 \cdot 25 + 5\]
Buradan
\[3^{405} = \left( 3^{16} \right)^{25} \cdot 3^{5} \equiv 1^{25} \cdot 3^{5} = 3^{5} \pmod{17}\]
Son olarak \(3^5 = 243 = 14 \cdot 17 + 5\) olduğundan
\[3^{405} \equiv 5 \pmod{17}\]
\(0 \leq 5 < 17\) olduğundan aranan kalan \(5\)’tir.
\(\blacksquare\)
Örnek 12.4 (Faktöriyellerin Toplamı) \[1! + 2! + 3! + \cdots + 99! + 100!\]
sayısının \(240\) ile bölümünden elde edilen kalanı bulunuz.
Çözüm
Anahtar gözlem, toplamdaki terimlerin büyük çoğunluğunun modülo \(240\)’ta yok olmasıdır.
\[240 = 2^4 \cdot 3 \cdot 5\]
Şimdi \(6!\) sayısına bakalım:
\[6! = 720 = 3 \cdot 240\]
Demek ki \(240 \mid 6!\)’dir. Her \(n \geq 6\) için \(6! \mid n!\) olduğundan (çünkü \(n! = 6! \cdot 7 \cdot 8 \cdots n\)), geçişme gereği
\[240 \mid n! \qquad \text{yani} \qquad n! \equiv 0 \pmod{240} \qquad (n \geq 6)\]
O hâlde toplamdaki \(6!\)’den \(100!\)’e kadar olan bütün terimler modülo \(240\)’ta sıfırdır. Geriye ilk beş terim kalır:
\[ \begin{aligned} 1! + 2! + \cdots + 100! &\equiv 1! + 2! + 3! + 4! + 5! \pmod{240} \\ &= 1 + 2 + 6 + 24 + 120 \\ &= 153 \end{aligned} \]
\(0 \leq 153 < 240\) olduğundan aranan kalan \(153\)’tür.
\(\blacksquare\)
Örnek 12.5 (Tam Karelerin Son Rakamı) Her \(n\) tam sayısı için \(n^2\) sayısının birler basamağındaki rakamın yalnızca
\[0, \quad 1, \quad 4, \quad 5, \quad 6, \quad 9\]
rakamlarından biri olabileceğini gösteriniz.
Çözüm
Bir sayının birler basamağı, o sayının \(10\) ile bölümünden kalandır. O hâlde \(n^2\) sayısını modülo \(10\) incelemeliyiz.
\(n \equiv r \pmod{10}\), \(r \in \{0, 1, \dots, 9\}\) olsun. Teorem 12.1 (f) gereği
\[n^2 \equiv r^2 \pmod{10}\]
Şimdi \(r^2\) değerlerini modülo \(10\) hesaplayalım:
| \(r\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(r^2\) | \(0\) | \(1\) | \(4\) | \(9\) | \(16\) | \(25\) | \(36\) | \(49\) | \(64\) | \(81\) |
| \(r^2 \bmod 10\) | \(0\) | \(1\) | \(4\) | \(9\) | \(6\) | \(5\) | \(6\) | \(9\) | \(4\) | \(1\) |
Son satırda görünen değerler kümesi
\[\{0, 1, 4, 5, 6, 9\}\]
olduğundan, başka hiçbir rakam bir tam karenin son basamağı olamaz.
\(\blacksquare\)
Bu tablo hızlı bir eleme aracıdır: son rakamı \(2, 3, 7\) veya \(8\) olan hiçbir sayı tam kare değildir. Örneğin \(123456787\) sayısının tam kare olup olmadığını anlamak için karekök almaya gerek yoktur; son rakamı \(7\) olduğundan tam kare olamaz.
12.5 Sadeleştirme Kuralı
Şimdi kongrüanslarda bölmenin ne zaman serbest olduğunu belirleyelim.
Teorem 12.3 (Sadeleştirme Kuralı) \(a, b, c, n \in \mathbb{Z}\), \(1 < n\) ve \(d = \gcd(c, n)\) olsun. Eğer
\[ca \equiv cb \pmod n\]
ise
\[a \equiv b \pmod{\frac{n}{d}}\]
İspat
\(ca \equiv cb \pmod n\) olsun; yani \(n \mid c(a-b)\)’dir. O hâlde
\[c(a - b) = n k\]
olacak biçimde bir \(k\) tam sayısı vardır.
\(d = \gcd(c, n)\) olduğundan
\[c = d c', \qquad n = d n'\]
yazalım; Sonuç 5.1 gereği \(\gcd(c', n') = 1\)’dir. Bunları yerine koyalım:
\[d c' (a - b) = d n' k\]
\(d \neq 0\) olduğundan sadeleştirebiliriz:
\[c'(a - b) = n' k\]
Bu eşitlik \(n' \mid c'(a-b)\) olduğunu söyler. \(\gcd(n', c') = 1\) olduğundan Teorem 5.1 gereği
\[n' \mid a - b\]
bulunur; yani
\[a \equiv b \pmod{n'}, \qquad n' = \frac{n}{d}\]
\(\blacksquare\)
Sonuç 12.1 (Aralarında Asal Çarpanla Sadeleştirme) \(a, b, c, n \in \mathbb{Z}\) ve \(1 < n\) olsun.
1. Eğer \(ca \equiv cb \pmod n\) ve \(\gcd(c, n) = 1\) ise \(a \equiv b \pmod n\)’dir.
2. \(p\) bir asal sayı olmak üzere, eğer \(ca \equiv cb \pmod p\) ve \(p \nmid c\) ise \(a \equiv b \pmod p\)’dir.
Birincisi Teorem 12.3’nin \(d = 1\) hâlidir. İkincisi ise Önerme 9.1 gereği \(p \nmid c\) olduğunda \(\gcd(c,p) = 1\) olmasından çıkar.
Bölümün başındaki karşı örneğe dönelim:
\[2 \cdot 3 \equiv 2 \cdot 6 \pmod 6\]
Burada \(\gcd(2, 6) = 2\)’dir. Teorem 12.3 yalnızca
\[3 \equiv 6 \pmod{3}\]
sonucunu verir — ki bu doğrudur. Modülü küçültmeden sadeleştirmek yanlış olurdu.
12.6 Modülle EBOB Değişmez
Önerme 12.1 (Kongrü Sayıların Modülle EBOB’u) \(a, b, n \in \mathbb{Z}\) ve \(1 < n\) olsun. Eğer \(a \equiv b \pmod n\) ise
\[\gcd(n, a) = \gcd(n, b)\]
Gerçekten de \(a \equiv b \pmod n\) ise \(a = b + nk\) olacak biçimde bir \(k\) tam sayısı vardır. Önerme 6.1 gereği
\[\gcd(n, a) = \gcd(n,\ b + nk) = \gcd(n, b)\]
Bu küçük önerme ileride birkaç yerde işimizi görecek: bir kalan sınıfının modülle aralarında asal olup olmadığı, sınıftan hangi temsilciyi seçtiğimize bağlı değildir. Euler’in \(\phi\) fonksiyonunu kalan sınıfları üzerinden tanımlarken bu bilgi vazgeçilmez olacak.
12.7 Polinomlarla Kongrüans
Teorem 12.4 (Polinomlar Kongrüansı Korur) \(0 < m \in \mathbb{Z}\) ve
\[P(x) = c_m x^{m} + c_{m-1} x^{m-1} + \cdots + c_1 x + c_0\]
katsayıları tam sayı olan bir polinom olsun. Eğer \(a \equiv b \pmod n\) ise
\[P(a) \equiv P(b) \pmod n\]
İspat
\(a \equiv b \pmod n\) olsun. Teorem 12.1 (f) gereği her \(k \in \{0, 1, \dots, m\}\) için
\[a^{k} \equiv b^{k} \pmod n\]
(burada \(k = 0\) için her iki taraf \(1\)’dir). Şimdi (e) özelliğiyle her iki tarafı \(c_k\) ile çarpalım:
\[c_k a^{k} \equiv c_k b^{k} \pmod n\]
Son olarak (d) özelliğinin toplam kısmını \(m+1\) terim için ardışık olarak uygularsak
\[\sum_{k=0}^{m} c_k a^{k} \equiv \sum_{k=0}^{m} c_k b^{k} \pmod n\]
yani \(P(a) \equiv P(b) \pmod n\) bulunur.
\(\blacksquare\)
Sonuç 12.2 (Çözümler Sınıf Hâlinde Gelir) \(P(x)\) tam katsayılı bir polinom olsun. Eğer \(a\) tam sayısı
\[P(x) \equiv 0 \pmod n\]
kongrüansının bir çözümü ve \(b \equiv a \pmod n\) ise, \(b\) de bu kongrüansın bir çözümüdür.
Gerçekten de Teorem 12.4 gereği \(P(b) \equiv P(a) \equiv 0 \pmod n\)’dir.
Bu sonuç son derece pratiktir: bir kongrüansın çözümlerini ararken sonsuz sayıda tam sayıyı denemek gerekmez. \(0, 1, \dots, n-1\) değerlerini denemek yeterlidir; geri kalan her tam sayı bunlardan birine kongrüdür ve aynı sonucu verir.
Örnek 12.6 (\(p \mid a^2 - b^2\) İse) \(p\) bir asal sayı ve \(a, b \in \mathbb{Z}\) olmak üzere
\[a^2 \equiv b^2 \pmod p \implies a \equiv b \pmod p \ \text{ veya } \ a \equiv -b \pmod p\]
olduğunu gösteriniz.
Çözüm
\(a^2 \equiv b^2 \pmod p\) olsun; tanım gereği
\[p \mid a^2 - b^2\]
Sol tarafı çarpanlarına ayıralım:
\[a^2 - b^2 = (a - b)(a + b)\]
O hâlde
\[p \mid (a-b)(a+b)\]
\(p\) asal olduğundan Teorem 9.1 gereği
\[p \mid a - b \qquad \text{veya} \qquad p \mid a + b\]
Bunlar sırasıyla
\[a \equiv b \pmod p \qquad \text{veya} \qquad a \equiv -b \pmod p\]
demektir.
\(\blacksquare\)
\(p\)’nin asal olması vazgeçilmezdir. \(n = 8\) alalım:
\[3^2 = 9 \equiv 1 = 1^2 \pmod 8\]
olmasına rağmen \(3 \not\equiv 1\) ve \(3 \not\equiv -1 \equiv 7 \pmod 8\)’dir. Nitekim modülo \(8\)’de \(x^2 \equiv 1\) kongrüansının dört çözümü vardır: \(1, 3, 5, 7\).
12.8 Çalışma Problemleri
Alıştırma 12.1 (Kalan Hesapları) Aşağıdaki kalanları bulunuz.
a) \(2^{100}\) sayısının \(7\) ile bölümünden kalan.
b) \(7^{1000}\) sayısının \(11\) ile bölümünden kalan.
c) \(1! + 2! + \cdots + 50!\) sayısının \(15\) ile bölümünden kalan.
d) \(\displaystyle \sum_{k=1}^{100} k^5\) toplamının \(4\) ile bölümünden kalan.
Alıştırma 12.2 (Modülü Değiştirmek) \(a, b, n, m \in \mathbb{Z}\) ve \(1 < n, m\) olsun.
a) \(a \equiv b \pmod n\) ve \(m \mid n\) ise \(a \equiv b \pmod m\) olduğunu gösteriniz.
b) \(a \equiv b \pmod n\) ve \(n \mid m\) ise \(a \equiv b \pmod m\) önermesinin yanlış olduğunu bir karşı örnekle gösteriniz.
c) \(\gcd(n,m) = 1\) olsun. \(a \equiv b \pmod n\) ve \(a \equiv b \pmod m\) olması için gerek ve yeter koşulun \(a \equiv b \pmod{nm}\) olduğunu gösteriniz.
İpucu (c): Teorem 5.2’ı kullanınız.
Alıştırma 12.3 (Kongrüanslarla Bölünebilme) Aşağıdakileri kongrüans diliyle ispatlayınız.
a) Her \(n\) pozitif tam sayısı için \(7 \mid 5^{2n} + 3 \cdot 2^{5n-2}\).
b) Her \(n\) tam sayısı için \(15 \mid 3n^5 + 5n^3 + 7n\).
c) Her \(n\) tam sayısı için, \(7 \nmid n\) ise \(7 \mid n^3 + 1\) veya \(7 \mid n^3 - 1\)’dir.
Alıştırma 12.4 (Küçük Fermat’ya Hazırlık) \(p\) bir asal sayı olmak üzere, her \(a, b\) tam sayısı için
\[(a + b)^{p} \equiv a^{p} + b^{p} \pmod p\]
olduğunu gösteriniz.
İpucu: Binom açılımını yazıp Alıştırma 9.2’u kullanınız: aradaki bütün katsayılar \(p\) ile bölünür.