2 Bölme Algoritması
İlkokuldan beri bildiğimiz “bölme işlemi” aslında bir teoremdir: verilen iki tam sayı için bölüm ve kalanın var olduğu ve tek türlü belirli olduğu ispatlanması gereken bir olgudur. Bu bölümde bu teoremi iyi sıralama prensibinden çıkaracak ve sayılar teorisinin en çok kullanılan ispat tekniklerinden birini — kalanlara göre durum ayırmayı — kuracağız.
2.1 Kalanlı Bölme
Teorem 2.1 (Bölme Algoritması) \(a, b \in \mathbb{Z}\) ve \(a > 0\) olsun. Bu durumda
\[b = aq + r, \qquad 0 \leq r < a\]
olacak biçimde tek türlü belirli \(q\) ve \(r\) tam sayıları vardır.
İspat
İspatı iki parçaya ayıralım.
1. Varlık. Aşağıdaki kümeyi tanımlayalım:
\[S = \{ b - ak \ : \ k \in \mathbb{Z}, \ b - ak \geq 0 \}\]
Önce \(S\) kümesinin boş olmadığını gösterelim. \(1 \leq a\) olduğundan \(|b| \leq a|b|\)’dir. \(k = -|b|\) seçelim:
\[b - a(-|b|) = b + a|b| \geq b + |b| \geq 0\]
Demek ki \(b + a|b| \in S\)’dir; yani \(S\) boş kümeden farklıdır. Ayrıca tanımı gereği \(S \subseteq \mathbb{N} \cup \{0\}\)’dır.
Sonuç 1.1 gereği \(S\) kümesinin bir en küçük elemanı vardır; buna \(r\) diyelim. \(r \in S\) olduğundan
\[r = b - aq \qquad \text{yani} \qquad b = aq + r\]
olacak biçimde bir \(q \in \mathbb{Z}\) vardır. Geriye \(0 \leq r < a\) olduğunu göstermek kalıyor.
\(r \in S\) olduğundan \(0 \leq r\)’dir. Şimdi \(a \leq r\) olduğunu varsayalım ve çelişki arayalım:
\[0 \leq r - a = b - aq - a = b - a(q+1)\]
Bu, \(r - a\) sayısının da \(S\) kümesine ait olduğunu söyler. Oysa \(a > 0\) olduğundan \(r - a < r\)’dir; bu da \(r\)’nin \(S\)’nin en küçük elemanı olmasıyla çelişir. O hâlde \(r < a\)’dır.
2. Teklik. Aynı koşulları sağlayan iki yazılış olduğunu varsayalım:
\[b = aq + r = aq' + r', \qquad 0 \leq r,\, r' < a\]
Her iki eşitsizlikten
\[0 \leq r' < a \quad \text{ve} \quad -a < -r \leq 0\]
yazılır; taraf tarafa toplarsak
\[-a < r' - r < a \qquad \text{yani} \qquad |r' - r| < a\]
elde edilir. Öte yandan \(aq + r = aq' + r'\) eşitliğinden
\[a(q - q') = r' - r\]
bulunur. Mutlak değer alalım:
\[a \cdot |q - q'| = |r' - r| < a\]
Her iki tarafı \(a > 0\)’a bölersek \(|q - q'| < 1\) olur. Ama \(q - q'\) bir tam sayıdır ve mutlak değeri \(1\)’den küçük olan tek tam sayı \(0\)’dır. O hâlde
\[q = q' \qquad \text{ve buradan} \qquad r = b - aq = b - aq' = r'\]
bulunur; yazılış tek türlü belirlidir.
\(\blacksquare\)
Tanım 2.1 (Bölüm ve Kalan) Bölme algoritmasındaki \(q\) ve \(r\) sayılarına sırasıyla, \(b\)’nin \(a\) ile bölünmesinden elde edilen bölüm ve kalan denir.
Tanımın en sık gözden kaçan yanı, kalanın \(0 \leq r < a\) aralığında olmak zorunda olmasıdır. Negatif sayılarda bu, alışkanlıklarımızı zorlayabilir: \(-48\) sayısını \(21\)’e bölerken “\(-48 = 21 \cdot (-2) - 6\)” yazmak matematiksel olarak doğru bir eşitliktir ama bölme algoritmasının verdiği yazılış değildir; çünkü \(-6 < 0\)’dır. Doğru yazılış, bölümü bir azaltıp kalanı \(21\) artırarak elde edilir.
Örnek 2.1 (Pozitif Bölenle Bölme) Aşağıdaki \(a, b\) tam sayı çiftleri için \(b = aq + r\), \(0 \leq r < a\) koşulunu sağlayan \(q\) ve \(r\) sayılarını bulunuz.
a) \(b = 56, \ a = 13\) b) \(b = -48, \ a = 21\)
Çözüm
a) \(13\)’ün katları \(13, 26, 39, 52, 65, \dots\) biçiminde ilerler. \(56\)’yı geçmeyen en büyüğü \(52 = 13 \cdot 4\)’tür:
\[56 = 13 \cdot 4 + 4, \qquad 0 \leq 4 < 13\]
Yani \(q = 4\), \(r = 4\)’tür.
b) Kalanın negatif olmaması gerektiğine dikkat edelim. \(21\)’in katları arasında \(-48\)’i geçmeyen en büyüğünü ararız:
\[21 \cdot (-2) = -42 > -48, \qquad 21 \cdot (-3) = -63 \leq -48\]
O hâlde \(q = -3\) alınmalıdır:
\[-48 = 21 \cdot (-3) + 15, \qquad 0 \leq 15 < 21\]
Yani \(q = -3\), \(r = 15\)’tir.
\(\blacksquare\)
Bölme algoritmasında bölenin pozitif olması istenmişti. Bölen negatif olduğunda da benzer bir sonuç geçerlidir; tek değişiklik, kalanın \(|a|\) ile sınırlanmasıdır.
Sonuç 2.1 (Negatif Bölenle Bölme) \(a, b \in \mathbb{Z}\) ve \(a \neq 0\) olsun. Bu durumda
\[b = aq + r, \qquad 0 \leq r < |a|\]
olacak biçimde tek türlü belirli \(q\) ve \(r\) tam sayıları vardır.
İspat
\(a > 0\) ise \(|a| = a\) olduğundan iddia Teorem 2.1 ile aynıdır; ispatlanacak bir şey yoktur.
\(a < 0\) olsun. Bu durumda \(|a| = -a > 0\)’dır. Bölme algoritmasını \(b\) ile pozitif \(|a|\) sayısına uygulayalım:
\[b = |a| \cdot q' + r, \qquad 0 \leq r < |a|\]
olacak biçimde tek türlü belirli \(q', r\) tam sayıları vardır. Burada \(|a| = -a\) yazarsak
\[b = (-a)q' + r = a(-q') + r\]
elde edilir. O hâlde \(q = -q'\) ve \(r\) aranan sayılardır.
Teklik. \(b = aq + r = aq'' + r''\) ve \(0 \leq r, r'' < |a|\) olsun. Yukarıdaki gibi \(a(q - q'') = r'' - r\) ve \(|r'' - r| < |a|\) yazılır. Mutlak değer alındığında
\[|a| \cdot |q - q''| = |r'' - r| < |a|\]
olur; buradan \(|q - q''| < 1\), yani \(q = q''\) ve dolayısıyla \(r = r''\) bulunur.
\(\blacksquare\)
Örnek 2.2 (Negatif Bölenle Bölme) Aşağıdaki \(a, b\) tam sayı çiftleri için \(b = aq + r\), \(0 \leq r < |a|\) koşulunu sağlayan \(q\) ve \(r\) sayılarını bulunuz.
a) \(b = 62, \ a = -13\) b) \(b = -48, \ a = -14\)
Çözüm
a) Önce \(|a| = 13\) ile bölelim: \(62 = 13 \cdot 4 + 10\). Şimdi \(13 = -(-13)\) yazımıyla bölümün işaretini çevirelim:
\[62 = (-13) \cdot (-4) + 10, \qquad 0 \leq 10 < 13\]
Yani \(q = -4\), \(r = 10\)’dur.
b) Önce \(|a| = 14\) ile bölelim. \(14\)’ün katları arasında \(-48\)’i geçmeyen en büyüğü \(14 \cdot (-4) = -56\)’dır:
\[-48 = 14 \cdot (-4) + 8\]
İşareti çevirelim:
\[-48 = (-14) \cdot 4 + 8, \qquad 0 \leq 8 < 14\]
Yani \(q = 4\), \(r = 8\)’dir.
\(\blacksquare\)
2.2 Çift ve Tek Sayılar
Bölme algoritmasının en basit özel hâli \(a = 2\) durumudur: her tam sayı \(2\)’ye bölündüğünde ya \(0\) ya da \(1\) kalanını verir. Bu, tam sayıları iki sınıfa ayırır.
Tanım 2.2 (Çift ve Tek Tam Sayı) \(a\) bir tam sayı olsun. \(a\)’nın \(2\) ile bölümünden elde edilen kalan \(0\) ise \(a\)’ya çift, \(1\) ise tek tam sayı denir.
Bir başka deyişle \(a\) çift ise \(a = 2k\), tek ise \(a = 2k + 1\) olacak biçimde bir \(k \in \mathbb{Z}\) vardır.
Bölme algoritmasındaki kalanın tek türlü belirli olması, doğrudan şu sonucu verir: her tam sayı ya tektir ya da çifttir; hiçbir tam sayı hem tek hem çift olamaz.
Önerme 2.1 (Toplamın Pariteleri) İki çift tam sayının toplamı çifttir. İki tek tam sayının toplamı da çifttir. Bir tek sayı ile bir çift sayının toplamı ise tektir.
İspat
Üç durumu ayrı ayrı ele alalım.
1. Çift \(+\) çift. \(a = 2k\) ve \(b = 2m\) olsun (\(k, m \in \mathbb{Z}\)). O hâlde
\[a + b = 2k + 2m = 2(k + m)\]
olur. \(k + m\) bir tam sayı olduğundan \(a + b\) çifttir.
2. Tek \(+\) tek. \(a = 2k + 1\) ve \(b = 2m + 1\) olsun. Bu durumda
\[a + b = (2k+1) + (2m+1) = 2k + 2m + 2 = 2(k + m + 1)\]
bulunur; \(k + m + 1\) tam sayı olduğundan \(a + b\) çifttir.
3. Tek \(+\) çift. \(a = 2k + 1\) ve \(b = 2m\) olsun. O hâlde
\[a + b = 2k + 1 + 2m = 2(k + m) + 1\]
olur. \(k + m\) tam sayı olduğundan \(a + b\), \(2\) ile bölündüğünde \(1\) kalanını verir; yani tektir.
\(\blacksquare\)
2.3 Kalanlara Göre Durum Ayırma
Sayılar teorisinin en verimli tekniklerinden biri şudur: bir iddiayı bütün tam sayılar için ispatlamak yerine, sayıyı uygun bir \(a\) ile bölüp kalanına göre sonlu sayıda duruma ayırırız. Kalan yalnızca \(0, 1, \dots, a-1\) değerlerini alabileceğinden, sonsuz bir iddia sonlu sayıda hesaba indirgenir.
Örnek 2.3 (Tek Sayıların Kareleri) Her \(n\) tek tam sayısı için \(n^2\) sayısının \(8\) ile bölümünden kalanın \(1\) olduğunu ispatlayınız.
Çözüm
Bölme algoritmasına göre \(n = 4k + r\), \(0 \leq r < 4\) olacak biçimde \(k, r\) tam sayıları vardır; yani \(r \in \{0, 1, 2, 3\}\)’tür.
\(n\) tek olduğundan \(r\) da tek olmalıdır: \(r = 0\) ya da \(r = 2\) olsaydı \(n = 4k\) veya \(n = 4k+2 = 2(2k+1)\) çift olurdu. Demek ki
\[n = 4k + 1 \qquad \text{veya} \qquad n = 4k + 3\]
biçimindedir. İki durumu da hesaplayalım.
Durum 1: \(n = 4k + 1\).
\[n^2 = 16k^2 + 8k + 1 = 8\underbrace{(2k^2 + k)}_{\in \mathbb{Z}} + 1\]
Durum 2: \(n = 4k + 3\).
\[n^2 = 16k^2 + 24k + 9 = 16k^2 + 24k + 8 + 1 = 8\underbrace{(2k^2 + 3k + 1)}_{\in \mathbb{Z}} + 1\]
Her iki durumda da \(n^2\) sayısı \(8m + 1\) biçimindedir ve \(0 \leq 1 < 8\) olduğundan bölme algoritmasının tekliği gereği kalan tam olarak \(1\)’dir.
\(\blacksquare\)
Örnek 2.4 (Karelerin Üçe Bölümünden Kalan) Her \(a\) tam sayısı için \(a^2\) sayısının, \(k\) bir tam sayı olmak üzere \(3k\) veya \(3k+1\) biçiminde olduğunu gösteriniz.
Çözüm
\(a \in \mathbb{Z}\) olsun. Bölme algoritmasına göre
\[a = 3q + r, \qquad 0 \leq r < 3\]
olacak biçimde \(q, r\) tam sayıları vardır; yani \(r \in \{0, 1, 2\}\)’dir. Üç durumu tek tek inceleyelim.
\(r = 0\), yani \(a = 3q\) ise:
\[a^2 = 9q^2 = 3(3q^2)\]
Bu \(3k\) biçimindedir.
\(r = 1\), yani \(a = 3q + 1\) ise:
\[a^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1\]
Bu \(3k + 1\) biçimindedir.
\(r = 2\), yani \(a = 3q + 2\) ise:
\[a^2 = 9q^2 + 12q + 4 = 9q^2 + 12q + 3 + 1 = 3(3q^2 + 4q + 1) + 1\]
Bu da \(3k + 1\) biçimindedir.
Üç durumda da \(a^2\) ya \(3k\) ya da \(3k+1\) biçiminde çıktı; başka bir seçenek yoktur.
\(\blacksquare\)
Son örnek şunu söylüyor: hiçbir tam kare \(3k+2\) biçiminde değildir. Bu tür “hangi biçimler imkânsız” bilgileri, bir denklemin çözümü olmadığını göstermenin en pratik yoludur. Aşağıdaki iki örnek bu fikrin doğrudan uygulamasıdır.
Bir \(a\) tam sayısı için \(a = b^2\) olacak biçimde bir \(b \in \mathbb{Z}\) varsa \(a\)’ya tam kare denir.
Örnek 2.5 (\(3a^2 - 1\) Neden Tam Kare Olamaz?) \(a\) bir tam sayı olmak üzere \(3a^2 - 1\) sayısının asla bir tam kare olamayacağını gösteriniz.
Çözüm
\(3a^2\) sayısı \(3\)’ün bir katıdır. Buradan
\[3a^2 - 1 = 3a^2 - 3 + 2 = 3(a^2 - 1) + 2\]
yazılır; yani \(3a^2 - 1\) daima \(3k + 2\) biçimindedir.
Oysa Örnek 2.4 gereği her tam kare \(3k\) veya \(3k+1\) biçimindedir; hiçbir tam kare \(3k+2\) biçiminde olamaz. O hâlde \(3a^2 - 1\) bir tam kare değildir.
\(\blacksquare\)
Örnek 2.6 (\(4k+2\) ve \(4k+3\) Biçimindeki Sayılar) \(k\) bir tam sayı olmak üzere \(4k + 2\) veya \(4k + 3\) biçimindeki hiçbir tam sayının tam kare olamayacağını gösteriniz.
Çözüm
Bir tam karenin \(4\) ile bölümünden kalanın yalnızca \(0\) veya \(1\) olabileceğini gösterelim. \(a \in \mathbb{Z}\) bir tam kare olsun; yani \(a = b^2\) olacak biçimde bir \(b \in \mathbb{Z}\) vardır.
Bölme algoritmasına göre \(b = 4q + r\), \(0 \leq r < 4\) olacak biçimde \(q, r\) tam sayıları vardır. Kareyi açalım:
\[a = b^2 = (4q + r)^2 = 16q^2 + 8qr + r^2\]
Şimdi \(r \in \{0, 1, 2, 3\}\) değerlerini tek tek deneyelim.
\(r = 0\): \(a = 16q^2 + 8qr = 4(4q^2 + 2qr)\), yani \(4k\) biçiminde.
\(r = 1\): \(a = 16q^2 + 8qr + 1 = 4(4q^2 + 2qr) + 1\), yani \(4k+1\) biçiminde.
\(r = 2\): \(a = 16q^2 + 8qr + 4 = 4(4q^2 + 2qr + 1)\), yani \(4k\) biçiminde.
\(r = 3\): \(a = 16q^2 + 8qr + 9 = 4(4q^2 + 2qr + 2) + 1\), yani \(4k+1\) biçiminde.
Görüldüğü gibi her tam kare \(4k\) veya \(4k+1\) biçimindedir. Bölme algoritmasındaki kalanın tek türlü belirli olması nedeniyle bir sayı aynı anda hem \(4k+1\) hem \(4k+2\) biçiminde olamaz. O hâlde \(4k+2\) ve \(4k+3\) biçimindeki sayılar tam kare değildir.
\(\blacksquare\)
2.4 Kalan Aralığını Kaydırmak
Bölme algoritmasında kalan \([0, a)\) aralığında istenmişti. Bu aralık keyfîdir: uzunluğu \(a\) olan herhangi bir aralık aynı işi görür. Aşağıdaki örnek bu esnekliği gösterir; ispat tekniği de öğreticidir, çünkü yeni bir teorem kurmak yerine elimizdeki teoremi kaydırarak kullanır.
Örnek 2.7 (Kaydırılmış Kalan Aralığı) \(a, b \in \mathbb{Z}\) ve \(a > 0\) olsun.
\[b = aq + r, \qquad 2a \leq r < 3a\]
olacak biçimde tek türlü belirli \(q\) ve \(r\) tam sayılarının var olduğunu gösteriniz.
Çözüm
Varlık. Bölme algoritmasına göre
\[b = ak + s, \qquad 0 \leq s < a\]
olacak biçimde tek türlü belirli \(k\) ve \(s\) tam sayıları vardır. Şimdi eşitliğe \(2a\) ekleyip çıkaralım:
\[b = ak - 2a + s + 2a = a(k - 2) + (s + 2a)\]
\(0 \leq s < a\) eşitsizliğinin her tarafına \(2a\) eklersek
\[2a \leq s + 2a < 3a\]
elde edilir. O hâlde
\[q = k - 2, \qquad r = s + 2a\]
alınırsa istenen yazılış elde edilmiş olur.
Teklik. Aynı koşulu sağlayan iki yazılış olsun:
\[b = aq + r = aq' + r', \qquad 2a \leq r,\, r' < 3a\]
Her iki kalan da uzunluğu \(a\) olan aynı aralıkta olduğundan aralarındaki fark \(a\)’yı geçemez:
\[|r' - r| < a\]
Öte yandan \(a(q - q') = r' - r\) eşitliğinden mutlak değer alarak
\[a \cdot |q - q'| = |r' - r| < a\]
bulunur. Buradan \(|q - q'| < 1\), yani \(q = q'\) ve dolayısıyla \(r = r'\) çıkar.
\(\blacksquare\)
Yukarıdaki ispatta \(2a\) sayısının özel bir rolü yoktur. Aynı akıl yürütmeyle, herhangi bir \(c\) tam sayısı için
\[b = aq + r, \qquad ca \leq r < (c+1)a\]
yazılışının var ve tek olduğu gösterilebilir. Teklik ispatının tek dayanağı, kalanların uzunluğu \(a\) olan aynı aralıkta bulunmasıdır.
2.5 Çalışma Problemleri
Alıştırma 2.1 (Bölüm ve Kalan Bulma) Aşağıdaki \(a, b\) çiftleri için \(b = aq + r\), \(0 \leq r < |a|\) koşulunu sağlayan \(q\) ve \(r\) sayılarını bulunuz.
a) \(b = 100, \ a = 7\) b) \(b = -100, \ a = 7\) c) \(b = 100, \ a = -7\) d) \(b = -100, \ a = -7\)
Alıştırma 2.2 (Çarpımın Paritesi) İki tek tam sayının çarpımının tek, çarpanlardan en az biri çift olan bir çarpımın ise çift olduğunu gösteriniz.
Alıştırma 2.3 (Kalanlara Göre Durum Ayırma) a) Her \(n\) tam sayısı için \(n^2 + n\) sayısının çift olduğunu gösteriniz.
b) Her \(n\) tam sayısı için \(n^3\) sayısının \(9k\), \(9k+1\) veya \(9k+8\) biçiminde olduğunu gösteriniz.
c) \(a^2 + b^2 = c^2\) eşitliğini sağlayan \(a, b, c\) tam sayılarında \(a\) ile \(b\)’den en az birinin çift olmak zorunda olduğunu gösteriniz.
İpucu (c): İkisi de tek olsaydı Örnek 2.3 gereği \(a^2 + b^2\) sayısı \(8k + 2\) biçiminde olurdu; oysa \(c^2\) bu biçimde olamaz.
Alıştırma 2.4 (Ardışık Tam Kareler) Hiçbir tam karenin, kendisinden sonraki tam kareyle arasındaki farkın çift olmadığı durumları belirleyiniz; yani \((n+1)^2 - n^2\) ifadesinin her zaman tek olduğunu gösteriniz.