3 Tam Sayılarda Bölünebilme

Bölme algoritması her bölme işlemine bir kalan iliştirir. Sayılar teorisinin asıl ilgilendiği durum ise kalanın sıfır olduğu özel hâldir: bu durumda bölünen sayı, bölene “tam bölünür”. Bu bölümde bu bağıntıyı kesin biçimde tanımlayacak ve dersin geri kalanında refleks hâline gelecek temel özelliklerini ispatlayacağız.

3.1 Bölünebilme Bağıntısı

Tanım 3.1 (Bölünebilme) $a$ ve $b$ birer tam sayı olsun. Eğer

\[b = a \cdot x\]

olacak biçimde bir $x \in \mathbb{Z}$ varsa “$a$ sayısı $b$’yi tam böler” denir ve

\[a \mid b\]

yazılır. Bu durumda $b$’ye $a$’nın bir katı, $a$’ya da $b$’nin bir böleni denir.

Aksi hâlde, yani her $x \in \mathbb{Z}$ için $b \neq a \cdot x$ ise “$a$ sayısı $b$’yi bölmez” denir ve $a \nmid b$ yazılır.

Örnek 3.1 (İlk Örnekler) \[3 \mid 18, \qquad -4 \mid 28, \qquad -5 \mid -20\]

çünkü $18 = 3 \cdot 6$, $28 = (-4) \cdot (-7)$ ve $-20 = (-5) \cdot 4$’tür. Buna karşılık

\[2 \nmid 3\]

çünkü $3 = 2x$ eşitliğini sağlayan bir tam sayı yoktur.

Bölünebilme bir bağıntıdır, bir işlem değil

$a \mid b$ gösterimi bir önermedir; doğru ya da yanlış olabilir. $a/b$ ise bir sayıdır. İkisini karıştırmamak gerekir: $3 \mid 18$ ifadesi “doğru” değerini taşır, $18/3$ ifadesi ise $6$ sayısını gösterir.

Bu ayrım, tanımda bölme işlemine hiç başvurulmamış olmasının da nedenidir: tanım yalnızca bir çarpmanın varlığını ister.

3.2 Temel Özellikler

Aşağıdaki liste, ders boyunca sürekli kullanacağımız bölünebilme kurallarını toplar. Hepsinin ispatı tanımın doğrudan uygulanmasıdır: bölünebilmeyi çarpım olarak yazar, düzenler ve yeniden çarpım olarak okuruz.

Teorem 3.1 (Bölünebilmenin Temel Özellikleri) Her $a, b, c, d, e, f \in \mathbb{Z}$ için aşağıdakiler geçerlidir.

$1 \mid a$ ve $-1 \mid a$.
$a \mid 0$.
$0 \mid a$ ise $a = 0$.
$a \mid a$ (yansıma).
$a \mid b$ ve $b \mid c$ ise $a \mid c$ (geçişme).
$d \mid a$ ve $d \mid b$ ise $d \mid ae + bf$.
$d \mid a$ ve $d \mid b$ ise $d \mid a + b$ ve $d \mid a - b$.
$b \neq 0$ ve $a \mid b$ ise $|a| \leq |b|$.
$a \mid b$ ve $b \mid a$ ise $a = b$ veya $a = -b$.
$0 < a, b$ ve $a \mid b$, $b \mid a$ ise $a = b$.
$a \mid b$ ve $c \mid d$ ise $ac \mid bd$.
$ac \mid bc$ ve $c \neq 0$ ise $a \mid b$.
$a \mid b$ ise $a \mid -b$, $-a \mid b$ ve $-a \mid -b$.

İspat

(1) $a = 1 \cdot a$ olduğundan $1 \mid a$’dır. Benzer biçimde $a = (-1) \cdot (-a)$ olduğundan $-1 \mid a$’dır.

(2) $0 = a \cdot 0$ olduğundan $a \mid 0$’dır. (Burada $a = 0$ olması da sakınca doğurmaz.)

(3) $0 \mid a$ olsun. Tanım gereği $a = 0 \cdot x$ olacak biçimde bir $x$ vardır; ama $0 \cdot x = 0$ olduğundan $a = 0$’dır.

(4) $a = a \cdot 1$ olduğundan $a \mid a$’dır.

(5) $a \mid b$ ve $b \mid c$ olsun. O hâlde $b = ax$ ve $c = by$ olacak biçimde $x, y$ tam sayıları vardır. Birinciyi ikincide yerine yazalım:

\[c = by = (ax)y = a(xy)\]

$xy$ bir tam sayı olduğundan $a \mid c$’dir.

(6) $d \mid a$ ve $d \mid b$ olsun; yani $a = dx$ ve $b = dy$ olacak biçimde $x, y \in \mathbb{Z}$ vardır. Bu durumda

\[ae + bf = dxe + dyf = d(xe + yf)\]

olur. $xe + yf$ bir tam sayı olduğundan $d \mid ae + bf$’dir.

(7) Altıncı özellikte $e = f = 1$ alınırsa $d \mid a + b$, $e = 1$ ve $f = -1$ alınırsa $d \mid a - b$ elde edilir.

(8) $b \neq 0$ ve $a \mid b$ olsun; $b = ax$ olacak biçimde bir $x$ vardır. $b \neq 0$ olduğundan $x \neq 0$’dır, dolayısıyla $|x| \geq 1$’dir. Mutlak değer alalım:

\[|b| = |a| \cdot |x| \geq |a| \cdot 1 = |a|\]

(9) $a \mid b$ ve $b \mid a$ olsun. Önce $a = 0$ durumunu ayıralım: $a = 0$ ise (3) gereği $b = 0$’dır ve iddia sağlanır. Benzer biçimde $b = 0$ ise $a = 0$’dır.

Şimdi $a \neq 0$ ve $b \neq 0$ olsun. (8) özelliğini iki yönde de uygulayalım:

\[|a| \leq |b| \qquad \text{ve} \qquad |b| \leq |a|\]

Buradan $|a| = |b|$, yani $a = b$ veya $a = -b$ bulunur.

(10) (9) gereği $a = b$ veya $a = -b$’dir. İkinci seçenek $a, b > 0$ ile bağdaşmaz; çünkü $a = -b < 0$ olurdu. O hâlde $a = b$’dir.

(11) $b = ax$ ve $d = cy$ olsun. Taraf tarafa çarpalım:

\[bd = (ax)(cy) = (ac)(xy)\]

$xy$ tam sayı olduğundan $ac \mid bd$’dir.

(12) $ac \mid bc$ ve $c \neq 0$ olsun. $bc = (ac)x$ olacak biçimde bir $x$ vardır. $c \neq 0$ olduğundan her iki tarafı $c$’ye sadeleştirebiliriz:

\[b = ax\]

Bu ise $a \mid b$ demektir.

(13) $b = ax$ olsun. O hâlde

\[-b = a(-x), \qquad b = (-a)(-x), \qquad -b = (-a)(x)\]

yazılır; üç eşitlik sırasıyla $a \mid -b$, $-a \mid b$ ve $-a \mid -b$ olduğunu gösterir.

$\blacksquare$

Altıncı özellik neden bu kadar önemli?

Listedeki en çok kullanacağımız madde altıncısıdır: bir $d$ sayısı iki sayıyı birden bölüyorsa, onların her doğrusal birleşimini de böler. Bézout teoreminden Öklid algoritmasına kadar bu bölümden sonra gelen hemen her ispatta bu kural devreye girecektir.

Sıfır sıfırı böler mi?

“$0 \mid 0$” önermesi doğrudur. Tanıma göre bunun anlamı, $0 = 0 \cdot x$ olacak biçimde bir $x$ tam sayısının var olmasıdır — ki her $x$ bunu sağlar.

Buradaki tuhaflık hissinin kaynağı, $0/0$ ifadesinin tanımsız olmasıdır. Ama bölünebilme bağıntısı bir bölme işlemi değildir; yalnızca uygun bir çarpanın varlığını sorar. Nitekim (3) özelliği tam da bu yüzden “$0$ yalnızca $0$’ı böler” der.

3.3 Ardışık Sayıların Çarpımları

Bölünebilme sorularının büyük bölümü, bir ifadeyi ardışık tam sayıların çarpımı olarak görmeyi öğrenince kendiliğinden çözülür. Aşağıdaki temel gözlem bu tekniğin çekirdeğidir.

Örnek 3.2 (Ardışık Sayıların Çarpımı) Her $n$ tam sayısı için

a) $2 \mid n(n+1)$ b) $3 \mid n(n+1)(n+2)$

olduğunu gösteriniz.

Çözüm

a) Bölme algoritmasına göre $n$ ya çift ya da tektir.

$n = 2k$ ise $n(n+1) = 2k(n+1) = 2\big(k(n+1)\big)$ olur; yani $2 \mid n(n+1)$.
$n = 2k+1$ ise $n + 1 = 2k + 2 = 2(k+1)$ olur ve

\[n(n+1) = n \cdot 2(k+1) = 2\big(n(k+1)\big)\]

yazılır; yine $2 \mid n(n+1)$.

Her iki durumda da çarpım çifttir. Sezgisel olarak: ardışık iki sayıdan biri mutlaka çifttir.

b) Bu kez $n$’yi $3$ ile bölelim: $n = 3q + r$, $r \in \{0, 1, 2\}$.

$r = 0$ ise $n = 3q$ olduğundan çarpımın ilk çarpanı $3$’ün katıdır.
$r = 1$ ise $n + 2 = 3q + 3 = 3(q+1)$ olduğundan üçüncü çarpan $3$’ün katıdır.
$r = 2$ ise $n + 1 = 3q + 3 = 3(q+1)$ olduğundan ikinci çarpan $3$’ün katıdır.

Üç durumda da çarpanlardan biri $3$’ün katıdır; dolayısıyla çarpımın tamamı $3$ ile bölünür.

$\blacksquare$

Genel kural

Aynı akıl yürütme şunu verir: ardışık $k$ tam sayının çarpımı daima $k$ ile bölünür. Çünkü bu sayılar $k$ ile bölündüklerinde $0, 1, \dots, k-1$ kalanlarının hepsini birer kez verir; özel olarak biri $k$’nin katıdır.

(İleride, aritmetiğin esas teoremini kurduktan sonra bu çarpımın aslında $k!$ ile bölündüğünü de göreceğiz.)

Örnek 3.3 ($n^3 - n$ Üçe Bölünür) Her $n$ tam sayısı için $3 \mid n^3 - n$ olduğunu gösteriniz.

Çözüm

İfadeyi çarpanlarına ayıralım:

\[n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1)\,n\,(n+1)\]

Bu, ardışık üç tam sayının çarpımıdır. Örnek 3.2 gereği ardışık üç sayının çarpımı $3$ ile bölünür; o hâlde $3 \mid n^3 - n$’dir.

$\blacksquare$

Örnek 3.4 ($3 \mid a(a^2 + 2)$) Her $a$ tam sayısı için $\dfrac{a(a^2+2)}{3}$ ifadesinin bir tam sayı olduğunu gösteriniz.

Çözüm

İfadenin tam sayı olması, $3 \mid a(a^2 + 2)$ demektir. Çarpımı, bildiğimiz bir yapıya benzetelim:

\[a(a^2 + 2) = a^3 + 2a = (a^3 - a) + 3a\]

Sağ taraftaki iki terimi ayrı ayrı inceleyelim:

Örnek 3.3 gereği $3 \mid a^3 - a$’dır.
Açıkça $3 \mid 3a$’dır.

Teorem 3.1 (7) gereği $3$ sayısı bu iki sayının toplamını da böler:

\[3 \mid (a^3 - a) + 3a = a(a^2 + 2)\]

O hâlde $\dfrac{a(a^2+2)}{3}$ bir tam sayıdır.

$\blacksquare$

3.4 Tümevarımla Bölünebilme

Üstel ifadeler içeren bölünebilme iddiaları çoğunlukla tümevarımla ispatlanır. İzlenen yol hep aynıdır: $(k+1)$’inci ifadeyi, $k$’ıncı ifadenin bir katı artı bölünebilirliği bilinen bir terim biçiminde yazmak.

Örnek 3.5 ($8 \mid 5^{2n} + 7$) Her $n$ pozitif tam sayısı için $8 \mid 5^{2n} + 7$ olduğunu gösteriniz.

Çözüm

$5^{2n} = (5^2)^n = 25^n$ olduğunu gözlemleyelim; iddia $8 \mid 25^n + 7$ biçimine dönüşür.

Başlangıç adımı ($n = 1$).

\[25^1 + 7 = 32 = 8 \cdot 4\]

olduğundan iddia doğrudur.

Tümevarım adımı. İddianın $n = k$ için doğru olduğunu, yani $8 \mid 25^k + 7$ olduğunu varsayalım. $n = k+1$ için gösterelim:

\[ \begin{aligned} 25^{k+1} + 7 &= 25 \cdot 25^k + 7 \\ &= 25 \cdot 25^k + 25 \cdot 7 - 25 \cdot 7 + 7 \\ &= 25\left( 25^k + 7 \right) - 168 \end{aligned} \]

Sağ taraftaki iki terime bakalım:

Tümevarım hipotezi gereği $8 \mid 25^k + 7$’dir; o hâlde $8 \mid 25(25^k + 7)$’dir.
$168 = 8 \cdot 21$ olduğundan $8 \mid 168$’dir.

Teorem 3.1 (7) gereği $8$ sayısı bu ikisinin farkını da böler:

\[8 \mid 25\left( 25^k + 7 \right) - 168 = 25^{k+1} + 7\]

Tümevarım ilkesi gereği iddia her $n$ için doğrudur.

$\blacksquare$

Örnek 3.6 ($24 \mid 2 \cdot 7^n + 3 \cdot 5^n - 5$) Her $n$ pozitif tam sayısı için $2 \cdot 7^n + 3 \cdot 5^n - 5$ sayısının $24$ ile tam bölündüğünü gösteriniz.

Çözüm

Kısaca $f(n) = 2 \cdot 7^n + 3 \cdot 5^n - 5$ yazalım.

Başlangıç adımı ($n = 1$).

\[f(1) = 2 \cdot 7 + 3 \cdot 5 - 5 = 14 + 15 - 5 = 24\]

olduğundan $24 \mid f(1)$’dir.

Tümevarım adımı. $24 \mid f(k)$ olduğunu varsayalım ve $f(k+1)$’i $f(k)$ cinsinden yazalım:

\[ \begin{aligned} f(k+1) &= 2 \cdot 7^{k+1} + 3 \cdot 5^{k+1} - 5 \\ &= 7 \cdot \left( 2 \cdot 7^{k} \right) + 5 \cdot \left( 3 \cdot 5^{k} \right) - 5 \end{aligned} \]

Amacımız $7 f(k)$ ifadesini ortaya çıkarmak. $7 f(k) = 7 \cdot 2 \cdot 7^k + 7 \cdot 3 \cdot 5^k - 35$ olduğuna dikkat ederek çıkaralım:

\[ \begin{aligned} f(k+1) - 7 f(k) &= \left( 5 \cdot 3 \cdot 5^{k} - 7 \cdot 3 \cdot 5^{k} \right) + \left( -5 + 35 \right) \\ &= -2 \cdot 3 \cdot 5^{k} + 30 \\ &= -6 \cdot 5^{k} + 30 \\ &= -6\left( 5^{k} - 5 \right) \end{aligned} \]

O hâlde

\[f(k+1) = 7 f(k) - 6\left( 5^{k} - 5 \right)\]

yazılır. İki terimi ayrı ayrı inceleyelim.

Tümevarım hipotezi gereği $24 \mid f(k)$, dolayısıyla $24 \mid 7f(k)$’dir.
İkinci terim için $5^k - 5 = 5\left( 5^{k-1} - 1 \right)$ yazalım. Çarpanlara ayırma özdeşliği gereği

\[5^{k-1} - 1 = (5 - 1)\left( 5^{k-2} + \cdots + 5 + 1 \right) = 4 \cdot t\]

olacak biçimde bir $t$ tam sayısı vardır (bu, $k = 1$ için de doğrudur; o zaman her iki taraf $0$’dır). Buradan

\[6\left( 5^{k} - 5 \right) = 6 \cdot 5 \cdot 4t = 120\,t = 24 \cdot 5t\]

bulunur; yani $24 \mid 6(5^k - 5)$’tir.

Teorem 3.1 (7) gereği $24$ sayısı farkı da böler:

\[24 \mid 7f(k) - 6\left( 5^{k} - 5 \right) = f(k+1)\]

Tümevarım ilkesi gereği iddia her $n$ için doğrudur.

$\blacksquare$

Örnek 3.7 ($2^n - 1 \mid 2^m - 1$ Ne Zaman Olur?) Her $n, m$ pozitif tam sayısı için

\[n \mid m \iff 2^n - 1 \mid 2^m - 1\]

olduğunu gösteriniz.

Çözüm

Her iki yönü ayrı ayrı ele alacağız. Aşağıdaki çarpanlara ayırma özdeşliğini kullanacağız: her $x$ ve her $s \in \mathbb{N}$ için

\[x^{s} - 1 = (x - 1)\left( x^{s-1} + x^{s-2} + \cdots + x + 1 \right) \tag{$\ast$}\]

($\Rightarrow$) $n \mid m$ ise $2^n - 1 \mid 2^m - 1$.

$m = nq$ olacak biçimde bir $q \in \mathbb{N}$ vardır. $(\ast)$ özdeşliğinde $x = 2^n$ ve $s = q$ alalım:

\[2^m - 1 = 2^{nq} - 1 = \left( 2^{n} \right)^{q} - 1 = \left( 2^{n} - 1 \right)\left( \left(2^{n}\right)^{q-1} + \cdots + 2^{n} + 1 \right)\]

Sağ taraftaki ikinci çarpan bir tam sayıdır; o hâlde $2^n - 1 \mid 2^m - 1$’dir.

($\Leftarrow$) $2^n - 1 \mid 2^m - 1$ ise $n \mid m$.

Bölme algoritmasına göre

\[m = nq + r, \qquad 0 \leq r < n\]

yazalım. $2^m - 1$ ifadesini bu yazılıma göre parçalayalım:

\[ \begin{aligned} 2^{m} - 1 &= 2^{nq + r} - 1 \\ &= 2^{r} \cdot 2^{nq} - 1 \\ &= 2^{r}\left( 2^{nq} - 1 \right) + 2^{r} - 1 \end{aligned} \]

İlk yönde gösterdiğimiz gibi $2^n - 1 \mid 2^{nq} - 1$’dir, dolayısıyla $2^n - 1$ sayısı $2^r(2^{nq} - 1)$ terimini de böler. Hipotez gereği $2^n - 1$ sayısı $2^m - 1$’i de bölüyor. O hâlde farkı da böler:

\[2^{n} - 1 \ \mid \ \left( 2^{m} - 1 \right) - 2^{r}\left( 2^{nq} - 1 \right) = 2^{r} - 1\]

Şimdi $r$’nin büyüklüğüne bakalım. $0 \leq r < n$ olduğundan

\[0 \leq 2^{r} - 1 < 2^{n} - 1\]

olur. Ama $2^n - 1$ sayısı $2^r - 1$’i bölüyor ve Teorem 3.1 (8) gereği, bölünen sıfırdan farklı olsaydı $2^n - 1 \leq 2^r - 1$ olması gerekirdi — bu ise yukarıdaki eşitsizlikle çelişir. Geriye tek olasılık kalır:

\[2^{r} - 1 = 0 \implies 2^{r} = 1 \implies r = 0\]

$r = 0$ olduğundan $m = nq$, yani $n \mid m$’dir.

$\blacksquare$

3.5 Doğru mu, Yanlış mı?

Bölünebilmeyle ilgili sezgiler çoğu zaman yanıltıcıdır. Aşağıdaki örnek, benzer görünen önermelerden hangilerinin doğru hangilerinin yanlış olduğunu ayırt etmeyi gösterir; yanlış bir önermeyi çürütmek için tek bir karşı örnek yeterlidir.

Örnek 3.8 (Önermeleri Sınama) Aşağıdaki önermelerin doğru olup olmadığını araştırınız. Doğru olanları ispatlayınız, yanlış olanlara karşı örnek veriniz.

a) Her $a, b, c$ için, $a \mid b$ veya $a \mid c$ ise $a \mid bc$’dir.

b) Her $a, b, c$ için, $a \mid bc$ ise $a \mid b$ veya $a \mid c$’dir.

c) Her $a, b$ için, $a \mid b$ ise $a \leq b$’dir.

d) Her $a$ için $3 \mid a(a+2)$’dir.

e) Her $a$ için $3 \mid a(a+7)(a-2)$’dir.

f) Her $a$ için $3 \mid a(a+1)(2a+1)$’dir.

Çözüm

a) Doğru. Simetri gereği $a \mid b$ durumunu incelemek yeterlidir. $b = ax$ olsun. O hâlde

\[bc = (ax)c = a(xc)\]

olur ve $xc$ tam sayı olduğundan $a \mid bc$’dir.

b) Yanlış. $a = 6$, $b = 2$, $c = 3$ alalım. $bc = 6$ olduğundan $6 \mid bc$’dir; ama $6 \nmid 2$ ve $6 \nmid 3$’tür.

(Bu önerme yalnızca $a$ asal olduğunda doğrudur; ileride bunu Öklid lemması olarak göreceğiz.)

c) Yanlış. $a = -3$, $b = 3$ alalım. $3 = (-3) \cdot (-1)$ olduğundan $a \mid b$’dir, ama $-3 \leq 3$ eşitsizliği doğru olsa da önerme genel olarak bozulur: $a = 3$, $b = -3$ alalım. $-3 = 3 \cdot (-1)$ olduğundan $3 \mid -3$’tür, oysa $3 \leq -3$ yanlıştır.

(Doğru olan biçim Teorem 3.1 (8)’dir: $b \neq 0$ ise $|a| \leq |b|$.)

d) Yanlış. $a = 2$ alalım:

\[a(a+2) = 2 \cdot 4 = 8\]

ve $3 \nmid 8$’dir.

e) Yanlış. $a = 1$ alalım:

\[a(a+7)(a-2) = 1 \cdot 8 \cdot (-1) = -8\]

ve $3 \nmid -8$’dir.

f) Doğru. $a$’yı $3$ ile bölelim: $a = 3q + r$, $r \in \{0, 1, 2\}$.

$r = 0$ ise ilk çarpan $a = 3q$, yani $3$’ün katıdır.
$r = 1$ ise $2a + 1 = 6q + 3 = 3(2q + 1)$, yani üçüncü çarpan $3$’ün katıdır.
$r = 2$ ise $a + 1 = 3q + 3 = 3(q + 1)$, yani ikinci çarpan $3$’ün katıdır.

Üç durumda da çarpanlardan biri $3$’ün katı olduğundan çarpım $3$ ile bölünür.

$\blacksquare$

(d) ve (e) neden bozuluyor?

Bir çarpımın $3$ ile bölünmesi için çarpanların $3$ ile bölümünden kalanlarının $0, 1, 2$ değerlerinin hepsini taraması gerekmez; yalnızca birinin $0$ olması yeterlidir. (f) şıkkında $a$, $a+1$ ve $2a+1$ kalanları birlikte her durumda bir $0$ üretir. (d) ve (e) şıklarında ise iki çarpan aynı kalanı verdiğinden bir boşluk kalır ve o boşluğa düşen $a$ değerleri karşı örnek olur.

3.6 Çalışma Problemleri

Alıştırma 3.1 (Temel Bölünebilme İddiaları) Aşağıdakileri ispatlayınız.

a) Her $n$ pozitif tam sayısı için $9 \mid 10^n - 1$.

b) Her $n$ pozitif tam sayısı için $6 \mid n^3 + 5n$.

c) Her $n$ pozitif tam sayısı için $7 \mid 2^{3n} - 1$.

d) Her $n$ tam sayısı için $5 \mid n^5 - n$.

Alıştırma 3.2 (Bölenlerin Taşınması) a) $a \mid b$ ise her $n \in \mathbb{N}$ için $a^n \mid b^n$ olduğunu gösteriniz.

b) $d \mid n$ ve $d \mid n + 2$ ise $d \mid 2$ olduğunu gösteriniz. Buradan, ardışık iki tek sayının ortak bölenlerinin yalnızca $\pm 1$ olduğu sonucunu çıkarınız.

c) $a \mid b + c$ ve $a \mid b - c$ ise $a \mid 2b$ ve $a \mid 2c$ olduğunu gösteriniz.

Alıştırma 3.3 (Doğru mu, Yanlış mı?) Aşağıdaki önermelerin doğruluğunu araştırınız; yanlış olanlara karşı örnek veriniz.

a) $a \mid b + c$ ise $a \mid b$ veya $a \mid c$’dir.

b) $a^2 \mid b^2$ ise $a \mid b$’dir.

c) $a \mid b$ ve $a \mid c$ ise $a^2 \mid bc$’dir.