Yıl: 1993-1
Yazar: İsmail Ş. Güloğlu
Eski Çin bilgelerinden Yih-Ling (Ölümü 717)’den bize kadar gelebilen problemlerden birinin bugünkü matematik dilimiz ve gösterim tarzımızla ifadesi şudur:
$$x\equiv1\quad(\!\!\!\mod2)$$
$$x\equiv2\quad(\!\!\!\mod5)$$
$$x\equiv5\quad(\!\!\!\mod6)$$
$$x\equiv5\quad(\!\!\!\mod12)$$
kongrüans denklemlerinden oluşan sistemin ortak çözümleri kümesini bulunuz!
Yukarıdaki problemde $x$ tamsayısı $x\equiv5\quad(\!\!\!\!\mod12)$ şartını sağlarsa $x\equiv5\quad(\!\!\!\!\mod12)$ ve $x\equiv5\quad(\!\!\!\!\mod12)$ denklemleri de sağlanmış olacağı için soru
$$x\equiv2\quad(\!\!\!\!\mod5)$$
$$x\equiv5\quad(\!\!\!\!\mod12)$$
denklemlerinden oluşan sistemi çözmeye denktir.
Bu yazımızın konusu olan meşhur Çinlilerin Kalan Teoremi bu sistemin en az bir çözümü olduğun ifade eder.
Çinlilerin Kalan Teoremi: $m_1,m_2, \dots ,m_k$ ikişer ikişer aralarında asal pozitif tamsayılar ve $a_1,a_2,\dots ,a_k$ herhangi tamsayılar ise
$$x\equiv a_1\quad(\!\!\!\!\mod m_1)$$
$$x\equiv a_2\quad(\!\!\!\!\mod m_2)$$
$$\vdots$$
$$x\equiv a_k\quad(\!\!\!\!\mod m_k)$$
kongrüans denklemlerinden oluşan sistemin bir ortak çözümü vardır.
Aynca $x$ tamsayısı bir çözüm ise $y$ tamsayısının da bir çözüm olması için gerek ve yeter şart $M=m_1\cdot m_2\cdot\dots\cdot m_k$ için $x\equiv y \quad (\!\!\!\!\mod M)$ olmasıdır; özel olarak verilen sistemin $0<x\leq M$ koşullarına uyan tam bir tane çözümü vardır.
Bu teoremi anlamanızı sağlayacak ve ispatını yapmanızı kolaylaştıracak bir kaç ipucu verelim:
(i) $m_1,m_2,\dots, m_k$ sayılarının en küçük ortak katı $M$ olduğu için teoremin, çözümün tekliği hakkındaki ikinci kısmının doğruluğu kolayca görülebilir.
(ii) $a_1, a_1+m_1, a_1+2m_1, \dots, a_1+(m_2-1)m_1$ sayıları $m_2$ modülüne göre farklı kongrüans sınıflarındadırlar (Niçin?). Şu halde $a_1+im_1\equiv a_2\; (\!\!\!\!\mod m_2)$ olacak şekilde bir için $0, 1, \dots , m_2$ vardır. $x_1=a_1+im_1$ dersek, $x_1,x_1+m_1m_2,x_1+2m_1m_2,\dots,x_1+(m_3-1)m_1m_2$ sayıları $m_3$ modülüne göre farklı kongrüans sınıflarındadırlar (Niçin?). Şu halde $x_2=x_1+jm_1m_2\equiv a_3\;(\!\!\!\!\mod m_3)$ olacak şekilde $j$ tamsayısı vardır ve
$$x_2\equiv a_3\quad (\!\!\!\!\mod m_3)$$
$$x_2\equiv x_1\equiv a_2\quad (\!\!\!\!\mod m_2)$$
$$x_2\equiv x_1\equiv a_1\quad (\!\!\!\!\mod m_1)$$
denklemleri sağlanır. Artık ispatı tamamlamayı okuyucuya bırakabiliriz.
Diğer bir ispat fikri şu gözleme dayanır: Herhangi bir $(a_1,a_2,\dots, a_k)$ için çözümün varlığı problemi $(1,0,\dots,0),(0,1,0,\dots,0),\dots,(0,0,\dots,0,1)$ özel durumlarında çözümün varlığına indirgenebilir, yani her $i=1,\dots,k$ için $x_i\equiv 1 \;(\!\!\!\!\mod m_i)$ ve $x_i\equiv0\;(\!\!\!\!\mod m_j)$, $j\neq i$, olacak şekilde bir $x_i$ tamsayısı bulunabilirse,
$$x=a_1x_1+a_2x_2+\dots+a_kx_k$$
sayısı verilen sistemin bir çözümü olur.
Diğer taraftan $m_i$ ve $M_i=M/m_i=m_1m_2\dots m_{i-1}m_{i+1}\dots m_k$ tamsayıları aralarında asal oldukları için $um_i+vM_i=1$ olacak şekilde $u$ ve $v$ tamsayıları vardır. $x_i=vM_i$ dersek $x_i\equiv1 \;(\!\!\!\!\mod m_i)$ ve $x_j\equiv0\;(\!\!\!\!\mod m_j)$, $j\neq i$ elde edilir.
Çinlilerin Kalan Teoremi bazı özelliklere sahip uygun tamsayıların ve tamsayı dizilerinin varlığını göstermek için akıllıca kullanılabilir. Zaman zaman olimpiyat sorulan arısında da böyle uygulamalara rastlanıyor.
Örnek 1: Her biri uygun bir tam sayının karesine bölünebilen 1000 tane ardışık tamsayı var mıdır?
Bir tamsayının karesine bölünebilme, bir asal sayının karesine bölünebilmeye denk olduğu için problem, $p_i^2| (N+i)$, $i= 1,\dots, 1000$ olacak şekilde $p_i$ asal sayılan ve $N$ tamsayısının bulunup bulunamayacağını somaktadır.
Sonsuz tane asal sayı olduğu için 1000 tane farklı asal sayı bulabiliriz. Bunları $p_1,p_2,\dots,p_{1000}$ ile gösterelim ve $m_i=p_i^2$, $i=1,\dots , 1000$ diyelim. Aşikâr olarak $m_i$ sayıları ikişer ikişer aralarında asaldırlar ve dolayısı ile Çinlilerin Kalan Teoremine göre
$$x\equiv-1\quad(\!\!\!\!\mod m_1)$$
$$x\equiv-2\quad(\!\!\!\!\mod m_2)$$
$$\vdots$$
$$x\equiv-1000\quad(\!\!\!\!\mod m_{1000})$$
denklemleri sağlanacak şekilde bir $x= N$ tamsayısı vardır. $N+1, N+2, \dots , N+1000$ ardışık tamsayılarının her biri bir tam sayının karesine bölünür.
30. Uluslararası Matematik Olimpiyatları’nda (1989) şu soru sorulmuştur:
Örnek 2: Her pozitif $n$ tam sayısı için hiçbiri uygun bir asal sayının kuvveti olmayan $n$ tane ardışık tamsayının bulunduğunu kanıtlayın.
Ve önerilen çözüm şu idi: $N=[(n+1)!]^2+1$ diyelim. Elbette her $j\in\{1,2,\dots,n\}$ için $1+j$ sayısı $N+j$’nin bir bölenidir. Uygun bir $j$ için $N+j$ bir $p$ asal sayısının kuvveti olsa $1+j= p^r$ ve $N+j=p^s$ olacak şekilde $r$ ve $s$ pozitif tamsayıları bulunur. $r<s$’dir. $N+j= (1+j) + ((n+1)!)^2$ ve $p^{r+1}|[(n+1)!]^2$ olduğunda $p^{r+1}l(1+j)$ elde ederiz ki bu mümkün değildir. Şu halde $N+1, N+2,\dots, N+n$ ardışık tamsayıları istenen koşulu sağlayan bir dizi oluştururlar.
Çinlilerin Kalan Teoremi’nden istifade ile şöyle bir çözüm de verebiliriz:
Bir tamsayının bir asal sayının kuvveti olmaması demek en az iki farklı asal böleni bulunması demektir. $2n$ tane farklı asal sayı alalım. Bunları $p_1,p_2,\dots,p_{2n}$ ile gösterelim ve
$$m_i=p_{2i-1}p_{2i},\quad i=1,2,\dots,n$$
diyelim. $m_i$ sayıları ikişer ikişer aralarında asaldırlar. Çinlilerin Kalan Teoremi’nden
$$N\equiv-1\quad(\!\!\!\!\mod m_1)$$
$$N\equiv-2\quad(\!\!\!\!\mod m_2)$$
$$\vdots$$
$$N\equiv-n\quad(\!\!\!\!\mod m_{n})$$
olacak şekilde bir $N$ (pozitif) tamsayısının bulunduğunu biliyoruz. $N+1, N+2, \dots, N+n$ istenen özelliklere sahip bir dizi olur.
Bu yazıyı, konuyu ne kadar kavradığınızı anlamanıza ve uygulamadaki becerinizi tanımanız ve geliştirmenize vesile olacak alıştırma ve problemlerle tamamlayalım.
Alıştırma 1.
$$2x\equiv3\quad(\!\!\!\!\mod 5)$$
$$3x\equiv4\quad(\!\!\!\!\mod 7)$$
$$5x\equiv2\quad(\!\!\!\!\mod 11)$$
sistemini sağlayan en küçük pozitif tamsayıyı bulunuz. Bu örnekten hareketle Çinlilerin Kalan Teoremi’nin daha genel olarak nasıl ifade ve ispat edilebileceğini düşününüz.
Alıştırma 2. $m$ ve $n$ pozitif tamsayılar, $d$ ve $e$ sırasıyla bunların en büyük ortak böleni ve en küçük ortak katı olsun. $a$ ve $b$ tamsayılar olmak üzere
$$x\equiv a\;(\!\!\!\!\mod m),\quad x\equiv b (\!\!\!\!\mod n)$$
denklemlerinin bir ortak çözümünün bulunması için gerek ve yeter şart $a\equiv b\;(\!\!\!\!\mod d)$ olmasıdır. Eğer bir çözüm varsa, $0< x\leq e$ koşulunu sağlayan tam bir tane çözüm vardır.
İspatlayın.
Problem 1. Her $n$ pozitif tam sayısı için ardışık öyle $n$ tane tamsayının bulunabileceğini gösterin ki bunların her biri için onu bölüp diğerlerini bölmeyen bir tamsayı bulunsun.
Problem 2. $n$ ve $d$ pozitif tamsayılar olsun. Ardışık terimleri arasındaki fark $2d$ ve uzunluğu $n$ olan ve tek sayılardan oluşan öyle bir $a_1,a_2,\dots, a_n$ aritmetik dizisi var mıdır ki, her $j\,n\{1,2,\dots,n\}$ için bu dizinin $j$-inci terimi $a_j$,’yi bölen, diğer terimleri bölmeyen $j$ tane asal sayı bulunsun.
İşte size zor bir problem:
Problem 3. Uygun $n$ pozitif tamsayısı için $2^{n}+1$ sayısının asal olduğunu biliyoruz ($n=1,2,4$). Acaba $k$ pozitif bir tamsayı olmak üzere $(k\cdot 2^n+1)_{n\in\mathbb{N}}$ dizisinin terimleri arasında muhakkak en az bir asal sayı bulunur mu? Başka bir deyişle $(k\cdot 2^n+1)_{n\in\mathbb{N}}$ dizisinin hiç bir terimi asal sayı olmayacak şekilde bir $k$ tamsayısı var mıdır?
İyi çalışmalar!
Not: Bu yazı Matematik Dünyası Dergisi arşivinden siteye eklenmiştir. Yazı ilk olarak derginin 1994 yılı 3. sayısında yer almıştır. Matematik Dünyası arşivi titiz bir çalışma ile çevrim içi platformlarda yeni okuyucularıyla buluşuyor. Bu yazıyı burada okunabilir hale getiren arşiv ekibi üyesi Övünç Özgür Eker‘e ve tüm gönüllü arşiv ekibimize teşekkür ediyoruz. Yazıyı PDF olarak okumak için PDF arşivine buradan ulaşabilirsiniz.
