9 Asal Sayılar
Bölünebilme kuramının merkezinde, başka sayılara ayrılamayan sayılar durur. Bu bölümde bu “bölünemez” sayıları tanımlayacak, aralarında asallık kuramımızın onlara nasıl özellikle iyi uyduğunu göreceğiz. Elde edeceğimiz sonuçlar bir sonraki bölümde aritmetiğin esas teoremini kuracak.
9.1 Tanım
Tanım 9.1 (Asal Sayı) \(1 < p \in \mathbb{Z}\) olsun. Eğer \(p\)’nin \(1\) ve kendisinden başka hiç pozitif böleni yoksa \(p\)’ye bir asal sayı denir.
Asal olmayan \(1 < n\) tam sayılarına bileşik sayı denir.
Örnek 9.1 (İlk Asal Sayılar) \(2, 3, 5, 7, 11, 13\) birer asal sayıdır. Buna karşılık \(6 = 2 \cdot 3\) olduğundan \(6\) asal değildir; bileşiktir.
Tanım gereği \(1\) asal değildir; çünkü tanım \(1 < p\) koşulunu içerir.
Bu, keyfî bir dışlama değildir. Bir sonraki bölümde her sayının asalların çarpımı olarak tek türlü yazıldığını göreceğiz. \(1\) asal sayılsaydı bu teklik anında bozulurdu:
\[6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3 = \cdots\]
Yani \(1\)’i dışarıda bırakmak, aritmetiğin esas teoremini kurtarmak içindir.
Bileşik sayıların tanımını biraz açalım. \(1 < n\) asal değilse, \(n\)’nin \(1\)’den ve \(n\)’den farklı bir \(k\) pozitif böleni vardır. O hâlde
\[n = k \cdot m\]
olacak biçimde bir \(m\) tam sayısı vardır ve \(1 < m < n\)’dir. Kısaca: asal olmayan bir \(1 < n\) tam sayısı, kendisinden küçük iki tam sayının çarpımı biçiminde yazılabilir. Bu gözlemi ileride tümevarım adımlarında kullanacağız.
9.2 Asal Sayılar ve Aralarında Asallık
Asal sayıların bölünebilme kuramındaki gücü, aşağıdaki basit gözlemden gelir: bir asal sayı, her sayıyla ya “tamamen ilgilidir” ya da “hiç ilgili değildir”.
Önerme 9.1 (Bir Asalla EBOB) Her \(a \in \mathbb{Z}\) ve her \(p\) asal sayısı için
\[\gcd(p, a) = \begin{cases} 1, & p \nmid a \text{ ise} \\ p, & p \mid a \text{ ise} \end{cases}\]
İspat
\(d := \gcd(p, a)\) diyelim. \(d\) pozitif bir tam sayıdır ve \(d \mid p\)’dir. \(p\) asal olduğundan pozitif bölenleri yalnızca \(1\) ve \(p\)’dir; o hâlde
\[d = 1 \qquad \text{veya} \qquad d = p\]
Şimdi iki durumu ayıralım.
\(p \mid a\) ise. Bu durumda \(p\) sayısı hem \(p\)’yi hem \(a\)’yı böler; yani bir ortak bölendir. Ortak bölenlerin en büyüğü \(p\)’yi geçemeyeceğinden ve \(p\) bir ortak bölen olduğundan \(d = p\)’dir.
\(p \nmid a\) ise. \(d = p\) olsaydı \(d \mid a\), yani \(p \mid a\) olurdu — hipoteze aykırı. O hâlde \(d = 1\)’dir.
\(\blacksquare\)
Sonuç 9.1 (Farklı Asallar Aralarında Asaldır) \(p\) ile \(q\) farklı iki asal sayı olsun. Bu durumda \(p \nmid q\) ve dolayısıyla
\[\gcd(p, q) = 1\]
Gerçekten de \(q\)’nun pozitif bölenleri yalnızca \(1\) ve \(q\)’dur. \(p \mid q\) olsaydı \(p = 1\) veya \(p = q\) olurdu; ikisi de hipoteze aykırıdır. Önerme 9.1 gereği \(\gcd(p,q) = 1\)’dir.
9.3 Öklid Lemmasının Asal Hâli
Öklid lemması “\(a \mid bc\) ve \(\gcd(a,b) = 1\) ise \(a \mid c\)” diyordu. Modül asal olduğunda aralarında asallık koşulu kendiliğinden sağlanır ve lemma çok daha kullanışlı bir biçim alır.
Teorem 9.1 (Asal Sayılar İçin Öklid Lemması) Her \(a, b \in \mathbb{Z}\) ve her \(p\) asal sayısı için
\[p \mid ab \implies p \mid a \ \text{ veya } \ p \mid b\]
Bir başka deyişle: bir asal sayı iki tam sayının çarpımını bölerse, bu tam sayılardan en az birini böler.
İspat
\(p \mid ab\) olsun. İki durum vardır.
Durum 1: \(p \mid a\). İddia zaten sağlanmıştır; gösterilecek bir şey yoktur.
Durum 2: \(p \nmid a\). Önerme 9.1 gereği \(\gcd(p, a) = 1\)’dir. Elimizde
\[p \mid ab \qquad \text{ve} \qquad \gcd(p,a) = 1\]
vardır. Teorem 5.1 gereği \(p \mid b\)’dir.
Her iki durumda da \(p \mid a\) veya \(p \mid b\) sonucuna ulaşılır.
\(\blacksquare\)
\(6 \mid 2 \cdot 3\) olmasına rağmen \(6 \nmid 2\) ve \(6 \nmid 3\)’tür. Teorem bozulmuş değildir: \(6\) asal değildir.
Nitekim bu özellik asallığı karakterize eder: \(1 < n\) tam sayısı bu özelliği taşıyorsa asal olmak zorundadır (bkz. Alıştırma 9.1).
Sonuç 9.2 (Çok Çarpanlı Hâl) \(p\) bir asal sayı ve \(a_1, \dots, a_n \in \mathbb{Z}\) olsun. Eğer
\[p \mid a_1 a_2 \cdots a_n\]
ise, \(p \mid a_s\) olacak biçimde bir \(s \in \{1, \dots, n\}\) vardır.
İspat
\(n\) üzerinden tümevarım yapalım.
Başlangıç adımı (\(n = 1\)). \(p \mid a_1\) olduğundan \(s = 1\) alınır.
Tümevarım adımı. İddianın \(n = k\) için doğru olduğunu varsayalım ve
\[p \mid a_1 a_2 \cdots a_k a_{k+1}\]
olsun. Çarpımı iki parçaya ayıralım:
\[p \ \mid \ \underbrace{\left( a_1 \cdots a_k \right)}_{A} \cdot a_{k+1}\]
Teorem 9.1 gereği \(p \mid A\) veya \(p \mid a_{k+1}\)’dir.
- \(p \mid a_{k+1}\) ise \(s = k+1\) alınır.
- \(p \mid A = a_1 \cdots a_k\) ise tümevarım hipotezi gereği \(p \mid a_s\) olacak biçimde bir \(s \in \{1, \dots, k\}\) vardır.
Her iki durumda da istenen \(s\) bulunur.
\(\blacksquare\)
Sonuç 9.3 (Asalların Çarpımını Bölen Asal) \(p, q_1, \dots, q_n\) asal sayılar olmak üzere, eğer
\[p \mid q_1 q_2 \cdots q_n\]
ise \(p = q_k\) olacak biçimde bir \(k \in \{1, \dots, n\}\) vardır.
Bunun nedeni açıktır: Sonuç 9.2 gereği \(p \mid q_k\) olacak biçimde bir \(k\) vardır. \(q_k\) asal olduğundan pozitif bölenleri yalnızca \(1\) ve \(q_k\)’dır; \(p > 1\) olduğundan \(p = q_k\) olmak zorundadır.
Sonuç 9.4 (Kuvvetleri Bölmek) Her \(a\) tam sayısı, her \(k\) pozitif tam sayısı ve her \(p\) asal sayısı için
\[p \mid a^{k} \iff p \mid a\]
Gerçekten de (\(\Leftarrow\)) yönü açıktır. (\(\Rightarrow\)) yönü ise Sonuç 9.2’in \(a_1 = \cdots = a_k = a\) alınmış hâlidir.
9.4 Her Sayının Bir Asal Böleni Vardır
Lemma 9.1 (Asal Bölenin Varlığı) \(1\)’den büyük her tam sayının en az bir asal böleni vardır.
İspat
\(1 < n\) bir tam sayı olsun. \(n\)’nin \(1\)’den büyük pozitif bölenlerinin kümesini alalım:
\[D = \{ d \in \mathbb{N} \ : \ d > 1, \ d \mid n \}\]
\(n \mid n\) ve \(n > 1\) olduğundan \(n \in D\)’dir; yani \(D\) boş değildir. İyi sıralama prensibi gereği \(D\) kümesinin bir en küçük elemanı vardır; buna \(p\) diyelim.
İddia: \(p\) asaldır. Aksini varsayalım. \(p > 1\) ve \(p\) asal olmadığından
\[p = ab, \qquad 1 < a < p\]
olacak biçimde tam sayılar vardır. Şimdi \(a \mid p\) ve \(p \mid n\) olduğundan geçişme gereği \(a \mid n\)’dir. Ayrıca \(a > 1\)’dir. Demek ki \(a \in D\)’dir ve \(a < p\)’dir — bu, \(p\)’nin \(D\)’nin en küçük elemanı olmasıyla çelişir.
O hâlde \(p\) asaldır ve \(n\)’nin bir bölenidir.
\(\blacksquare\)
9.5 Asal Sayılar Sonsuzdur
Teorem 9.2 (Öklid Teoremi) Sonsuz tane asal sayı vardır.
İspat
Aksini varsayalım: yalnızca sonlu sayıda asal sayı bulunsun ve bunların hepsi
\[p_1, p_2, \dots, p_n\]
olsun. Şimdi şu sayıyı tanımlayalım:
\[N = p_1 p_2 \cdots p_n + 1\]
Bütün \(p_i\)’ler \(2\)’den büyük veya eşit olduğundan \(N > 1\)’dir. Lemma 9.1 gereği \(N\) sayısının bir \(p\) asal böleni vardır.
Varsayımımıza göre bütün asallar listemizde olduğundan \(p = p_j\) olacak biçimde bir \(j\) vardır. Buradan iki bilgi çıkar:
- \(p = p_j\) çarpımın bir çarpanı olduğundan \(p \mid p_1 p_2 \cdots p_n\)’dir.
- \(p \mid N\)’dir.
Teorem 3.1 (7) gereği \(p\) sayısı farkı da böler:
\[p \ \mid \ N - p_1 p_2 \cdots p_n = 1\]
Ama \(p\) asal olduğundan \(p > 1\)’dir ve \(1\)’i bölemez. Çelişki.
O hâlde asal sayıların kümesi sonlu olamaz; sonsuz tane asal sayı vardır.
\(\blacksquare\)
İspat, “\(p_1 p_2 \cdots p_n + 1\) sayısı asaldır” demez — bu genel olarak yanlıştır. Örneğin
\[2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\]
bileşiktir. İspatın söylediği yalnızca şudur: bu sayının asal böleni, listedeki asalların hiçbiri olamaz. Listeyi sonlu kabul etmek işte bu yüzden çelişki üretir.
9.6 Eratosthenes Kalburu
Bir sayının asal olup olmadığını anlamak için bütün küçük sayıları denemek gerekmez. Aşağıdaki teorem, denenecek bölen sayısını çarpıcı biçimde azaltır.
Teorem 9.3 (Eratosthenes Kalburu) Asal olmayan her \(n > 1\) tam sayısının
\[p \leq \sqrt{n}\]
koşuluna uyan bir \(p\) asal böleni vardır.
İspat
\(1 < n\) asal olmayan bir tam sayı olsun. Bu durumda
\[n = k \cdot l, \qquad 1 < k \leq l < n\]
olacak biçimde \(k, l\) tam sayıları vardır. (Çarpanlardan küçük olanına \(k\) dedik; eşit olabilirler.)
\(1 < k\) olduğundan Lemma 9.1 gereği \(k\)’nın bir \(p\) asal böleni vardır. Teorem 3.1 (8) gereği
\[p \leq k\]
Ayrıca \(p \mid k\) ve \(k \mid n\) olduğundan geçişme gereği \(p \mid n\)’dir.
Son olarak \(p \leq k \leq l\) olduğundan
\[p^2 \leq k \cdot l = n\]
yazılır. Her iki tarafın karekökünü alırsak \(p \leq \sqrt{n}\) bulunur.
\(\blacksquare\)
Teoremin karşıt tersini almak, doğrudan bir asallık testi verir.
\(1 < n \in \mathbb{Z}\) olsun. Eğer \(n\) tam sayısının
\[p \leq \sqrt{n}\]
koşuluna uyan hiç \(p\) asal çarpanı yoksa, \(n\) asaldır.
Örnek 9.2 (\(101\) Asal mıdır?) \(101\) sayısının asal olduğunu gösteriniz.
Çözüm
\(\sqrt{101} \approx 10{,}05\) olduğundan, yalnızca \(10\)’u geçmeyen asalları denememiz yeterlidir:
\[2, \quad 3, \quad 5, \quad 7\]
Sırayla bakalım:
- \(101\) tektir, yani \(2 \nmid 101\).
- Rakamlar toplamı \(1 + 0 + 1 = 2\) olduğundan \(3 \nmid 101\).
- Son rakamı \(0\) veya \(5\) olmadığından \(5 \nmid 101\).
- \(101 = 7 \cdot 14 + 3\) olduğundan \(7 \nmid 101\).
\(\sqrt{101}\)’i geçmeyen hiçbir asal \(101\)’i bölmediğinden, Teorem 9.3 gereği \(101\) asaldır.
\(\blacksquare\)
Örnek 9.3 (\(10\) ile \(100\) Arasındaki Asallar) Eratosthenes kalburunu kullanarak \(10\) ile \(100\) arasındaki tüm asal sayıları belirleyiniz.
Çözüm
\(100\)’ü geçmeyen bir sayı bileşikse, \(\sqrt{100} = 10\)’u geçmeyen bir asal böleni vardır. O hâlde yalnızca
\[2, \quad 3, \quad 5, \quad 7\]
asallarının katlarını elemek yeterlidir.
1. Adım. \(10\) ile \(100\) arasındaki bütün sayıları yazıp \(2\)’nin katlarını (çift sayıları) eleyelim. Geriye yalnızca tek sayılar kalır.
2. Adım. Kalanlardan \(3\)’ün katlarını eleyelim: \(15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99\).
3. Adım. \(5\)’in katlarını eleyelim: \(25, 35, 55, 65, 85, 95\). (Diğerleri zaten elenmişti.)
4. Adım. \(7\)’nin katlarını eleyelim: \(49, 77, 91\). (Geri kalanları önceki adımlarda elenmişti.)
Elemeden sonra geriye kalan sayılar aranan asallardır:
\[11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 79,\ 83,\ 89,\ 97\]
Toplam \(21\) asal sayı vardır.
\(\blacksquare\)
9.7 Asalların Biçimi Üzerine
Örnek 9.4 (\(2\) ve \(3\) Dışındaki Asallar) \(2\) ve \(3\) dışındaki her asal sayının, \(k\) bir tam sayı olmak üzere \(6k + 1\) veya \(6k - 1\) biçiminde olduğunu gösteriniz.
Çözüm
\(p\) sayısı \(2\) ve \(3\)’ten farklı bir asal olsun. Bölme algoritmasına göre
\[p = 6q + r, \qquad r \in \{0, 1, 2, 3, 4, 5\}\]
yazılır. Kalanları tek tek eleyelim.
- \(r = 0\): \(p = 6q\) olur; \(2 \mid p\)’dir. \(p\) asal ve \(p \neq 2\) olduğundan bu imkânsızdır.
- \(r = 2\): \(p = 6q + 2 = 2(3q + 1)\) olur; yine \(2 \mid p\)’dir, imkânsız.
- \(r = 4\): \(p = 6q + 4 = 2(3q + 2)\) olur; yine \(2 \mid p\)’dir, imkânsız.
- \(r = 3\): \(p = 6q + 3 = 3(2q + 1)\) olur; \(3 \mid p\)’dir. \(p\) asal ve \(p \neq 3\) olduğundan imkânsız.
Geriye yalnızca \(r = 1\) ve \(r = 5\) kalır:
- \(r = 1\) ise \(p = 6q + 1\)’dir.
- \(r = 5\) ise \(p = 6q + 5 = 6(q+1) - 1\)’dir; yani \(p = 6k - 1\) biçimindedir.
\(\blacksquare\)
Her asal \(6k \pm 1\) biçimindedir, ama \(6k \pm 1\) biçimindeki her sayı asal değildir: \(25 = 6 \cdot 4 + 1\) ve \(35 = 6 \cdot 6 - 1\) bileşiktir.
Yine de bu gözlem asallık aramalarını altı kat hızlandırır: \(6k\), \(6k+2\), \(6k+3\), \(6k+4\) biçimindeki sayılara hiç bakmaya gerek yoktur.
Örnek 9.5 (\(2^n - 1\) Asalsa \(n\) Asaldır) Her \(n\) pozitif tam sayısı için, \(2^n - 1\) sayısı asalsa \(n\)’nin de asal olduğunu gösteriniz.
Çözüm
Karşıt tersini ispatlayacağız: \(n\) asal değilse \(2^n - 1\) de asal değildir.
\(n = 1\) ise \(2^1 - 1 = 1\) olur ve \(1\) asal değildir; iddia sağlanır. O hâlde \(n > 1\) ve \(n\) bileşik olsun. Bu durumda
\[n = a \cdot b, \qquad 1 < a < n\]
olacak biçimde tam sayılar vardır.
\(a \mid n\) olduğundan Örnek 3.7 gereği
\[2^{a} - 1 \ \mid \ 2^{n} - 1\]
Şimdi bu bölenin öz bir bölen olduğunu, yani \(1\)’den ve \(2^n - 1\)’in kendisinden farklı olduğunu görelim:
- \(a > 1\) olduğundan \(2^a - 1 \geq 2^2 - 1 = 3 > 1\)’dir.
- \(a < n\) olduğundan \(2^a - 1 < 2^n - 1\)’dir.
Demek ki \(2^n - 1\) sayısının \(1\) ile kendisinden farklı bir pozitif böleni vardır; yani asal değildir.
Karşıt ters ispatlandığından, \(2^n - 1\) asalsa \(n\) asaldır.
\(\blacksquare\)
\(n\) asal olduğunda \(2^n - 1\) asal olmak zorunda değildir. En küçük karşı örnek \(n = 11\)’dir:
\[2^{11} - 1 = 2048 - 1 = 2047 = 23 \cdot 89\]
\(2^p - 1\) biçimindeki asallara Mersenne asalları denir; bugün bilinen en büyük asal sayılar bu ailedendir.
Örnek 9.6 (\(p\) ile \(p^2+2\) Asalsa) \(p\) ve \(p^2 + 2\) birer asal sayı ise \(p^2 + 4\) sayısının da asal olduğunu gösteriniz.
Çözüm
Önce \(p\)’nin ne olabileceğini belirleyelim. \(p \neq 3\) olduğunu varsayalım ve çelişki arayalım.
\(p \neq 3\) asal olduğundan \(3 \nmid p\)’dir. Bölme algoritmasına göre \(p = 3q + r\), \(r \in \{1, 2\}\) yazılır (kalan \(0\) olamaz, çünkü \(3 \nmid p\)). Her iki durumda karesini hesaplayalım:
- \(p = 3q + 1\) ise \(p^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1\).
- \(p = 3q + 2\) ise \(p^2 = 9q^2 + 12q + 4 = 3(3q^2 + 4q + 1) + 1\).
Her iki durumda da \(p^2\) sayısı \(3k + 1\) biçimindedir. O hâlde
\[p^2 + 2 = 3k + 3 = 3(k+1)\]
olur; yani \(3 \mid p^2 + 2\)’dir. Ayrıca \(p \geq 2\) olduğundan \(p^2 + 2 \geq 6 > 3\)’tür. Demek ki \(p^2 + 2\) sayısı, \(1\) ile kendisinden farklı olan \(3\) böleni tarafından bölünmektedir; asal olamaz. Bu, hipotezle çelişir.
O hâlde \(p = 3\) olmak zorundadır. Şimdi doğrulayalım:
\[p^2 + 2 = 11 \quad (\text{asal}), \qquad p^2 + 4 = 13 \quad (\text{asal})\]
Böylece \(p^2 + 4\) asaldır.
\(\blacksquare\)
9.8 Çalışma Problemleri
Alıştırma 9.1 (Asallığın Bir Karakterizasyonu) \(1 < n \in \mathbb{Z}\) olsun ve
\[\text{"her } a, b \in \mathbb{Z} \text{ için } n \mid ab \text{ ise } n \mid a \text{ veya } n \mid b \text{"}\]
koşulunun sağlandığı varsayılsın. Bu durumda \(n\)’nin bir asal sayı olduğunu ispatlayınız.
İpucu: \(n\) bileşik olsaydı \(n = ab\), \(1 < a, b < n\) yazılabilirdi; koşulu bu \(a\) ile \(b\)’ye uygulayınız.
Alıştırma 9.2 (Asal Sayı ve Binom Katsayıları) \(p\) bir asal sayı olmak üzere, her \(k \in \{1, \dots, p-1\}\) için
\[p \ \Big| \ \binom{p}{k}\]
olduğunu gösteriniz.
İpucu: \(k! \, (p-k)! \, \dbinom{p}{k} = p!\) eşitliğinden yola çıkınız. \(p\) asal olduğundan ve \(k!\) ile \((p-k)!\) çarpanlarının hepsi \(p\)’den küçük olduğundan Sonuç 9.2 gereği \(p \nmid k!\,(p-k)!\)’dir; ardından Teorem 5.1’nı uygulayınız.
Alıştırma 9.3 (Faktöriyelin Komşularındaki Asallar) a) Her \(2 < n\) tam sayısı için \(n < p < n!\) koşuluna uyan bir \(p\) asal sayısının var olduğunu gösteriniz.
b) Her \(1 < n\) tam sayısı için, \(n! + 1\) sayısının her asal çarpanının \(n\)’den büyük bir tek sayı olduğunu gösteriniz.
İpucu (a): \(n! - 1\) sayısının bir asal bölenini alıp, bu bölenin \(n\)’yi geçmesi gerektiğini gösteriniz.
Alıştırma 9.4 (\(2^n + 1\) Ne Zaman Asal Olabilir?) a) Her \(n\) pozitif tam sayısı ve her \(k\) negatif olmayan tam sayısı için
\[n + 1 \ \mid \ n^{2k+1} + 1\]
olduğunu tümevarımla gösteriniz.
b) \(2^n + 1\) sayısı asal ise \(n = 2^k\) olacak biçimde negatif olmayan bir \(k\) tam sayısının var olduğunu gösteriniz.
c) (b) şıkkının tersinin yanlış olduğunu \(n = 32\) için gösteriniz. (İpucu: \(2^{32} + 1 = 641 \cdot 6700417\).)
Alıştırma 9.5 (\(4k+3\) Biçimindeki Asallar) a) \(4k+1\) biçimindeki sonlu sayıda tam sayının çarpımının yine \(4k+1\) biçiminde olduğunu gösteriniz.
b) \(4k + 3\) biçiminde sonsuz sayıda asal sayı olduğunu ispatlayınız.
İpucu (b): Sonlu sayıda olduklarını varsayıp \(q_1, \dots, q_n\) diyelim ve \(N = 4 q_1 q_2 \cdots q_n - 1\) sayısını inceleyiniz; (a) şıkkı bu sayının \(4k+3\) biçiminde bir asal böleni olması gerektiğini söyler.