13 Tam Kalan Sistemleri
Kongrüans, tam sayıları \(n\) gruba ayırır: aynı kalanı verenler bir arada. Bu bölümde bu grupların her birinden birer temsilci seçmenin ne anlama geldiğini inceleyeceğiz. “Tam kalan sistemi” adını verdiğimiz bu temsilci listeleri, ileride Euler ve Fermat teoremlerinin ispatında merkezî rol oynayacak.
13.1 Her Sayı Tam Bir Kalana Kongrüdür
Lemma 13.1 (Kalanların Temsil Gücü) \(1 < n\) sabit bir tam sayı olsun. Bu durumda her tam sayı
\[0, \quad 1, \quad 2, \quad \dots, \quad n-1\]
sayılarından tam birisine modülo \(n\) kongrüdür.
İspat
\(a\) herhangi bir tam sayı olsun.
Varlık. Bölme algoritmasına göre
\[a = nq + r, \qquad 0 \leq r < n\]
olacak biçimde \(q, r\) tam sayıları vardır. Buradan \(a - r = nq\), yani \(n \mid a - r\) olur; demek ki
\[a \equiv r \pmod n\]
ve \(r \in \{0, 1, \dots, n-1\}\)’dir.
Teklik. \(a \equiv r \pmod n\) ve \(a \equiv r' \pmod n\) olsun; \(r, r' \in \{0, 1, \dots, n-1\}\) olduğunu varsayalım. Teorem 12.1 (b) ve (c) gereği
\[r \equiv r' \pmod n\]
olur; yani \(n \mid r - r'\)’dür. Öte yandan
\[0 \leq r, r' \leq n - 1 \implies |r - r'| \leq n - 1 < 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 = r'\)’dür.
\(\blacksquare\)
13.2 Tam Kalan Sistemi
Tanım 13.1 (Tam Kalan Sınıfları Kümesi) \(1 < n\) sabit bir tam sayı ve \(\{a_1, a_2, \dots, a_n\}\) tam sayıların bir alt kümesi olsun. Eğer
her tam sayı, \(a_1, a_2, \dots, a_n\) sayılarından tam birisine modülo \(n\) kongrüdür
koşulu sağlanırsa, bu kümeye modülo \(n\) tam kalan sınıfları kümesi (kısaca tam kalan sistemi) denir.
Örnek 13.1 (En Tanıdık Örnek) \(1 < n\) olmak üzere
\[\{ 0, 1, 2, \dots, n-1 \}\]
kümesi bir modülo \(n\) tam kalan sistemidir; bu, Lemma 13.1’nin doğrudan ifadesidir.
Tanım 13.2 (Negatif Olmayan En Küçük Tam Kalan Sistemi) \(1 < n\) olmak üzere \(\{0, 1, 2, \dots, n-1\}\) kümesine negatif olmayan en küçük tam kalan sınıfları kümesi denir.
Bir tam kalan sistemi olup olmadığını anlamak için tanımdaki “her tam sayı” koşulunu tek tek sınamak gerekmez; çok daha pratik bir ölçüt vardır.
Teorem 13.1 (Tam Kalan Sistemi Ölçütü) \(1 < n\) sabit bir tam sayı ve \(A = \{a_1, a_2, \dots, a_n\} \subset \mathbb{Z}\) \(n\) elemanlı bir küme olsun. \(A\)’nın bir modülo \(n\) tam kalan sistemi olması için gerek ve yeter koşul, elemanlarının ikişer ikişer birbirine kongrü olmamasıdır:
\[i \neq j \implies a_i \not\equiv a_j \pmod n\]
İspat
(\(\Rightarrow\)) \(A\) bir tam kalan sistemi olsun. \(i \neq j\) için \(a_i \equiv a_j \pmod n\) olduğunu varsayalım.
Teorem 12.1 (a) gereği \(a_i \equiv a_i \pmod n\)’dir. O hâlde \(a_i\) tam sayısı, \(A\) kümesinin iki farklı elemanına — hem \(a_i\)’ye hem \(a_j\)’ye — modülo \(n\) kongrü olur. Bu, tanımdaki “tam birisine” koşuluyla çelişir.
(\(\Leftarrow\)) \(A\)’nın elemanları ikişer ikişer kongrü olmasın. Her \(a_i\) için, Lemma 13.1 gereği
\[a_i \equiv r_i \pmod n, \qquad r_i \in \{0, 1, \dots, n-1\}\]
olacak biçimde tek türlü belirli bir \(r_i\) vardır.
\(r_i\)’ler birbirinden farklıdır. \(i \neq j\) için \(r_i = r_j\) olsaydı, geçişme gereği
\[a_i \equiv r_i = r_j \equiv a_j \pmod n\]
olurdu; bu, hipoteze aykırıdır.
O hâlde \(r_1, \dots, r_n\) sayıları, \(n\) elemanlı \(\{0, 1, \dots, n-1\}\) kümesinin birbirinden farklı \(n\) elemanıdır. Demek ki
\[\{ r_1, r_2, \dots, r_n \} = \{ 0, 1, \dots, n-1 \}\]
Şimdi herhangi bir \(m\) tam sayısı alalım. Lemma 13.1 gereği \(m\), \(\{0, \dots, n-1\}\) kümesinin tam bir elemanına kongrüdür; bu eleman bir \(r_i\)’dir ve dolayısıyla
\[m \equiv r_i \equiv a_i \pmod n\]
olur. Başka bir \(a_j\)’ye de kongrü olsaydı \(a_i \equiv a_j\) olurdu — hipoteze aykırı. O hâlde \(m\), \(A\)’nın tam bir elemanına kongrüdür.
\(\blacksquare\)
Ölçütü kullanırken kümenin tam \(n\) elemanlı olduğunu doğrulamayı unutmayın. Örneğin \(\{0, 1\}\) kümesinin elemanları modülo \(5\)’te kongrü değildir, ama \(5\) elemanlı olmadığından tam kalan sistemi değildir.
Kısacası: \(n\) eleman \(+\) ikişer ikişer kongrü olmama \(=\) tam kalan sistemi.
Örnek 13.2 (Bir Tam Kalan Sistemi) \[\{ -19,\ -11,\ 18,\ 22,\ 62,\ 82,\ 91 \}\]
kümesinin modülo \(7\) bir tam kalan sistemi olduğunu gösteriniz.
Çözüm
Küme \(7\) elemanlıdır; Teorem 13.1 gereği elemanların ikişer ikişer kongrü olmadığını göstermek yeterlidir. Bunun için her elemanın modülo \(7\) kalanını hesaplayalım:
\[ \begin{aligned} -19 &\equiv 2, & -11 &\equiv 3, & 18 &\equiv 4, & 22 &\equiv 1 \pmod 7 \\ 62 &\equiv 6, & 82 &\equiv 5, & 91 &\equiv 0 \pmod 7 \end{aligned} \]
(Örneğin \(-19 + 21 = 2\), \(62 - 56 = 6\) ve \(91 = 13 \cdot 7\)’dir.)
Kalanlar
\[\{ 2, 3, 4, 1, 6, 5, 0 \} = \{ 0, 1, 2, 3, 4, 5, 6 \}\]
biçiminde birbirinden farklı çıktığından elemanlar ikişer ikişer kongrü değildir. O hâlde verilen küme modülo \(7\) bir tam kalan sistemidir.
\(\blacksquare\)
13.3 Sistemi Bozmayan Dönüşümler
Bir tam kalan sisteminden yeni sistemler üretmenin sistematik bir yolu vardır: bütün elemanları uygun bir sayıyla çarpmak.
Teorem 13.2 (Aralarında Asal Bir Sayıyla Çarpmak) \(1 < n\) sabit bir tam sayı, \(\{a_1, a_2, \dots, a_n\}\) bir modülo \(n\) tam kalan sistemi, \(a \in \mathbb{Z}\) ve \(\gcd(a, n) = 1\) olsun. Bu durumda
\[\{ a a_1,\ a a_2,\ \dots,\ a a_n \}\]
kümesi de bir modülo \(n\) tam kalan sistemidir.
İspat
Teorem 13.1’ü kullanacağız; iki şeyi doğrulamalıyız.
1. Küme \(n\) elemanlıdır. \(i \neq j\) için \(a a_i \neq a a_j\) olduğunu görelim. Eşit olsalardı, \(\gcd(a,n) = 1\) olduğundan \(a \neq 0\)’dır ve sadeleştirmeyle \(a_i = a_j\) bulunurdu — oysa küme \(n\) elemanlıdır.
2. Elemanlar ikişer ikişer kongrü değildir. \(i \neq j\) için
\[a a_i \equiv a a_j \pmod n\]
olduğunu varsayalım. \(\gcd(a, n) = 1\) olduğundan Sonuç 12.1 (1) gereği \(a\) çarpanını sadeleştirebiliriz:
\[a_i \equiv a_j \pmod n\]
Ama \(\{a_1, \dots, a_n\}\) bir tam kalan sistemi olduğundan Teorem 13.1 gereği \(i = j\) olmalıdır — çelişki.
İki koşul da sağlandığından \(\{a a_1, \dots, a a_n\}\) bir tam kalan sistemidir.
\(\blacksquare\)
\(n = 6\) ve \(a = 2\) alalım. \(\{0,1,2,3,4,5\}\) bir tam kalan sistemidir, ama ikiyle çarpılmış hâli
\[\{0, 2, 4, 6, 8, 10\}\]
modülo \(6\)’da \(\{0, 2, 4, 0, 2, 4\}\) kalanlarını verir; hiçbir tek kalan üretilemez. Burada \(\gcd(2,6) = 2 \neq 1\)’dir.
Örnek 13.3 (Yalnızca Çift Sayılardan Oluşan Bir Sistem) Her \(1 < n\) tek tam sayısı için, her bir elemanı çift olan bir modülo \(n\) tam kalan sistemi bulunduğunu gösteriniz.
Çözüm
\(n\) tek olduğundan \(2 \nmid n\)’dir; Önerme 9.1 gereği
\[\gcd(2, n) = 1\]
Şimdi negatif olmayan en küçük tam kalan sistemi olan \(\{0, 1, \dots, n-1\}\) kümesini alıp bütün elemanlarını \(2\) ile çarpalım. Teorem 13.2 gereği
\[\{ 0,\ 2,\ 4,\ \dots,\ 2(n-1) \}\]
kümesi de bir modülo \(n\) tam kalan sistemidir. Bu kümenin her elemanı çifttir.
\(\blacksquare\)
Örnek 13.4 (Modülo \(9\) İçin Örnek) Her bir elemanı çift olan bir modülo \(9\) tam kalan sistemi örneği veriniz.
Çözüm
\(9\) tek olduğundan Örnek 13.3’daki kuruluş uygulanabilir. \(\{0, 1, \dots, 8\}\) kümesini \(2\) ile çarpalım:
\[\{ 0,\ 2,\ 4,\ 6,\ 8,\ 10,\ 12,\ 14,\ 16 \}\]
Doğrulayalım; kalanları modülo \(9\) hesaplayalım:
| Eleman | \(0\) | \(2\) | \(4\) | \(6\) | \(8\) | \(10\) | \(12\) | \(14\) | \(16\) |
|---|---|---|---|---|---|---|---|---|---|
| Kalan | \(0\) | \(2\) | \(4\) | \(6\) | \(8\) | \(1\) | \(3\) | \(5\) | \(7\) |
Kalanlar \(0\)’dan \(8\)’e kadar bütün değerleri birer kez veriyor; küme \(9\) elemanlı ve elemanları ikişer ikişer kongrü değil. O hâlde bu bir modülo \(9\) tam kalan sistemidir ve bütün elemanları çifttir.
\(\blacksquare\)
Örnek 13.5 (Çift Modülde Neden Olmaz?) \(n\) çift bir tam sayı olmak üzere, her bir elemanı çift olan bir kümenin asla modülo \(n\) tam kalan sistemi olamayacağını gösteriniz.
Çözüm
\(n\) çift olsun ve \(A = \{a_1, \dots, a_n\}\) kümesinin bütün elemanlarının çift olduğunu varsayalım.
Herhangi bir \(a_i\) için bölme algoritmasını yazalım:
\[a_i = n q_i + r_i, \qquad 0 \leq r_i < n\]
Buradan
\[r_i = a_i - n q_i\]
olur. Sağ taraftaki iki terime bakalım: \(a_i\) çifttir ve \(n\) çift olduğundan \(n q_i\) de çifttir. İki çift sayının farkı çift olduğundan (bkz. Önerme 2.1) \(r_i\) çifttir.
Demek ki \(A\) kümesinin elemanlarının verdiği bütün kalanlar çifttir. Oysa bir tam kalan sisteminin kalanları \(\{0, 1, \dots, n-1\}\) kümesinin tamamını vermelidir ve \(n > 1\) olduğundan bu kümede \(1\) gibi tek sayılar da vardır.
Tek bir kalan bile üretilemediğinden \(A\) bir tam kalan sistemi olamaz.
\(\blacksquare\)
Örnek 13.3 ile Örnek 13.5 birlikte tam bir sınıflandırma verir:
Yalnızca çift sayılardan oluşan bir modülo \(n\) tam kalan sistemi vardır ancak ve ancak \(n\) tek ise.
Bu, Teorem 13.2’deki aralarında asallık koşulunun ne kadar keskin olduğunu gösterir: koşul sağlandığında dönüşüm işler, sağlanmadığında hiçbir şey kurtaramaz.
13.4 Çalışma Problemleri
Alıştırma 13.1 (Tam Kalan Sistemi mi?) Aşağıdaki kümelerin belirtilen modüle göre tam kalan sistemi olup olmadığını belirleyiniz.
a) \(\{1, 2, 3, 4, 5\}\), modülo \(5\)
b) \(\{-2, -1, 0, 1, 2\}\), modülo \(5\)
c) \(\{0, 3, 6, 9, 12, 15\}\), modülo \(6\)
d) \(\{1, 5, 9, 13, 17, 21\}\), modülo \(6\)
Alıştırma 13.2 (Öteleme ve Çarpma) \(\{a_1, \dots, a_n\}\) bir modülo \(n\) tam kalan sistemi olsun.
a) Her \(b \in \mathbb{Z}\) için \(\{a_1 + b, \dots, a_n + b\}\) kümesinin de bir tam kalan sistemi olduğunu gösteriniz.
b) \(\gcd(a,n) = 1\) ve \(b \in \mathbb{Z}\) olmak üzere \(\{a a_1 + b, \dots, a a_n + b\}\) kümesinin de bir tam kalan sistemi olduğunu gösteriniz.
Alıştırma 13.3 (Bir Tam Kalan Sisteminin Toplamı) \(1 < n\) tek bir tam sayı ve \(\{a_1, \dots, a_n\}\) bir modülo \(n\) tam kalan sistemi olsun.
\[a_1 + a_2 + \cdots + a_n \equiv 0 \pmod n\]
olduğunu gösteriniz. \(n\) çift olduğunda bu sonucun neden bozulduğunu açıklayınız.
İpucu: Toplam, \(0 + 1 + \cdots + (n-1) = \dfrac{n(n-1)}{2}\) sayısına kongrüdür.