5 Öklid Lemması ve Aralarında Asallık
Bézout teoremi elimize güçlü bir alet verdi: aralarında asal iki sayının doğrusal birleşimiyle \(1\) elde edilebiliyor. Bu bölümde bu aletin ne kadar iş gördüğünü göreceğiz. Elde edeceğimiz teoremler — özellikle Öklid lemması — aritmetiğin esas teoreminin ispatında ve kongrüans hesaplarında sürekli karşımıza çıkacak.
5.1 Sadeleştirme
En büyük ortak bölene bölmek, iki sayıyı aralarında asal hâle getirir. Bu basit gözlem, kesirlerin “en sade biçimi” fikrinin arkasındaki matematiktir.
Sonuç 5.1 (EBOB’a Bölmek Aralarında Asal Yapar) \(a\) ve \(b\) ikisi birden sıfır olmayan tam sayılar olsun ve \(d = \gcd(a,b)\) biçiminde tanımlansın. Bu durumda
\[\gcd\left( \frac{a}{d}, \ \frac{b}{d} \right) = 1\]
İspat
\(d \mid a\) ve \(d \mid b\) olduğundan \(a/d\) ile \(b/d\) birer tam sayıdır; ifadenin anlamlı olduğunu böylece belirlemiş olduk.
Bézout teoremi gereği
\[d = ax + by\]
olacak biçimde \(x, y\) tam sayıları vardır. \(d \neq 0\) olduğundan her iki tarafı \(d\)’ye bölelim:
\[1 = \frac{a}{d}\,x + \frac{b}{d}\,y\]
Sağ tarafta \(a/d\) ile \(b/d\) tam sayılarının bir doğrusal birleşimi vardır ve değeri \(1\)’dir. Sonuç 4.3 gereği bu iki sayı aralarında asaldır.
\(\blacksquare\)
Sonuç 5.2 (Kesirlerin En Sade Biçimi) Her \(\alpha\) rasyonel sayısı için
\[\alpha = \frac{a}{b}, \qquad b > 0, \qquad \gcd(a,b) = 1\]
olacak biçimde \(a, b\) tam sayıları vardır.
İspat
\(\alpha\) rasyonel olduğundan \(\alpha = m/n\) olacak biçimde \(m, n \in \mathbb{Z}\), \(n \neq 0\) vardır. Gerekirse pay ve paydayı \(-1\) ile çarparak \(n > 0\) olduğunu varsayabiliriz.
\(d = \gcd(m, n)\) diyelim ve
\[a := \frac{m}{d}, \qquad b := \frac{n}{d}\]
tanımlayalım. Bunlar birer tam sayıdır; ayrıca \(d > 0\) ve \(n > 0\) olduğundan \(b > 0\)’dır. Kesri sadeleştirirsek
\[\frac{a}{b} = \frac{m/d}{n/d} = \frac{m}{n} = \alpha\]
bulunur. Son olarak Sonuç 5.1 gereği \(\gcd(a,b) = 1\)’dir.
\(\blacksquare\)
Örnek 5.1 (\(\sqrt{2}\) İrrasyoneldir) \(\sqrt{2}\) sayısının rasyonel olmadığını gösteriniz.
Çözüm
Aksini varsayalım: \(\sqrt{2}\) rasyonel olsun. Sonuç 5.2 gereği
\[\sqrt{2} = \frac{a}{b}, \qquad b > 0, \qquad \gcd(a,b) = 1\]
olacak biçimde \(a, b\) tam sayıları vardır. Her iki tarafın karesini alıp paydadan kurtulalım:
\[2 = \frac{a^2}{b^2} \implies a^2 = 2b^2 \tag{$\ast$}\]
1. \(a\) çifttir. \((\ast)\) eşitliği \(a^2\) sayısının çift olduğunu söyler. Eğer \(a\) tek olsaydı, tek sayıların çarpımı tek olacağından \(a^2\) de tek olurdu. O hâlde \(a\) çifttir; yani \(a = 2k\) olacak biçimde bir \(k \in \mathbb{Z}\) vardır.
2. \(b\) de çifttir. \(a = 2k\) değerini \((\ast)\)’da yerine koyalım:
\[(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2\]
Aynı akıl yürütmeyle \(b^2\) çift, dolayısıyla \(b\) de çifttir.
3. Çelişki. \(a\) ile \(b\)’nin ikisi de çift olduğundan \(2\) sayısı ikisinin de bir ortak bölenidir; yani
\[2 \mid \gcd(a,b) = 1\]
olur. Bu imkânsızdır.
Çelişki, \(\sqrt{2}\)’nin rasyonel olduğu varsayımından doğmuştur. O hâlde \(\sqrt{2}\) irrasyoneldir.
\(\blacksquare\)
Yukarıdaki ispatın işlemesinin tek nedeni, kesri en sade biçimde yazmış olmamızdır. \(\gcd(a,b) = 1\) kabulü olmasaydı “\(a\) ile \(b\) çifttir” sonucu bir çelişki üretmez, yalnızca kesri sadeleştirmemiz gerektiğini söylerdi. Bu teknik ileride \(\sqrt{p}\) sayılarının irrasyonelliğini gösterirken de aynen tekrarlanacaktır.
5.2 Öklid Lemması
Şimdi bölümün merkezindeki teoreme geliyoruz. “\(a\) bir çarpımı bölüyorsa çarpanlardan birini böler” önermesinin genel olarak yanlış olduğunu görmüştük (\(6 \mid 2 \cdot 3\) ama \(6 \nmid 2\) ve \(6 \nmid 3\)). Öklid lemması, doğru olması için gereken ek koşulu tam olarak söyler.
Teorem 5.1 (Öklid Lemması) \(a, b, c \in \mathbb{Z}\) olsun. Eğer
\[a \mid bc \qquad \text{ve} \qquad \gcd(a,b) = 1\]
ise \(a \mid c\)’dir.
İspat
\(\gcd(a,b) = 1\) olduğundan Sonuç 4.3 gereği
\[1 = ax + by\]
olacak biçimde \(x, y\) tam sayıları vardır. Her iki tarafı \(c\) ile çarpalım:
\[c = acx + bcy\]
Sağ taraftaki iki terimi ayrı ayrı inceleyelim:
- \(acx = a(cx)\) olduğundan \(a \mid acx\)’tir.
- Hipotez gereği \(a \mid bc\)’dir; Teorem 3.1 (11) gereği \(a \mid bcy\)’dir.
Teorem 3.1 (7) gereği \(a\) sayısı bu ikisinin toplamını da böler:
\[a \mid acx + bcy = c\]
\(\blacksquare\)
\(a = 6\), \(b = 2\), \(c = 3\) alalım. \(6 \mid 2 \cdot 3\) doğrudur, ama \(6 \nmid 3\)’tür. Lemma bozulmuş değildir: burada \(\gcd(6, 2) = 2 \neq 1\)’dir.
Öklid lemmasının en çok kullanılan hâli, \(a\)’nın asal olduğu durumdur; bir asal sayı, bölmediği her sayıyla aralarında asal olduğundan koşul kendiliğinden sağlanır. Bu özel hâli asal sayılar bölümünde ayrıca ele alacağız.
Teorem 5.2 (İki Bölenin Çarpımı) \(a, b, c \in \mathbb{Z}\) olsun. Eğer
\[a \mid c, \qquad b \mid c, \qquad \gcd(a,b) = 1\]
ise \(ab \mid c\)’dir.
İspat
\(a \mid c\) olduğundan
\[c = a s\]
olacak biçimde bir \(s \in \mathbb{Z}\) vardır. Hipotez gereği \(b \mid c = as\)’tir.
Şimdi Öklid lemmasını \(b\), \(a\) ve \(s\) sayılarına uygulayalım: \(b \mid as\) ve \(\gcd(b,a) = 1\) olduğundan
\[b \mid s\]
bulunur. O hâlde \(s = bt\) olacak biçimde bir \(t \in \mathbb{Z}\) vardır. Bunu ilk eşitlikte yerine koyalım:
\[c = as = a(bt) = (ab)\,t\]
\(t\) bir tam sayı olduğundan \(ab \mid c\)’dir.
\(\blacksquare\)
Bu teorem, sayılar teorisi problemlerinde en sık kullanılan “birleştirme kuralıdır”. Bir sayının \(24\) ile bölündüğünü göstermek istiyorsak, doğrudan \(24\) ile uğraşmak yerine
\[24 = 3 \cdot 8, \qquad \gcd(3, 8) = 1\]
yazıp \(3\) ile ve \(8\) ile bölünmeyi ayrı ayrı gösteririz. Aşağıdaki örnekler bu stratejinin uygulamalarıdır.
Kuralın aralarında asallık koşulu olmadan çalışmadığına dikkat ediniz: \(4 \mid 12\) ve \(6 \mid 12\) olmasına rağmen \(24 \nmid 12\)’dir; çünkü \(\gcd(4,6) = 2 \neq 1\)’dir.
Teorem 5.3 (Çarpımla Aralarında Asallık) \(a, b, c \in \mathbb{Z}\) olsun. Eğer
\[\gcd(a,b) = 1 \qquad \text{ve} \qquad \gcd(a,c) = 1\]
ise \(\gcd(a, bc) = 1\)’dir.
İspat
Sonuç 4.3 gereği
\[1 = ax + by, \qquad 1 = au + cv\]
olacak biçimde \(x, y, u, v\) tam sayıları vardır. İki eşitliği taraf tarafa çarpalım:
\[1 = (ax + by)(au + cv) = a^2 xu + acxv + abyu + bcyv\]
İlk üç terimde \(a\) ortak çarpandır; onları gruplayalım:
\[1 = a\big( axu + cxv + byu \big) + (bc)\,\big( yv \big)\]
Böylece \(1\) sayısını \(a\) ile \(bc\)’nin bir doğrusal birleşimi olarak yazdık. Sonuç 4.3 gereği \(\gcd(a, bc) = 1\)’dir.
\(\blacksquare\)
Sonuç 5.3 (Kuvvetlerle Aralarında Asallık) \(a, b \in \mathbb{Z}\) ve \(\gcd(a,b) = 1\) olsun. Bu durumda her \(m, n\) pozitif tam sayısı için
\[\gcd\left( a^{m},\, b^{n} \right) = 1\]
İspat
Önce sabit bir \(a\) için \(\gcd(a, b^n) = 1\) olduğunu \(n\) üzerinden tümevarımla gösterelim.
Başlangıç adımı (\(n = 1\)). \(\gcd(a, b) = 1\) hipotezdir.
Tümevarım adımı. \(\gcd(a, b^k) = 1\) olduğunu varsayalım. Elimizde
\[\gcd(a, b) = 1 \qquad \text{ve} \qquad \gcd(a, b^{k}) = 1\]
vardır. Teorem 5.3 gereği
\[\gcd\left( a, \ b \cdot b^{k} \right) = \gcd\left( a, b^{k+1} \right) = 1\]
bulunur. Tümevarım gereği her \(n\) için \(\gcd(a, b^n) = 1\)’dir.
Şimdi \(b^n\) sayısını sabit tutup aynı akıl yürütmeyi \(a\) için tekrarlayalım: \(\gcd(b^n, a) = 1\) olduğundan, yukarıdaki sonucu \(a\) ile \(b^n\)’nin rollerini değiştirerek uygularsak
\[\gcd\left( b^{n}, a^{m} \right) = 1\]
elde edilir. En büyük ortak bölen sıralamadan bağımsız olduğundan \(\gcd(a^m, b^n) = 1\)’dir.
\(\blacksquare\)
5.3 Bölünebilme İddialarını Birleştirme
Örnek 5.2 (\(6 \mid n(n+1)(n+2)\)) Her \(n\) tam sayısı için \(6 \mid n(n+1)(n+2)\) olduğunu gösteriniz.
Çözüm
\(6 = 2 \cdot 3\) ve \(\gcd(2,3) = 1\) olduğundan, Teorem 5.2 gereği çarpımın hem \(2\) hem de \(3\) ile bölündüğünü göstermek yeterlidir.
\(2\) ile bölünme. Örnek 3.2 (a) gereği \(2 \mid n(n+1)\)’dir; dolayısıyla \(2\) sayısı \(n(n+1)(n+2)\) çarpımını da böler.
\(3\) ile bölünme. Örnek 3.2 (b) gereği \(3 \mid n(n+1)(n+2)\)’dir.
\(2 \mid n(n+1)(n+2)\), \(3 \mid n(n+1)(n+2)\) ve \(\gcd(2,3) = 1\) olduğundan
\[2 \cdot 3 = 6 \ \mid \ n(n+1)(n+2)\]
bulunur.
\(\blacksquare\)
Örnek 5.3 (Tek Sayılarda \(24 \mid a(a^2 - 1)\)) Her \(a\) tek tam sayısı için \(24 \mid a(a^2 - 1)\) olduğunu gösteriniz.
Çözüm
\(24 = 3 \cdot 8\) ve \(\gcd(3, 8) = 1\) olduğundan, Teorem 5.2 gereği \(3 \mid a(a^2-1)\) ve \(8 \mid a(a^2-1)\) olduğunu ayrı ayrı göstermek yeterlidir.
\(3\) ile bölünme. İfadeyi çarpanlarına ayıralım:
\[a(a^2 - 1) = a(a-1)(a+1) = (a-1)\,a\,(a+1)\]
Bu, ardışık üç tam sayının çarpımıdır; Örnek 3.2 (b) gereği \(3\) ile bölünür.
\(8\) ile bölünme. \(a\) tek olduğundan Örnek 2.3 gereği \(a^2 = 8k + 1\) olacak biçimde bir \(k\) tam sayısı vardır. Buradan
\[a^2 - 1 = 8k\]
bulunur; yani \(8 \mid a^2 - 1\)’dir. O hâlde \(8\) sayısı \(a(a^2-1)\) çarpımını da böler.
Birleştirme. \(3 \mid a(a^2-1)\), \(8 \mid a(a^2-1)\) ve \(\gcd(3,8) = 1\) olduğundan
\[3 \cdot 8 = 24 \ \mid \ a(a^2 - 1)\]
bulunur.
\(\blacksquare\)
Örnek 5.4 (\(6 \mid a(a^2 + 11)\)) Her \(a\) tam sayısı için \(6 \mid a(a^2 + 11)\) olduğunu gösteriniz.
Çözüm
İfadeyi, bölünebilirliğini bildiğimiz bir yapıya indirgeyelim:
\[a(a^2 + 11) = a^3 + 11a = (a^3 - a) + 12a = (a-1)\,a\,(a+1) + 12a\]
Sağ taraftaki iki terimi ayrı ayrı ele alalım.
- Örnek 5.2 gereği ardışık üç tam sayının çarpımı \(6\) ile bölünür: \(6 \mid (a-1)a(a+1)\).
- \(12a = 6 \cdot (2a)\) olduğundan \(6 \mid 12a\)’dır.
Teorem 3.1 (7) gereği \(6\) sayısı toplamı da böler:
\[6 \ \mid \ (a-1)a(a+1) + 12a = a(a^2 + 11)\]
\(\blacksquare\)
Örnek 5.5 (\(6 \mid n(7n^2 + 5)\)) Her \(n\) tam sayısı için \(6 \mid n(7n^2 + 5)\) olduğunu gösteriniz.
Çözüm
İfadeyi açalım ve \(6\)’nın katlarını ayıklayalım:
\[ \begin{aligned} n(7n^2 + 5) &= 7n^3 + 5n \\ &= 6n^3 + n^3 + 6n - n \\ &= 6\left( n^3 + n \right) + \left( n^3 - n \right) \\ &= 6\left( n^3 + n \right) + (n-1)\,n\,(n+1) \end{aligned} \]
Sağ taraftaki iki terime bakalım:
- İlk terim \(6\)’nın açık bir katıdır.
- Örnek 5.2 gereği ardışık üç tam sayının çarpımı \(6\) ile bölünür.
O hâlde \(6\) sayısı toplamı da böler:
\[6 \mid n(7n^2 + 5)\]
\(\blacksquare\)
5.4 Kuvvetler ve Bölünebilme
Örnek 5.6 (\(a \mid b \iff a^n \mid b^n\)) \(n\) sabit bir pozitif tam sayı olmak üzere, her \(a, b\) tam sayısı için
\[a \mid b \iff a^{n} \mid b^{n}\]
olduğunu gösteriniz.
Çözüm
(\(\Rightarrow\)) \(a \mid b\) olsun; \(b = ax\) olacak biçimde bir \(x \in \mathbb{Z}\) vardır. Her iki tarafın \(n\)’inci kuvvetini alalım:
\[b^{n} = (ax)^{n} = a^{n} x^{n}\]
\(x^n\) bir tam sayı olduğundan \(a^n \mid b^n\)’dir.
(\(\Leftarrow\)) \(a^n \mid b^n\) olsun. \(a = 0\) ise \(a^n = 0\) olur ve Teorem 3.1 (3) gereği \(b^n = 0\), yani \(b = 0\) olur; bu durumda \(a \mid b\) sağlanır. O hâlde \(a \neq 0\) varsayabiliriz. Benzer biçimde \(b = 0\) ise \(a \mid 0\) zaten doğrudur; \(b \neq 0\) da varsayalım.
\(d := \gcd(a,b)\) diyelim ve
\[a = d a', \qquad b = d b'\]
yazalım. Sonuç 5.1 gereği \(\gcd(a', b') = 1\)’dir. Hipotezi bu yazılımla ifade edelim:
\[d^{n} (a')^{n} \ \mid \ d^{n} (b')^{n}\]
\(d \neq 0\) olduğundan Teorem 3.1 (12) gereği \(d^n\) çarpanını sadeleştirebiliriz:
\[(a')^{n} \ \mid \ (b')^{n}\]
Öte yandan \(\gcd(a', b') = 1\) olduğundan Sonuç 5.3 gereği
\[\gcd\left( (a')^{n}, (b')^{n} \right) = 1\]
olur. Bir sayı hem \((b')^n\)’i bölüyor hem de onunla aralarında asal ise, kendisiyle \(1\)’in ortak bölenidir:
\[(a')^{n} \ \mid \ \gcd\left( (a')^n, (b')^n \right) = 1\]
Buradan \((a')^n = \pm 1\), dolayısıyla \(a' = \pm 1\) bulunur. O hâlde
\[a = d a' = \pm d\]
olur. \(d = \gcd(a,b) \mid b\) olduğundan Teorem 3.1 (13) gereği \(a = \pm d\) sayısı da \(b\)’yi böler:
\[a \mid b\]
\(\blacksquare\)
5.5 Çalışma Problemleri
Alıştırma 5.1 (Aralarında Asallığın Taşınması) \(a, b, c\) tam sayıları için aşağıdakileri gösteriniz.
a) \(\gcd(a,b) = 1\) ise \(\gcd(c, b) = \gcd(ac, b)\)’dir.
b) \(\gcd(a,b) = 1\) ve \(c \mid a - b\) ise \(\gcd(a, c) = 1\)’dir.
c) \(c \mid a\) ve \(\gcd(a,b) = 1\) ise \(\gcd(c, b) = 1\)’dir.
İpucu (b): \(d = \gcd(a,c)\) diyerek \(d \mid a - (a-b)\) hesabını yapınız.
Alıştırma 5.2 (Bölünebilme İddialarını Birleştirme) Aşağıdakileri ispatlayınız.
a) Her \(n\) tam sayısı için \(30 \mid n^5 - n\).
b) Her \(n\) tam sayısı için \(12 \mid n^4 - n^2\).
c) Her \(n\) tek tam sayısı için \(48 \mid n^3 - n\) olduğu doğru mudur? Değilse doğru olan en büyük sabiti bulunuz.
Alıştırma 5.3 (EBOB ve EKOK Arasında) \(a, b\) sıfırdan farklı tam sayılar ve \(c\) herhangi bir tam sayı olsun. Eğer \(a \mid c\) ve \(b \mid c\) ise, \(\gcd(a,b) = d\) olmak üzere
\[\frac{ab}{d} \ \Big| \ c\]
olduğunu gösteriniz.
İpucu: \(a = da'\), \(b = db'\) yazıp Sonuç 5.1 ile Teorem 5.2’ı birlikte kullanınız. (Bir sonraki bölümde \(ab/d\) sayısının \(a\) ile \(b\)’nin en küçük ortak katı olduğunu göreceğiz.)