17 Kalan Sınıfları ve Birimler Grubu
Şimdiye kadar kongrüansı bir bağıntı olarak kullandık: iki sayının birbirine kongrü olup olmadığını sorduk. Bu bölümde bakış açısını değiştireceğiz. Birbirine kongrü sayıları tek bir nesnede toplayacak ve bu nesneler üzerinde toplama ile çarpma işlemleri tanımlayacağız. Ortaya çıkan yapı, Euler ve Fermat teoremlerini son derece doğal kılacak.
17.1 Kongrüans Bir Denklik Bağıntısıdır
Önerme 17.1 (Kongrüans Denklik Bağıntısıdır) \(1 < n \in \mathbb{Z}\) olmak üzere \(\mathbb{Z}\) üzerinde tanımlanan
\[R = \left\{ (a,b) \ : \ a, b \in \mathbb{Z}, \ a \equiv b \pmod n \right\}\]
bağıntısı bir denklik bağıntısıdır. Her \(a \in \mathbb{Z}\) için \(a\)’nın denklik sınıfı
\[\left\{ a + nk \ : \ k \in \mathbb{Z} \right\} = a + n\mathbb{Z}\]
kümesidir.
İspat
Denklik bağıntısı olmak için üç özellik gerekir; üçü de Teorem 12.1’nde ispatlanmıştı:
- Yansıma. (a) gereği her \(a\) için \(a \equiv a \pmod n\)’dir.
- Simetri. (b) gereği \(a \equiv b\) ise \(b \equiv a\)’dır.
- Geçişme. (c) gereği \(a \equiv b\) ve \(b \equiv c\) ise \(a \equiv c\)’dir.
Şimdi \(a\)’nın denklik sınıfını belirleyelim. Tanım gereği bu sınıf, \(a\)’ya kongrü bütün tam sayılardan oluşur:
\[[a] = \{ x \in \mathbb{Z} \ : \ x \equiv a \pmod n \}\]
\(x \equiv a \pmod n\) olması, \(n \mid x - a\), yani \(x - a = nk\) olacak biçimde bir \(k\) tam sayısının var olması demektir. Buradan \(x = a + nk\) bulunur. O hâlde
\[[a] = \{ a + nk : k \in \mathbb{Z} \} = a + n\mathbb{Z}\]
\(\blacksquare\)
Tanım 17.1 (Kalan Sınıfı) \(a + n\mathbb{Z}\) kümesine \(a\) tam sayısının modülo \(n\) kalan sınıfı denir ve kısaca \(\overline{a}\) ile de gösterilir.
Sonuç 17.1 (Sınıflar Ne Zaman Aynıdır?) Her \(k, l \in \mathbb{Z}\) için aşağıdakiler geçerlidir:
i) \(k + n\mathbb{Z} = l + n\mathbb{Z} \iff k \equiv l \pmod n\)
ii) \(\left( k + n\mathbb{Z} \right) \cap \left( l + n\mathbb{Z} \right) = \emptyset \iff k \not\equiv l \pmod n\)
Bu, denklik bağıntılarının genel özelliğidir: iki denklik sınıfı ya tamamen çakışır ya da hiç kesişmez. Kongrüans dilinde bu, “aynı kalanı veren sayılar aynı sınıftadır” demektir.
\(n = 7\) için
\[\overline{3} = \overline{10} = \overline{-4} = \overline{17}\]
Hepsi aynı kümedir: \(\{\dots, -11, -4, 3, 10, 17, \dots\}\). Sınıfı adlandırmak için hangi temsilcinin seçildiği önemsizdir; bu yüzden bir işlem tanımlarken sonucun temsilci seçiminden bağımsız olduğunu doğrulamak zorundayız. Birazdan tam olarak bunu yapacağız.
Önerme 17.2 (Kalan Sınıfları Kümesi) \(1 < n \in \mathbb{Z}\) olsun. Modülo \(n\) kongrüans bağıntısının belirlediği tüm denklik sınıflarının kümesi
\[\left\{ 0 + n\mathbb{Z},\ 1 + n\mathbb{Z},\ \dots,\ (n-1) + n\mathbb{Z} \right\}\]
kümesidir. Bu küme \(\mathbb{Z}_n\) ile gösterilir.
İspat
Lemma 13.1 gereği her \(a\) tam sayısı \(0, 1, \dots, n-1\) sayılarından tam birine kongrüdür. O hâlde Sonuç 17.1 (i) gereği
\[a + n\mathbb{Z} = r + n\mathbb{Z}\]
olacak biçimde tek türlü belirli bir \(r \in \{0, \dots, n-1\}\) vardır. Demek ki her sınıf listede bulunur.
Ayrıca listedeki sınıflar birbirinden farklıdır: \(0 \leq r < r' \leq n-1\) için \(r \not\equiv r' \pmod n\) olduğundan Sonuç 17.1 (i) gereği \(r + n\mathbb{Z} \neq r' + n\mathbb{Z}\)’dir.
\(\blacksquare\)
Örnek 17.1 (\(\mathbb{Z}_{10}\) Kümesi) \[\mathbb{Z}_{10} = \left\{ \overline{0},\ \overline{1},\ \overline{2},\ \overline{3},\ \overline{4},\ \overline{5},\ \overline{6},\ \overline{7},\ \overline{8},\ \overline{9} \right\}\]
Bu küme \(10\) elemanlıdır. Örneğin \(\overline{3}\) sınıfı, son rakamı \(3\) olan pozitif tam sayıların hepsini (ve \(-7, -17, \dots\) sayılarını) içerir.
17.2 Sınıflarda Çarpma
Tanım 17.2 (Kalan Sınıflarının Çarpımı) \(1 < n \in \mathbb{Z}\) olsun. Modülo \(n\) kalan sınıflarının çarpımı
\[\left( k + n\mathbb{Z} \right) \left( l + n\mathbb{Z} \right) := (kl) + n\mathbb{Z}\]
biçiminde tanımlanır (her \(k, l \in \mathbb{Z}\) için).
Örnek 17.2 (Bir Çarpım Hesabı) \(n = 20\) olsun:
\[\left( 4 + 20\mathbb{Z} \right)\left( 7 + 20\mathbb{Z} \right) = 28 + 20\mathbb{Z} = 8 + 20\mathbb{Z}\]
Son eşitlikte \(28 \equiv 8 \pmod{20}\) olmasını kullandık.
Tanımda bir tehlike vardır: çarpımı hesaplamak için sınıflardan birer temsilci seçtik. Başka temsilciler seçseydik farklı bir sonuç çıkabilir miydi? Aşağıdaki önerme çıkmayacağını söyler.
Önerme 17.3 (Çarpma İyi Tanımlıdır) \(1 < n \in \mathbb{Z}\) olsun. Her \(a, b, c, d \in \mathbb{Z}\) için, eğer
\[a + n\mathbb{Z} = c + n\mathbb{Z} \qquad \text{ve} \qquad b + n\mathbb{Z} = d + n\mathbb{Z}\]
ise
\[(ab) + n\mathbb{Z} = (cd) + n\mathbb{Z}\]
İspat
Sonuç 17.1 (i) gereği hipotez şu demektir:
\[a \equiv c \pmod n \qquad \text{ve} \qquad b \equiv d \pmod n\]
Teorem 12.1 (d) gereği kongrüanslar çarpılabilir:
\[ab \equiv cd \pmod n\]
Yine Sonuç 17.1 (i) gereği bu, \((ab) + n\mathbb{Z} = (cd) + n\mathbb{Z}\) demektir.
\(\blacksquare\)
İyi tanımlılık olmasaydı \(\mathbb{Z}_n\) üzerinde çarpma diye bir işlem olmazdı: aynı iki sınıf, seçilen temsilcilere göre farklı sonuçlar verirdi ve hiçbir hesap güvenilir olmazdı.
Aynı gerekçeyle toplama da iyi tanımlıdır; ispatı Teorem 12.1 (d)’nin toplam kısmıyla birebir aynıdır.
17.3 Birim Sınıflar
Her sınıfın çarpımsal tersi yoktur. Örneğin \(\mathbb{Z}_{10}\)’da \(\overline{2} \cdot \overline{x} = \overline{1}\) eşitliğini sağlayan bir \(\overline{x}\) yoktur; çünkü \(2x \equiv 1 \pmod{10}\) denklemi çözülemez. Tersi olan sınıfları ayırt etmek, bu bölümün geri kalanının konusudur.
Tanım 17.3 (Primitif (İlkel) Kalan Sınıfı) \(a, n \in \mathbb{Z}\) ve \(1 < n\) olsun. Eğer
\[\gcd(a, n) = 1\]
ise \(a + n\mathbb{Z}\) kalan sınıfına bir modülo \(n\) primitif (ilkel) kalan sınıfı — kısaca birim sınıf — denir.
Önerme 17.4 (Birim Olmak İyi Tanımlıdır) Primitif kalan sınıfı kavramı temsilci seçiminden bağımsızdır: eğer \(a + n\mathbb{Z} = b + n\mathbb{Z}\) ise
\[\gcd(a, n) = \gcd(b, n)\]
Gerçekten de \(a + n\mathbb{Z} = b + n\mathbb{Z}\) olması \(a \equiv b \pmod n\) demektir; Önerme 12.1 gereği bu iki en büyük ortak bölen eşittir.
Tanım 17.4 (Birimler Kümesi) \(1 < n \in \mathbb{Z}\) olmak üzere, \(\mathbb{Z}_n\) içindeki tüm primitif kalan sınıflarının kümesi
\[U\left( \mathbb{Z}_n \right)\]
ile gösterilir.
Örnek 17.3 (Birim Kümelerine Örnekler) a) \(U(\mathbb{Z}_{10})\) kümesini bulunuz.
b) \(p\) bir asal sayı olmak üzere \(U(\mathbb{Z}_p)\) kümesini belirleyiniz.
c) \(U(\mathbb{Z}_{12})\) kümesini bulunuz.
Çözüm
a) \(0, 1, \dots, 9\) temsilcilerinden hangilerinin \(10\) ile aralarında asal olduğuna bakalım:
\[\gcd(1,10) = \gcd(3,10) = \gcd(7,10) = \gcd(9,10) = 1\]
Geri kalanlar için \(\gcd\) değeri \(2\), \(5\) veya \(10\) çıkar. O hâlde
\[U\left( \mathbb{Z}_{10} \right) = \left\{ \overline{1},\ \overline{3},\ \overline{7},\ \overline{9} \right\}\]
Bu küme \(4\) elemanlıdır.
b) \(p\) asal olduğundan Önerme 9.1 gereği \(\gcd(a, p)\) değeri, \(p \mid a\) ise \(p\), aksi hâlde \(1\)’dir. Temsilciler \(0, 1, \dots, p-1\) arasında \(p\) ile bölünen tek sayı \(0\)’dır. O hâlde
\[U\left( \mathbb{Z}_p \right) = \left\{ \overline{1},\ \overline{2},\ \dots,\ \overline{p-1} \right\}\]
Yani sıfır sınıfı dışındaki bütün sınıflar birimdir; bu küme \(p - 1\) elemanlıdır.
c) \(12\) ile aralarında asal olan \(0 \leq a < 12\) sayıları \(1, 5, 7, 11\)’dir:
\[U\left( \mathbb{Z}_{12} \right) = \left\{ \overline{1},\ \overline{5},\ \overline{7},\ \overline{11} \right\}\]
\(\blacksquare\)
17.4 Birimler Bir Grup Oluşturur
Teorem 17.1 (Birimler Grubu) \(1 < n \in \mathbb{Z}\) olsun. Bu durumda \(U(\mathbb{Z}_n)\) kümesi, kalan sınıflarının çarpımı işlemine göre bir grup oluşturur.
İspat
Önerme 17.3’de çarpma işleminin iyi tanımlı olduğunu görmüştük. Şimdi grup aksiyomlarını doğrulayalım.
1. Kapalılık. \(\overline{a}, \overline{b} \in U(\mathbb{Z}_n)\) olsun; yani \(\gcd(a,n) = 1\) ve \(\gcd(b,n) = 1\)’dir. Teorem 5.3 gereği
\[\gcd(ab, n) = 1\]
olur; yani \(\overline{a}\,\overline{b} = \overline{ab} \in U(\mathbb{Z}_n)\)’dir.
2. Birleşme özelliği. Tam sayılarda çarpma birleşmeli olduğundan
\[\left( \overline{a}\,\overline{b} \right) \overline{c} = \overline{(ab)c} = \overline{a(bc)} = \overline{a} \left( \overline{b}\,\overline{c} \right)\]
3. Birim eleman. \(\gcd(1, n) = 1\) olduğundan \(\overline{1} \in U(\mathbb{Z}_n)\)’dir. Ayrıca her \(\overline{a}\) için
\[\overline{1} \cdot \overline{a} = \overline{a} = \overline{a} \cdot \overline{1}\]
Özel olarak \(U(\mathbb{Z}_n) \neq \emptyset\)’dır.
4. Ters eleman. \(\overline{a} \in U(\mathbb{Z}_n)\) olsun; \(\gcd(a,n) = 1\)’dir. Önerme 15.1 gereği
\[ab \equiv 1 \pmod n\]
olacak biçimde bir \(b\) tam sayısı vardır; yani \(\overline{a}\,\overline{b} = \overline{1}\)’dir.
Geriye \(\overline{b}\) sınıfının da bir birim olduğunu, yani \(\gcd(b, n) = 1\) olduğunu göstermek kalıyor. \(ab \equiv 1 \pmod n\) olduğundan
\[ab - 1 = nk \implies ab - nk = 1\]
olacak biçimde bir \(k\) tam sayısı vardır. Sol tarafta \(b\) ile \(n\)’nin bir doğrusal birleşimi vardır ve değeri \(1\)’dir; Sonuç 4.3 gereği \(\gcd(b,n) = 1\)’dir.
Dört aksiyom da sağlandığından \(U(\mathbb{Z}_n)\) bir gruptur.
\(\blacksquare\)
Grup yapısının en somut faydası sadeleştirmedir: bir grupta \(xy = xz\) ise \(x\)’in tersiyle çarparak \(y = z\) elde edilir. \(U(\mathbb{Z}_n)\) bağlamında bu, tam olarak Sonuç 12.1 (1)’in söylediği şeydir.
İkinci fayda, sonlu gruplarla ilgili genel teoremlerin doğrudan uygulanabilmesidir. Nitekim Euler teoremi, bu grubun eleman sayısıyla ilgili bir sonuçtan başka bir şey değildir — bunu Euler teoremi bölümünde göreceğiz.
\(U(\mathbb{Z}_n)\) kümesinin eleman sayısı, tanımı gereği
\[\left| U(\mathbb{Z}_n) \right| = \#\left\{ a \in \{1, \dots, n\} \ : \ \gcd(a, n) = 1 \right\}\]
sayısıdır. Bu sayıya Euler’in \(\phi\) fonksiyonu denir ve \(\phi(n)\) ile gösterilir. Az önceki örneklerde
\[\phi(10) = 4, \qquad \phi(12) = 4, \qquad \phi(p) = p - 1\]
bulmuştuk. Bu fonksiyonu ve özelliklerini kendi bölümünde ayrıntılı inceleyeceğiz.
Örnek 17.4 (\(U(\mathbb{Z}_8)\) İçin Çarpım Tablosu) \(U(\mathbb{Z}_8)\) kümesini bulunuz ve çarpım tablosunu yazınız.
Çözüm
\(8\) ile aralarında asal olan \(0 \leq a < 8\) sayıları \(1, 3, 5, 7\)’dir:
\[U\left( \mathbb{Z}_8 \right) = \left\{ \overline{1},\ \overline{3},\ \overline{5},\ \overline{7} \right\}\]
Çarpımları modülo \(8\) hesaplayalım:
| \(\cdot\) | \(\overline{1}\) | \(\overline{3}\) | \(\overline{5}\) | \(\overline{7}\) |
|---|---|---|---|---|
| \(\overline{1}\) | \(\overline{1}\) | \(\overline{3}\) | \(\overline{5}\) | \(\overline{7}\) |
| \(\overline{3}\) | \(\overline{3}\) | \(\overline{1}\) | \(\overline{7}\) | \(\overline{5}\) |
| \(\overline{5}\) | \(\overline{5}\) | \(\overline{7}\) | \(\overline{1}\) | \(\overline{3}\) |
| \(\overline{7}\) | \(\overline{7}\) | \(\overline{5}\) | \(\overline{3}\) | \(\overline{1}\) |
(Örneğin \(3 \cdot 5 = 15 \equiv 7\) ve \(5 \cdot 7 = 35 \equiv 3 \pmod 8\)’dir.)
Tablonun köşegeninde yalnızca \(\overline{1}\) görünüyor: bu grupta her elemanın karesi birimdir, yani her eleman kendi tersidir. Nitekim \(1^2 = 1\), \(3^2 = 9 \equiv 1\), \(5^2 = 25 \equiv 1\), \(7^2 = 49 \equiv 1 \pmod 8\)’dir.
\(\blacksquare\)
17.5 Çalışma Problemleri
Alıştırma 17.1 (Kalan Sınıflarıyla Hesap) a) \(\mathbb{Z}_6\) kümesinin elemanlarını yazınız ve çarpım tablosunu oluşturunuz.
b) \(\mathbb{Z}_6\) içinde \(\overline{2} \cdot \overline{3} = \overline{0}\) olduğunu gözlemleyiniz. İkisi de sıfırdan farklı olan iki sınıfın çarpımının sıfır olabilmesi, \(n\) hakkında ne söyler?
c) \(\mathbb{Z}_n\) içinde sıfırdan farklı iki sınıfın çarpımının hiçbir zaman sıfır olmaması için gerek ve yeter koşulun \(n\)’nin asal olması olduğunu gösteriniz.
Alıştırma 17.2 (Birimler Kümeleri) Aşağıdaki kümeleri belirleyiniz ve eleman sayılarını yazınız.
a) \(U(\mathbb{Z}_9)\) b) \(U(\mathbb{Z}_{15})\) c) \(U(\mathbb{Z}_{16})\) d) \(U(\mathbb{Z}_{7})\)
Alıştırma 17.3 (Tersleri Bulma) \(U(\mathbb{Z}_{15})\) kümesindeki her elemanın çarpımsal tersini bulunuz. Kendi tersi olan elemanları belirleyiniz.
Alıştırma 17.4 (Birimlerin Çarpımı) \(1 < n\) ve \(\{a_1, \dots, a_k\}\) kümesi \(U(\mathbb{Z}_n)\) elemanlarının temsilcileri olsun. \(\gcd(a, n) = 1\) olmak üzere
\[\{ a a_1,\ a a_2,\ \dots,\ a a_k \}\]
kümesinin de aynı birim sınıfları — belki farklı sırayla — temsil ettiğini gösteriniz.
İpucu: Teorem 13.2’in ispatındaki fikri kullanınız; kapalılık ve sadeleştirme yeterlidir. (Bu gözlem, Euler teoreminin ispatının çekirdeğidir.)