14 Taban Gösterimi ve Bölünebilme Kuralları
“Bir sayı, rakamlarının toplamı \(3\) ile bölünüyorsa \(3\) ile bölünür” kuralını hepimiz biliriz. Bu kuralın neden doğru olduğu ise nadiren sorulur. Cevap kongrüans dilinde tek satırdır ve aynı fikir bütün bölünebilme kurallarını üretir. Önce sayıların basamaklarla yazılışını sağlam bir temele oturtalım.
14.1 Bir Tabana Göre Yazılış
Teorem 14.1 (Taban Gösterimi) Her \(n\) pozitif tam sayısı ve her \(2 \leq b\) tam sayısı için
\[n = d_m b^{m} + d_{m-1} b^{m-1} + \cdots + d_1 b + d_0, \qquad d_m \neq 0\]
olacak biçimde tek türlü belirli \(d_0, d_1, \dots, d_m \in \{0, 1, \dots, b-1\}\) sayıları vardır.
İspat
1. Varlık. İddiayı \(n\) üzerinden güçlü tümevarımla ispatlayalım.
Başlangıç durumu (\(1 \leq n < b\)). \(m = 0\) ve \(d_0 = n\) alalım. \(n \geq 1\) olduğundan \(d_0 \neq 0\)’dır ve \(0 \leq d_0 < b\) koşulu sağlanır.
Tümevarım adımı. \(n \geq b\) olsun ve iddianın \(n\)’den küçük bütün pozitif tam sayılar için doğru olduğunu varsayalım.
Bölme algoritmasına göre
\[n = b q + r, \qquad 0 \leq r < b\]
yazalım. Burada \(q\) pozitiftir (çünkü \(n \geq b\)) ve \(q < n\)’dir (çünkü \(b \geq 2\) olduğundan \(q \leq n/b \leq n/2 < n\)).
Güçlü tümevarım hipotezini \(q\)’ya uygulayalım:
\[q = c_k b^{k} + c_{k-1} b^{k-1} + \cdots + c_0, \qquad c_k \neq 0, \quad 0 \leq c_i < b\]
Şimdi bunu \(n = bq + r\) eşitliğinde yerine koyalım:
\[n = b\left( c_k b^{k} + \cdots + c_0 \right) + r = c_k b^{k+1} + c_{k-1} b^{k} + \cdots + c_0 b + r\]
O hâlde \(d_0 = r\) ve \(i \geq 1\) için \(d_i = c_{i-1}\) alınırsa istenen yazılış elde edilir; baş katsayı \(d_{k+1} = c_k \neq 0\)’dır.
2. Teklik. Aynı \(n\) için iki yazılış olduğunu varsayalım. Her iki yazılışta da \(b\) ile bölünen bütün terimleri bir kenara koyup modülo \(b\)’ye geçelim:
\[n \equiv d_0 \pmod b, \qquad n \equiv d_0' \pmod b\]
(çünkü \(d_i b^{i}\) terimleri \(i \geq 1\) için \(b\) ile bölünür). Buradan \(d_0 \equiv d_0' \pmod b\) olur ve \(0 \leq d_0, d_0' < b\) olduğundan Lemma 13.1 gereği
\[d_0 = d_0'\]
bulunur. Şimdi her iki yazılıştan \(d_0\)’ı çıkarıp \(b\)’ye bölelim:
\[\frac{n - d_0}{b} = d_m b^{m-1} + \cdots + d_1 = d_{m'}' b^{m'-1} + \cdots + d_1'\]
Sol taraf \(n\)’den küçük bir pozitif tam sayıdır (ya da sıfırdır). Aynı akıl yürütmeyi tekrarlayarak \(d_1 = d_1'\), \(d_2 = d_2'\), … elde ederiz. Basamak sayıları da eşit olmak zorundadır; aksi hâlde baş katsayılardan biri \(0\) olurdu.
\(\blacksquare\)
Tanım 14.1 (\(b\) Tabanına Göre Yazılış) Teorem 14.1’ndeki
\[n = d_m b^{m} + \cdots + d_1 b + d_0\]
yazılışına “\(n\) sayısının \(b\) tabanına göre yazılışı” denir ve
\[n = \left( d_m \dots d_1 d_0 \right)_{b}\]
gösterimi kullanılır. \(d_i\) sayılarına rakamlar denir.
Örnek 14.1 (\(104\) Sayısını Üç Tabanında Yazmak) \(104\) sayısını \(3\) tabanında yazınız.
Çözüm
İspattaki yol doğrudan bir algoritma verir: sayıyı ardışık olarak \(3\)’e böler, kalanları biriktiririz.
\[ \begin{aligned} 104 &= 3 \cdot 34 + 2 \\ 34 &= 3 \cdot 11 + 1 \\ 11 &= 3 \cdot 3 + 2 \\ 3 &= 3 \cdot 1 + 0 \\ 1 &= 3 \cdot 0 + 1 \end{aligned} \]
Rakamlar, kalanların ters sırada okunmasıyla elde edilir:
\[104 = (1\,0\,2\,1\,2)_{3}\]
(Sağlama: \(1 \cdot 81 + 0 \cdot 27 + 2 \cdot 9 + 1 \cdot 3 + 2 = 81 + 18 + 3 + 2 = 104\) ✓)
\(\blacksquare\)
Günlük hayatta \(b = 10\) kullanırız ve tabanı yazmayız. Bundan sonra bir sayının “rakamları” dendiğinde onluk tabandaki rakamları kastedilecektir:
\[N = a_m 10^{m} + a_{m-1} 10^{m-1} + \cdots + a_1 \cdot 10 + a_0\]
14.2 Bölünebilme Kurallarının Kaynağı
Bütün bölünebilme kuralları tek bir gözlemden doğar: \(10\) sayısının modüldeki kalanı ne ise, \(10\)’un kuvvetleri de o kalanın kuvvetlerini verir. Modül küçük olduğunda bu kalanlar çok basitleşir.
| Modül | \(10\)’un kalanı | \(10^k\)’nin kalanı |
|---|---|---|
| \(2\) | \(0\) | \(0\) (\(k \geq 1\) için) |
| \(5\) | \(0\) | \(0\) (\(k \geq 1\) için) |
| \(3\) | \(1\) | \(1\) |
| \(9\) | \(1\) | \(1\) |
| \(11\) | \(-1\) | \((-1)^k\) |
Şimdi bu satırların her birini birer teoreme dönüştürelim.
Teorem 14.2 (Dokuza ve Üçe Bölünebilme) \(1 \leq N\) tam sayısının onluk tabana göre yazılışı
\[N = a_m 10^{m} + a_{m-1} 10^{m-1} + \cdots + a_1 \cdot 10 + a_0\]
ve rakamlar toplamı
\[S = a_0 + a_1 + \cdots + a_m\]
olsun. Bu durumda
\[9 \mid N \iff 9 \mid S, \qquad 3 \mid N \iff 3 \mid S\]
İspat
Önce \(9\) için gösterelim. \(10 = 9 + 1\) olduğundan
\[10 \equiv 1 \pmod 9\]
Teorem 12.1 (f) gereği her \(k \geq 0\) için
\[10^{k} \equiv 1^{k} = 1 \pmod 9\]
Şimdi \(N\)’nin yazılışındaki her terime bu bilgiyi uygulayalım. (e) özelliği gereği
\[a_k 10^{k} \equiv a_k \cdot 1 = a_k \pmod 9\]
ve (d) özelliğinin toplam kısmıyla bütün terimleri toplarsak
\[N = \sum_{k=0}^{m} a_k 10^{k} \equiv \sum_{k=0}^{m} a_k = S \pmod 9\]
O hâlde \(N \equiv S \pmod 9\)’dur. İki sayı modülo \(9\) kongrü olduğundan biri \(9\) ile bölünüyorsa diğeri de bölünür:
\[9 \mid N \iff N \equiv 0 \iff S \equiv 0 \iff 9 \mid S \pmod 9\]
\(3\) için ispat kelimesi kelimesine aynıdır; tek fark \(10 \equiv 1 \pmod 3\) eşitliğinden başlanmasıdır.
\(\blacksquare\)
Teorem 14.3 (On Bire Bölünebilme) \(1 \leq N\) tam sayısının onluk tabana göre yazılışı
\[N = a_m 10^{m} + \cdots + a_1 \cdot 10 + a_0\]
ve alterne basamak toplamı
\[T = \sum_{k=0}^{m} (-1)^{k} a_k = a_0 - a_1 + a_2 - a_3 + \cdots + (-1)^{m} a_m\]
olsun. Bu durumda
\[11 \mid N \iff 11 \mid T\]
İspat
\(10 = 11 - 1\) olduğundan
\[10 \equiv -1 \pmod{11}\]
Teorem 12.1 (f) gereği her \(k \geq 0\) için
\[10^{k} \equiv (-1)^{k} \pmod{11}\]
Her terimi \(a_k\) ile çarpıp toplayalım:
\[N = \sum_{k=0}^{m} a_k 10^{k} \equiv \sum_{k=0}^{m} (-1)^{k} a_k = T \pmod{11}\]
\(N \equiv T \pmod{11}\) olduğundan biri \(11\) ile bölünüyorsa diğeri de bölünür.
\(\blacksquare\)
Önerme 14.1 (İkiye ve Beşe Bölünebilme) \(1 \leq N\) tam sayısının birler basamağı \(a_0\) olsun. Bu durumda
\[2 \mid N \iff 2 \mid a_0, \qquad 5 \mid N \iff 5 \mid a_0\]
Yani bir sayının \(2\) ile bölünmesi için son rakamının çift, \(5\) ile bölünmesi için son rakamının \(0\) veya \(5\) olması gerek ve yeterlidir.
Bunun nedeni \(10 \equiv 0 \pmod 2\) ve \(10 \equiv 0 \pmod 5\) olmasıdır: \(k \geq 1\) için \(10^k\) terimlerinin hepsi her iki modülde de sıfırdır, geriye yalnızca \(a_0\) kalır.
14.3 Çözümlü Örnekler
Örnek 14.2 (\(5896167376\) Sayısı \(11\) ile Bölünür mü?) \(N = 5896167376\) sayısının \(11\) ile bölünüp bölünmediğini belirleyiniz.
Çözüm
Rakamları sağdan sola doğru numaralandıralım:
\[a_0 = 6,\ a_1 = 7,\ a_2 = 3,\ a_3 = 7,\ a_4 = 6,\ a_5 = 1,\ a_6 = 6,\ a_7 = 9,\ a_8 = 8,\ a_9 = 5\]
Alterne toplamı hesaplayalım:
\[ \begin{aligned} T &= a_0 - a_1 + a_2 - a_3 + a_4 - a_5 + a_6 - a_7 + a_8 - a_9 \\ &= 6 - 7 + 3 - 7 + 6 - 1 + 6 - 9 + 8 - 5 \\ &= 0 \end{aligned} \]
\(11 \mid 0\) olduğundan Teorem 14.3 gereği
\[11 \mid 5896167376\]
\(\blacksquare\)
Örnek 14.3 (\(45634598712\) Sayısı \(11\) ile Bölünür mü?) \(N = 45634598712\) sayısının \(11\) ile bölünüp bölünmediğini belirleyiniz; bölünmüyorsa kalanı bulunuz.
Çözüm
Rakamları sağdan sola numaralandıralım:
\[a_0 = 2,\ a_1 = 1,\ a_2 = 7,\ a_3 = 8,\ a_4 = 9,\ a_5 = 5,\ a_6 = 4,\ a_7 = 3,\ a_8 = 6,\ a_9 = 5,\ a_{10} = 4\]
Alterne toplam:
\[ \begin{aligned} T &= 2 - 1 + 7 - 8 + 9 - 5 + 4 - 3 + 6 - 5 + 4 \\ &= 10 \end{aligned} \]
\(11 \nmid 10\) olduğundan sayı \(11\) ile bölünmez.
Dahası, ispatta \(N \equiv T \pmod{11}\) elde etmiştik. \(T = 10\) ve \(0 \leq 10 < 11\) olduğundan Teorem 12.2 gereği \(N\) sayısının \(11\) ile bölümünden kalan \(10\)’dur.
\(\blacksquare\)
Yukarıdaki örneğin son adımına dikkat ediniz: alterne toplam yalnızca bölünüp bölünmediğini değil, kalanı da verir. Aynı şey rakamlar toplamı için de geçerlidir: bir sayının \(9\) ile bölümünden kalan, rakamları toplamının \(9\) ile bölümünden kalana eşittir.
Örneğin \(N = 5896167376\) için rakamlar toplamı \(S = 58\) ve \(58 = 6 \cdot 9 + 4\) olduğundan \(N \equiv 4 \pmod 9\)’dur.
Örnek 14.4 (Dokuza Bölünebilme Uygulaması) \(N = 123456789\) sayısının \(9\) ve \(3\) ile bölünüp bölünmediğini belirleyiniz.
Çözüm
Rakamlar toplamı:
\[S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45\]
\(45 = 9 \cdot 5\) olduğundan \(9 \mid 45\)’tir. Teorem 14.2 gereği
\[9 \mid 123456789\]
\(9 \mid N\) ve \(3 \mid 9\) olduğundan geçişme gereği \(3 \mid N\)’dir de.
\(\blacksquare\)
14.4 Çalışma Problemleri
Alıştırma 14.1 (Taban Değiştirme) a) \(250\) sayısını \(2\), \(5\) ve \(7\) tabanlarında yazınız.
b) \((1101101)_2\) sayısını onluk tabanda yazınız.
c) \((2021)_3\) sayısını onluk tabanda yazınız.
Alıştırma 14.2 (Bölünebilme Testleri) Aşağıdaki sayıların \(3\), \(9\) ve \(11\) ile bölünüp bölünmediğini belirleyiniz; bölünmüyorsa kalanları bulunuz.
a) \(8\,675\,309\) b) \(1\,234\,321\) c) \(999\,999\,999\)
Alıştırma 14.3 (Yeni Bir Kural Türetmek) a) \(10^3 \equiv -1 \pmod{7}\) olduğunu gösteriniz.
b) Bu bilgiyi kullanarak \(7\) ile bölünebilme için bir kural türetiniz: sayıyı sağdan başlayarak üçer basamaklı gruplara ayırıp bu grupları dönüşümlü olarak toplayıp çıkarmak.
c) Kuralınızı \(1\,000\,003\) sayısına uygulayınız.
Not: Aynı gözlem \(11\) ve \(13\) için de işler; çünkü \(1001 = 7 \cdot 11 \cdot 13\)’tür.
Alıştırma 14.4 (Herhangi Bir Tabanda Bölünebilme) \(n\) sayısı \(b\) tabanında \((d_m \dots d_1 d_0)_b\) biçiminde yazılmış olsun.
a) \((b-1) \mid n\) olması için gerek ve yeter koşulun \((b-1) \mid (d_0 + d_1 + \cdots + d_m)\) olduğunu gösteriniz.
b) \((b+1) \mid n\) olması için gerek ve yeter koşulun \((b+1)\) sayısının alterne rakam toplamını bölmesi olduğunu gösteriniz.
Not: \(b = 10\) alındığında (a) şıkkı dokuza, (b) şıkkı on bire bölünebilme kuralını verir.