17 Eylül 2015 Perşembe

7'den 77'ye bölünebilme kuralları

Hayır, yetmişyediye kadar olan bütün sayılara bölünebilme kurallarını açıklamayacağım tabii ki ama buradaki malzemeyi kanıksayan okurun her sayıya bölünebilme kuralını kendisinin türetmesini temin etmeye çalışacağım. Son zamanlarda okuduğum bir sayılar teorisi kitabında epeyce zor görünen bir soruyu yazar sadece 9'a ve 17'ye bölünebilmeyi kullanarak tereyağından kıl çeker gibi halletmişti. Ben de 7 ve 17 ile bölünebilmenin en genel halini merak ederken aşağıdaki analizi yaptım. İsterseniz takip edin. Bu esnada kuralı uygulayan olmak yerine, kural koyan olmanın zevkine varabilirsiniz. Rahmetli Cahit Arf'ın dediği gibi: Bir teoremi ispatlamak, onu keşfetmek kadar zevklidir.

7 ile bölünüp bölünmediğini sorgulayacağımız sayı onluk tabanda $A := a_{k}a_{k-1} \ldots a_{1}a_{0}$ formunda temsil edilsin. Daha açık yazıldığında bu \begin{equation*} A = a_{k}\cdot 10^{k} + a_{k-1} \cdot 10^{k-1} + \cdots + a_{1} \cdot 10 + a_{0} \end{equation*} demektir. Sadece bu denkleme bakarak basit bölünebilme kurallarını hemen türetebiliriz. Örneğin yukarıdaki temsili $A=10(a_{k}\cdot 10^{k-1} + a_{k-1} \cdot 10^{k-2} + \cdots + a_{1})+a_{0}$ şeklinde yazdığımızda bu eşitliğin ilk terimi bariz bir şekilde 2, 5 ve 10 sayılarına bölünür. O zaman $A$ sayısının 2, 5 ve 10'a bölünebilmesi için gerek ve yeter şart $a_{0}$ rakamının bu sayılara tam bölünebilmesidir. Daha açık yazmak gerekirse $a_{0} \in \{0,2,4,6,8\}$ ise sayı 2'ye, $a_{0} \in \{0,5\}$ ise sayı 5'e ve $a_{0}=0$ ise sayı 10'a tam olarak bölünür. Öte yandan 3 ve 9'a bölünebilmenin kuralları için biraz daha çabalamamız lazım. İşe çok basit ama önemli bir lemma ile başlayalım. İspatını okurun bildiğini, kendisinin yapabileceğini ya da sayılar teorisi ile ilgili temel seviyede yazılmış kaynaklardan ulaşabileceğini varsayıyorum.

Lemma: (1) $a \equiv b ({\rm mod} \ n)$ ve $c \equiv d({\rm mod} \ n)$ ise, o zaman \begin{eqnarray}\nonumber a+c &\equiv& b+d ({\rm mod}\ n), \\ \nonumber a-c &\equiv& b-d ({\rm mod}\ n), \\ \nonumber ac &\equiv& bd ({\rm mod}\ n). \end{eqnarray} (2) $a \equiv b({\rm mod}\ n)$ ise, o zaman her $c$ için \begin{eqnarray}\nonumber a+c &\equiv& b+c({\rm mod}\ n), \\ \nonumber a-c &\equiv& b-c({\rm mod}\ n), \\ \nonumber ac &\equiv& bc({\rm mod}\ n). \end{eqnarray}

Öncelikle $10 \equiv 1({\rm mod}\ 3)$ olduğunu gözlüyoruz. Yukarıdaki lemma uyarınca $10^{2} \equiv 10 \equiv 1({\rm mod}\ 3)$ olur. Tümevarımla okur $10^{k} \equiv 1({\rm mod}\ 3)$ olduğunu kolayca gösterebilir. O zaman $A$ sayısının onluk tabandaki temsilinden \begin{equation*} A \equiv a_{k}+a_{k-1}+ \cdots + a_{1}+a_{0} ({\rm mod}\ 3) \end{equation*} olduğunu gösterebilirsiniz. İşte 3'e bölünebilme kuralı çıktı! Sayının rakamları toplamı 3'e bölünüyorsa, o zaman sayı da 3'e bölünebilir. 9'a bölünebilme kuralı da böyle ispatlanmalı. Çünkü $10 \equiv 1({\rm mod}\ 9)$ olduğundan $10^{k}\equiv 1({\rm mod}\ 9)$ olur. Yani bir sayının rakamları toplamı 9'a bölünüyorsa, o zaman sayı da 9'a bölünebilir.

Dikkatli okur yukarıdaki analizde $10^{k}\equiv 1({\rm mod}\ n)$ denkliğinin anahtar basamak olduğunu gözlemiştir. $n=3$ veya $n=9$ için bu denklik her $k \in {\mathbb N}$ için doğru ve bölünebilme kuralı da aşırı derecede kolaylaşmış oluyor. 7'ye bölünebilmede işimiz biraz daha uzayacak. Öncelikle 10'un kuvvetlerini mod 7'de inceleyelim. \begin{eqnarray} \nonumber &&10^{0} \equiv 1({\rm mod}\ 7), \ 10^{1} \equiv 3({\rm mod}\ 7),\ 10^{2} \equiv 30 \equiv 2({\rm mod}\ 7) \\ \nonumber &&10^{3} \equiv 20 \equiv 6 \equiv -1 ({\rm mod}\ 7), \ 10^{4} \equiv -10 \equiv -3 ({\rm mod}\ 7) \\ \nonumber &&10^{5} \equiv -30 \equiv -2 ({\rm mod}\ 7) \\ \nonumber &&10^{6} \equiv -20 \equiv 1({\rm mod}\ 7) \ \ \ {\rm Burada \ dur!} \end{eqnarray}

Durduğumuz noktada modüler olarak 1'e ulaştık. Hatırlanacağı üzere modüler olarak 1'e ulaşmak 3 ve 9'a bölünebilmede anahtar basamaktı. Bu yazıdaki lemmayı kullanarak $k \equiv K({\rm mod} 6)$ olmak üzere, $10^{k} \equiv 10^{K}({\rm mod} 7)$ olduğunu gözleyebiliriz. Dikkat edilirse yukarıdaki döngüyü çıkarırken denkliklerin sağ taraflarını mutlak değerce $3$'ü geçmeyecek şekilde ayarladık. Bu bizim işimizi kolaylaştıracaktır. $A$ sayısını mod 7'de yazabiliriz. \begin{equation*} A \equiv (a_{0}-a_{3}+a_{6}-a_{9}+\cdots) + 3(a_{1}-a_{4}+a_{7}-a_{10}+\cdots) + 2(a_{2}-a_{5}+a_{8}-a_{11}+\cdots) ({\rm mod}\ 7) \end{equation*}

Hafta Farsça'da, hepta Yunanca'da 7 demek. 7 sayısı genellikle bir işin tamamlanmasını ve mükemmeliyete ermesini temsil eder. Aynı zamanda bir haftada 7 gün olması da modüler aritmetikte Bugün Cuma ise 740585 gün sonra hangi gün olur? gibi sözlü soruların da karşımıza çıkmasına neden oluyor. $A=740585$ sayısının hanelerini 7'ye bölünebilme kuralıyla ilgili denklemde kullanırsak, o zaman \begin{equation*} 740585 \equiv (5-0) + 3(8-4) + 2(5-7) \equiv 13 \equiv -1 ({\rm mod}\ 7) \end{equation*} olur ve aradığımız günün Perşembe olduğu tespit edilir.

Bölünebilme ile ilgili ek bazı yorumlarda bulunarak bu postayı bitireceğiz.

  1. $n = p_{1}p_{2}\cdots p_{k}$ birbirinden farklı asal sayıların çarpımı biçiminde yazılabiliyorsa, o zaman herhangi bir sayının $n$ ile bölünebilmesi için $p_{1},p_{2},\ldots ,p_{k}$ ile bölünebilmesi gerekir. Örneğin 15' bölünebilme şartı basitçe hem 3'e hem de 5'e bölünebilmektir.
  2. $10^{k}\equiv 1({\rm mod}\ n)$ ne kadar hızlı gerçekleşirse, o zaman $n$ ile bölünebilme kuralı da kadar kolaylaşır. Örneğin $10^{1}\equiv -1({\rm mod}\ 11)$ ve $10^{2} \equiv -10 \equiv 1({\rm mod}\ 11)$ olduğundan, 10'luk tabanda temsil edilen $A$ sayısı için \begin{equation*} A \equiv (a_{0}+a_{2}+a_{4}+\cdots) - (a_{1}+a_{3}+a_{5}+\cdots) ({\rm mod}\ 11) \end{equation*} olur. 11'e bölünebilme ile ilgili bu kuralı siz muhtemelen daha önceden de ezbere -ama ispatsız- biliyordunuz.
  3. Burada uyguladığımız algoritma ile ilgili okur şu soruyu sorabilir: Ne malum $10^{k} \equiv 1({\rm mod}\ n)$ olacağı? Ya böyle bir $k$ yoksa? Hemen cevap verelim:
    Fermat'nın küçük teoremi: $p$, $A$ sayısını bölmeyen asal bir sayı olsun. O zaman $A^{p-1} \equiv 1({\rm mod}\ p)$.
    Bu teoremin ispatı hemen hemen her sayılar teorisi ya da soyut cebir kitabında olsa gerektir. (Belki bir gün yerölçüsünde de değinebiliriz bu teoremin başka uygulamalarına.)
  4. Bölünebilme kuralını uygulayacağımız sayı asal değilse, o zaman gerçekten de $10^{k} \equiv 1({\rm mod}\ n)$ hiç bir zaman gerçekleşmeyebilir. Örneğin $10 \equiv -2({\rm mod}\ 12)$ ama $k \geq 2$ için $10^{k} \equiv 4({\rm mod}\ 12)$ olur. Burada da periyodik bir davranış arayıp ona göre bir bölünebilme kuralı türeteceğiz. 12 ile bölünebilmede şansımız yaver gitti ve \begin{equation*} A \equiv a_{0}-2a_{1} + 4(a_{2}+a_{3} + \cdots)({\rm mod}\ 12) \end{equation*} kuralını ispatlamış olduk.
  5. $n$ asal değilse, $10^{k}({\rm mod}\ n) \in \{0,\ldots,n-1\}$ dizisinin periyodik olduğunu gösterebilir misiniz? (İpucu: Dizinin periyodik olmadığını varsayıp, bir çelişkiye ulaşmaya çalışın.)

Hiç yorum yok:

Yorum Gönder