11 Asal Çarpanlardan Bölenlere
Aritmetiğin esas teoremi her sayıya bir “kimlik kartı” verdi: asal çarpanları ve üsleri. Bu bölümde kartı okumayı öğreneceğiz. Bir sayının bütün bölenleri, kaç böleni olduğu, hatta iki sayının en büyük ortak böleni ve en küçük ortak katı — hepsi doğrudan üslerden okunabilir.
11.1 Asal Bölenler Kümesi
Tanım 11.1 (Asal Bölenler Kümesi) \(n\) bir tam sayı olmak üzere, \(n\)’nin bütün asal bölenlerinin kümesi \(\pi(n)\) ile gösterilir:
\[\pi(n) = \{ p \ : \ p \text{ asal ve } p \mid n \}\]
Bu notlarda \(\pi(n)\) sembolü bir kümedir. Literatürde aynı sembol çoğunlukla “\(x\)’i geçmeyen asalların sayısı” anlamındaki asal sayma fonksiyonu için kullanılır. Karıştırmamak gerekir; burada \(\pi(n)\) daima bir asal sayılar kümesidir.
Örnek 11.1 (Asal Bölenler Kümesi Örnekleri) \[60 = 2^2 \cdot 3 \cdot 5 \implies \pi(60) = \{2, 3, 5\}\]
\[16 = 2^4 \implies \pi(16) = \{2\}\]
Ayrıca \(\pi(1) = \pi(-1) = \emptyset\)’dır; \(1\)’in ve \(-1\)’in asal böleni yoktur.
Önerme 11.1 (Bölünebilme ve Asal Bölenler) Her \(a, b\) tam sayısı için, eğer \(a \mid b\) ise \(\pi(a) \subseteq \pi(b)\)’dir.
Bunun nedeni geçişmedir: \(p \in \pi(a)\) ise \(p \mid a\) ve \(a \mid b\) olduğundan \(p \mid b\), yani \(p \in \pi(b)\)’dir.
\(\pi(a) \subseteq \pi(b)\) olması \(a \mid b\) olmasını gerektirmez. Örneğin \(a = 8\) ve \(b = 2\) için
\[\pi(8) = \{2\} \subseteq \{2\} = \pi(2)\]
olmasına rağmen \(8 \nmid 2\)’dir. Asal bölenler kümesi hangi asalların göründüğünü söyler, kaç kez göründüğünü değil.
11.2 Aynı Asalın Kuvvetleri
Bölenleri okuyabilmek için önce tek bir asalın kuvvetleri arasındaki bölünebilmeyi belirlememiz gerekir.
Önerme 11.2 (Kuvvetler Arasında Bölünebilme) \(1 < a\) bir tam sayı ve \(k, s\) negatif olmayan tam sayılar olsun. Bu durumda
\[a^{k} \mid a^{s} \iff k \leq s\]
İspat
(\(\Leftarrow\)) \(k \leq s\) olsun. Bu durumda \(s - k \geq 0\)’dır ve
\[a^{s} = a^{k} \cdot a^{s-k}\]
yazılır. \(a^{s-k}\) bir tam sayı olduğundan \(a^k \mid a^s\)’dir.
(\(\Rightarrow\)) \(a^k \mid a^s\) olsun ve aksini, yani \(k > s\) olduğunu varsayalım.
\(a > 1\) olduğundan \(a^s \neq 0\)’dır. Teorem 3.1 (8) gereği
\[a^{k} \leq a^{s}\]
Öte yandan \(a > 1\) ve \(k > s\) olduğundan üstel fonksiyon artandır:
\[a^{k} = a^{s} \cdot a^{k-s} > a^{s} \cdot 1 = a^{s}\]
(Burada \(k - s \geq 1\) olduğundan \(a^{k-s} \geq a > 1\) olduğunu kullandık.) İki eşitsizlik çelişir.
O hâlde \(k \leq s\)’dir.
\(\blacksquare\)
11.3 Bütün Bölenleri Okumak
Teorem 11.1 (Bölenler Kümesi) \(0 < n \in \mathbb{Z}\), \(p_1, p_2, \dots, p_r\) ikişer ikişer farklı asal sayılar ve \(0 \leq k_i \in \mathbb{Z}\) olmak üzere
\[n = p_1^{\,k_1} p_2^{\,k_2} \cdots p_r^{\,k_r}\]
olsun. Bu durumda \(n\)’nin tüm pozitif bölenlerinin kümesi
\[\left\{ p_1^{\,m_1} p_2^{\,m_2} \cdots p_r^{\,m_r} \ : \ m_i \in \mathbb{Z}, \ 0 \leq m_i \leq k_i \ (i = 1, \dots, r) \right\}\]
kümesidir.
İspat
Kümeleri adlandıralım:
\[A := \{ d \in \mathbb{Z} : 0 < d, \ d \mid n \}, \qquad B := \left\{ p_1^{\,m_1} \cdots p_r^{\,m_r} : 0 \leq m_i \leq k_i \right\}\]
1. \(B \subseteq A\). \(b = p_1^{m_1} \cdots p_r^{m_r} \in B\) olsun. Her \(i\) için \(m_i \leq k_i\) olduğundan Önerme 11.2 gereği \(p_i^{m_i} \mid p_i^{k_i}\)’dir. Teorem 3.1 (11) gereği bölünebilmeler çarpılabilir:
\[p_1^{\,m_1} \cdots p_r^{\,m_r} \ \Big| \ p_1^{\,k_1} \cdots p_r^{\,k_r} = n\]
Ayrıca \(b > 0\) olduğundan \(b \in A\)’dır.
2. \(A \subseteq B\). \(d \in A\) olsun; yani \(0 < d\) ve \(d \mid n\)’dir.
\(d = 1\) ise bütün \(m_i\)’leri \(0\) alarak \(d = p_1^0 \cdots p_r^0 \in B\) elde ederiz.
Şimdi \(d > 1\) olsun. Önerme 11.1 gereği
\[\pi(d) \subseteq \pi(n) \subseteq \{p_1, \dots, p_r\}\]
O hâlde \(d\)’nin kanonik gösteriminde yalnızca \(p_1, \dots, p_r\) asalları görünebilir:
\[d = p_1^{\,s_1} p_2^{\,s_2} \cdots p_r^{\,s_r}, \qquad 0 \leq s_i\]
Geriye her \(i\) için \(s_i \leq k_i\) olduğunu göstermek kalıyor. Bir \(i\) sabitleyelim ve \(n\)’yi iki parçaya ayıralım:
\[n = p_i^{\,k_i} \cdot \underbrace{\left( p_1^{\,k_1} \cdots p_{i-1}^{\,k_{i-1}} p_{i+1}^{\,k_{i+1}} \cdots p_r^{\,k_r} \right)}_{M}\]
\(p_i\) ile diğer \(p_j\) asalları farklı olduğundan Sonuç 9.1 gereği \(\gcd(p_i, p_j) = 1\)’dir; Sonuç 5.3 gereği \(\gcd(p_i^{s_i}, p_j^{k_j}) = 1\) ve Teorem 5.3’in tekrarlı uygulanmasıyla
\[\gcd\left( p_i^{\,s_i}, \ M \right) = 1\]
bulunur.
Öte yandan \(p_i^{s_i} \mid d\) ve \(d \mid n\) olduğundan \(p_i^{s_i} \mid n = p_i^{k_i} M\)’dir. Teorem 5.1 gereği (\(p_i^{s_i}\) ile \(M\) aralarında asal olduğundan)
\[p_i^{\,s_i} \ \Big| \ p_i^{\,k_i}\]
elde edilir. Önerme 11.2 gereği \(s_i \leq k_i\)’dir.
Bu her \(i\) için geçerli olduğundan \(d \in B\)’dir.
İki kapsama birlikte \(A = B\) verir.
\(\blacksquare\)
Örnek 11.2 (Bölenleri Listeleme) \(12 = 2^2 \cdot 3\) olduğundan, bölenler \(2^{m_1} 3^{m_2}\) biçimindedir ve \(0 \leq m_1 \leq 2\), \(0 \leq m_2 \leq 1\)’dir:
| \(3^0\) | \(3^1\) | |
|---|---|---|
| \(2^0\) | \(1\) | \(3\) |
| \(2^1\) | \(2\) | \(6\) |
| \(2^2\) | \(4\) | \(12\) |
Yani \(12\)’nin pozitif bölenleri \(1, 2, 3, 4, 6, 12\)’dir; toplam \(6\) tane.
11.4 Bölen Sayısı
Yukarıdaki tablo, bölen sayısını hesaplamanın da yolunu gösteriyor: her üs için bağımsız bir seçim yapılır.
Tanım 11.2 (Bölen Sayısı Fonksiyonu) \(0 < n\) bir tam sayı olmak üzere, \(n\)’nin pozitif bölenlerinin sayısı \(\tau(n)\) ile gösterilir.
Sonuç 11.1 (Bölen Sayısı Formülü) \(n = p_1^{\,k_1} p_2^{\,k_2} \cdots p_r^{\,k_r}\) kanonik gösterimi olsun. Bu durumda
\[\tau(n) = \prod_{i=1}^{r} \left( k_i + 1 \right) = (k_1 + 1)(k_2 + 1) \cdots (k_r + 1)\]
İspat
Teorem 11.1 gereği \(n\)’nin her pozitif böleni
\[p_1^{\,m_1} p_2^{\,m_2} \cdots p_r^{\,m_r}, \qquad 0 \leq m_i \leq k_i\]
biçimindedir. Ayrıca farklı \((m_1, \dots, m_r)\) üs dizileri farklı bölenler verir; çünkü aritmetiğin esas teoremi gereği kanonik gösterim tek türlü belirlidir.
O hâlde bölenler ile üs dizileri arasında birebir eşleme vardır. Her \(m_i\) için
\[m_i \in \{0, 1, 2, \dots, k_i\}\]
yani \(k_i + 1\) seçenek bulunur ve seçimler birbirinden bağımsızdır. Toplam seçenek sayısı çarpımlarıdır:
\[\tau(n) = (k_1 + 1)(k_2 + 1) \cdots (k_r + 1)\]
\(\blacksquare\)
Örnek 11.3 (Bölen Sayısı Hesapları) \(\tau(120)\), \(\tau(1001)\) ve \(\tau(p^k)\) değerlerini hesaplayınız (\(p\) asal).
Çözüm
\(\tau(120)\). Örnek 10.2’de \(120 = 2^3 \cdot 3^1 \cdot 5^1\) bulmuştuk. O hâlde
\[\tau(120) = (3+1)(1+1)(1+1) = 4 \cdot 2 \cdot 2 = 16\]
\(\tau(1001)\). \(1001 = 7 \cdot 11 \cdot 13\)’tür (üç farklı asal, hepsinin üssü \(1\)):
\[\tau(1001) = (1+1)(1+1)(1+1) = 8\]
\(\tau(p^k)\). Tek bir asal ve tek bir üs vardır:
\[\tau\left( p^{k} \right) = k + 1\]
Nitekim \(p^k\) sayısının bölenleri \(1, p, p^2, \dots, p^k\)’dır; \(k+1\) tane.
\(\blacksquare\)
11.5 EBOB ve EKOK’u Üslerden Okumak
Bölenleri üsler cinsinden tanıdığımıza göre, ortak bölenleri ve ortak katları da aynı dille ifade edebiliriz.
Teorem 11.2 (Üslerle EBOB ve EKOK) \(p_1 < p_2 < \cdots < p_r\) asal sayılar, \(k_1, \dots, k_r\) ve \(l_1, \dots, l_r\) negatif olmayan tam sayılar olmak üzere
\[n = p_1^{\,k_1} \cdots p_r^{\,k_r}, \qquad m = p_1^{\,l_1} \cdots p_r^{\,l_r}\]
olsun. Bu durumda aşağıdakiler geçerlidir:
\[\text{i)} \quad \gcd(n, m) = \prod_{i=1}^{r} p_i^{\,\min\{k_i,\, l_i\}}\]
\[\text{ii)} \quad \operatorname{lcm}(n, m) = \prod_{i=1}^{r} p_i^{\,\max\{k_i,\, l_i\}}\]
\[\text{iii)} \quad n \cdot m = \gcd(n,m) \cdot \operatorname{lcm}(n,m)\]
İspat
i) \(d := \prod_i p_i^{\min\{k_i, l_i\}}\) diyelim. Teorem 4.2’nun iki koşulunu doğrulayacağız.
\(d\) bir ortak bölendir. Her \(i\) için \(\min\{k_i, l_i\} \leq k_i\) olduğundan Teorem 11.1 gereği \(d \mid n\)’dir. Aynı biçimde \(\min\{k_i, l_i\} \leq l_i\) olduğundan \(d \mid m\)’dir.
Her ortak bölen \(d\)’yi böler. \(c\) pozitif bir ortak bölen olsun. \(c \mid n\) olduğundan Teorem 11.1 gereği
\[c = p_1^{\,s_1} \cdots p_r^{\,s_r}, \qquad s_i \leq k_i\]
yazılır. Aynı teorem \(c \mid m\) için de uygulanınca \(s_i \leq l_i\) bulunur. İkisi birlikte
\[s_i \leq \min\{k_i, l_i\}\]
verir; yine Teorem 11.1 gereği \(c \mid d\)’dir.
(Negatif ortak bölenler için Teorem 3.1 (13) gereği aynı sonuç geçerlidir.)
İki koşul da sağlandığından \(d = \gcd(n,m)\)’dir.
ii) \(M := \prod_i p_i^{\max\{k_i, l_i\}}\) diyelim.
\(M\) bir ortak kattır. Her \(i\) için \(k_i \leq \max\{k_i, l_i\}\) olduğundan Teorem 11.1 gereği \(n \mid M\)’dir; benzer biçimde \(m \mid M\)’dir.
Her ortak kat \(M\) ile bölünür. \(c\) pozitif bir ortak kat olsun. \(n \mid c\) ve \(m \mid c\)’dir. Her \(i\) için \(p_i^{k_i} \mid n \mid c\) ve \(p_i^{l_i} \mid m \mid c\) olduğundan \(p_i^{\max\{k_i,l_i\}} \mid c\)’dir. Farklı asalların kuvvetleri ikişer ikişer aralarında asal olduğundan Teorem 5.2’ın tekrarlı uygulanmasıyla çarpımları da \(c\)’yi böler:
\[M = \prod_{i} p_i^{\,\max\{k_i, l_i\}} \ \Big| \ c\]
Özel olarak \(M \leq c\)’dir. O hâlde \(M\), en küçük pozitif ortak kattır: \(M = \operatorname{lcm}(n,m)\).
iii) Her \(i\) için, iki sayıdan küçüğü ile büyüğünün toplamı, sayıların toplamına eşittir:
\[\min\{k_i, l_i\} + \max\{k_i, l_i\} = k_i + l_i\]
Bu yüzden
\[\gcd(n,m) \cdot \operatorname{lcm}(n,m) = \prod_{i} p_i^{\,\min\{k_i,l_i\} + \max\{k_i,l_i\}} = \prod_{i} p_i^{\,k_i + l_i} = n \cdot m\]
\(\blacksquare\)
Teoremde iki sayı için aynı \(p_1, \dots, p_r\) listesi kullanıldı. Bu bir kısıtlama değildir: bir asal sayılardan birinde görünmüyorsa üssü \(0\) alınır. Örneğin
\[12 = 2^2 \cdot 3^1 \cdot 5^0, \qquad 50 = 2^1 \cdot 3^0 \cdot 5^2\]
yazılabilir ve teorem doğrudan uygulanır.
Örnek 11.4 (Üslerle EBOB ve EKOK Hesabı) \(\gcd(360, 84)\) ve \(\operatorname{lcm}(360, 84)\) değerlerini asal çarpanlara ayırarak bulunuz.
Çözüm
Önce kanonik gösterimleri yazalım:
\[360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0, \qquad 84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1\]
Her asal için üsleri karşılaştıralım:
| Asal | \(360\)’ın üssü | \(84\)’ün üssü | Minimum | Maksimum |
|---|---|---|---|---|
| \(2\) | \(3\) | \(2\) | \(2\) | \(3\) |
| \(3\) | \(2\) | \(1\) | \(1\) | \(2\) |
| \(5\) | \(1\) | \(0\) | \(0\) | \(1\) |
| \(7\) | \(0\) | \(1\) | \(0\) | \(1\) |
Teorem 11.2 gereği
\[\gcd(360, 84) = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^0 = 4 \cdot 3 = 12\]
\[\operatorname{lcm}(360, 84) = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 = 8 \cdot 9 \cdot 5 \cdot 7 = 2520\]
(Sağlama: \(12 \cdot 2520 = 30240\) ve \(360 \cdot 84 = 30240\) ✓)
\(\blacksquare\)
Üsler yöntemi kavramsal olarak aydınlatıcıdır ama pratikte yavaştır: sayıları asal çarpanlarına ayırmak, büyük sayılarda son derece zordur. Öklid algoritması ise çarpanlara hiç bakmadan birkaç bölmede sonuca ulaşır.
Kısacası: anlamak için üsler, hesaplamak için Öklid algoritması.
11.6 Asal Bölenler Kümesiyle Çalışmak
Örnek 11.5 (\(\pi\) Kümesinin Temel Özellikleri) Her \(a, b\) tam sayısı ve her \(k\) pozitif tam sayısı için
\[\pi(ab) = \pi(a) \cup \pi(b), \qquad \pi\left( a^{k} \right) = \pi(a)\]
olduğunu gösteriniz.
Çözüm
Birinci eşitlik.
(\(\supseteq\)) \(p \in \pi(a)\) olsun; \(p \mid a\)’dır. \(a \mid ab\) olduğundan geçişme gereği \(p \mid ab\), yani \(p \in \pi(ab)\)’dir. Aynı akıl yürütme \(\pi(b)\) için de geçerlidir.
(\(\subseteq\)) \(p \in \pi(ab)\) olsun; \(p\) asal ve \(p \mid ab\)’dir. Teorem 9.1 gereği \(p \mid a\) veya \(p \mid b\)’dir; yani \(p \in \pi(a) \cup \pi(b)\)’dir.
İkinci eşitlik. \(p\) asal olmak üzere Sonuç 9.4 gereği
\[p \mid a^{k} \iff p \mid a\]
olduğundan iki küme aynı elemanlara sahiptir.
\(\blacksquare\)
Örnek 11.6 (Aralarında Asallığın \(\pi\) ile İfadesi) İkisi birden sıfır olmayan her \(a, b\) tam sayısı için
\[\gcd(a,b) = 1 \iff \pi(a) \cap \pi(b) = \emptyset\]
olduğunu gösteriniz.
Çözüm
(\(\Rightarrow\)) \(\gcd(a,b) = 1\) olsun. \(\pi(a) \cap \pi(b)\) kümesinde bir \(p\) elemanı bulunsaydı, \(p\) hem \(a\)’yı hem \(b\)’yi bölen bir asal olurdu. Bu durumda \(p\) bir ortak bölendir ve Teorem 4.2 gereği
\[p \mid \gcd(a,b) = 1\]
olurdu; oysa \(p > 1\)’dir. O hâlde kesişim boştur.
(\(\Leftarrow\)) \(\pi(a) \cap \pi(b) = \emptyset\) olsun ve \(d := \gcd(a,b)\) diyelim. \(d > 1\) olduğunu varsayalım. Lemma 9.1 gereği \(d\)’nin bir \(p\) asal böleni vardır. \(p \mid d\), \(d \mid a\) ve \(d \mid b\) olduğundan geçişme gereği
\[p \mid a \qquad \text{ve} \qquad p \mid b\]
olur; yani \(p \in \pi(a) \cap \pi(b)\)’dir. Bu, kesişimin boş olmasıyla çelişir.
O hâlde \(d = 1\)’dir.
\(\blacksquare\)
11.7 Çalışma Problemleri
Alıştırma 11.1 (Bölenler ve Bölen Sayısı) a) \(2^4 \cdot 3^2 \cdot 5\) sayısının kaç pozitif böleni vardır?
b) \(\tau(n) = 3\) olacak biçimdeki bütün \(n\) sayılarını belirleyiniz.
c) \(\tau(n)\) değerinin tek sayı olması için gerek ve yeter koşulun \(n\)’nin bir tam kare olması olduğunu gösteriniz.
İpucu (c): Alıştırma 10.3’yi ve bölen sayısı formülünü birlikte kullanınız.
Alıştırma 11.2 (Bölenlerin Çarpımı) \(0 < n\) bir tam sayı olsun. \(n\)’nin bütün pozitif bölenlerinin çarpımının
\[n^{\tau(n)/2}\]
olduğunu gösteriniz.
İpucu: \(d\) bir bölense \(n/d\) de bir bölendir; bölenleri \((d, n/d)\) çiftleri hâlinde eşleştiriniz.
Alıştırma 11.3 (Üslerle Hesaplar) Aşağıdaki değerleri kanonik gösterimleri kullanarak hesaplayınız.
a) \(\gcd(2^5 \cdot 3^3 \cdot 7,\ 2^2 \cdot 3^4 \cdot 11)\)
b) \(\operatorname{lcm}(2^5 \cdot 3^3 \cdot 7,\ 2^2 \cdot 3^4 \cdot 11)\)
c) \(\gcd(1001, 2431)\) (İpucu: \(2431 = 11 \cdot 13 \cdot 17\).)