Yazar: Emre Alkan
Yıl: 1994-3
Sayı: 18
Bu yazıda sayılar teorisinin klasikleşmiş iki teoremini verip, ilginç kanıtlarını yapacağız.
Teorem. (Fermat) $p$ asal bir sayı ve $p \nmid a$ olsun. $$a^{p-1} \equiv 1 (\mbox{mod } p)$$ olur.
Kolayca görüleceği üzere buna eşdeğer bir sonuç şöyledir.
Teorem. $p$ asal sayı ise $$a^p \equiv a (\mbox{mod } p)$$ olur.
Kanıt 1. Her $a$ pozitif sayısı için $a^p \equiv a (\mbox{mod } p)$ olduğunu göstereceğiz. Tümevarım $a=1$ için doğru. $a^p\equiv a(\mbox{mod } p)$ olsun. $(a+1)^p\equiv a+1 (\mbox{mod } p)$ olduğunu görelim. $(a+1)^p \equiv a^p + 1 (\mbox{mod } p)$ olduğundan tümevarım tamamlanır.
Kanıt 2. $p \nmid a$ olsun ve $a,2a,3a,\ldots,(p-1)a$ sayılarını ele alalım. $i\neq j$ ve $i,j\in\{1,2,\ldots, p-1\}$ olmak üzere $ia\equiv ja (\mbox{mod } p)$ ise $p\nmid a$ olduğundan $i=j$ çelişkisi elde edilir. Böylece
$$a(2a)(3a)\cdot (p-1)a\equiv (p-1)! (\mbox{mod } p) $$
ve $(p-1)!a^{p-1}\equiv (p-1)! (\mbox{mod } p)$ olur. $p$ ve $(p-1)!$ aralarında asal olduğundan $a^{p-1} \equiv 1 (\mbox{mod } p)$ elde edilir.
Şimdi bu teoremin bir genellemesini verelim.
Teorem. (Euler) $\phi(m)$ bir $m$ sayısından küçük ve $m$ ile arasında asal olan sayıların sayısı olsun. $(a,m)=1$ ise $$a^{\phi(m)}\equiv 1 (\mbox{mod } p)$$
Kanıt 1. $x_1, x_2, \ldots, x_{\phi(m)}$ sözü edilen sayılar olsun. $(ax_i,m)=1$ olur. Ayrıca $ax_i\equiv ax_j (\mbox{mod } m), i\neq j,$ ise $x_i\equiv x_j (\mbox{mod } p)$ çelişkisi elde edilir. Böylece
$$(ax_1)(ax_2)\cdots(ax_{\phi(m)}) \equiv x_1x_2\cdots x_{\phi(m)} (\mbox{mod } m)$$
ve $m$ ile $x_1x_2\cdots x_{\phi(m)}$ aralarında asal olduğundan $a^{\phi(m)}\equiv 1(\mbox{mod } p)$ elde edilir.
Kanıt 2. $m$ sayısını asal çarpanlarına $m=\prod p^a$ şeklinde ayıralım. Çarpımdaki her $p^a$ için $a^{\phi(m)}\equiv 1 (\mbox{mod } p^a)$ olduğunu görmek yeterlidir. Bu ise, $\phi(p^a)=p^{a-1}(p-1)$ olduğundan
$$a^{p^{a-1}}(p-1)\equiv 1 (\mbox{mod } p^a)$$
olduğunu görmeye denktir. Şimdi şunu gösterelim. $a>0$ ve $m\equiv 1 (\mbox{mod } p^a)$ ise $m^p\equiv 1 (\mbox{mod } p^{a+1})$ olur. $m=1+kp^a$ alalım.
$$m^p = (1+kp^a)^p = (kp^a)^p+\binom{p}{1}(kp^a)^{p-1}+\binom{p}{2}(kp^a)^{p-2}+ \cdots + \binom{p}{p-2}(kp^a)^2+\binom{p}{p-1}kp^a+1$$
$1\leq k \leq p-1$ için $p\mid \binom{p}{k}$ ve $a+1<2a+1<3a+1<\cdots$ olduğundan göstermek istediğimiz $m^p\equiv 1 (\mbox{mod } p^{a+1})$ elde edilir. $a^{p-1}\equiv 1 (\mbox{mod } p^a)$ olduğunu biliyoruz. Az önceki yardımcı sonucu kullanarak
$$a^{p(p-1)} \equiv 1 (\mbox{mod } p^2)$$
$$a^{p^2(p-1)} \equiv 1 (\mbox{mod } p^3)$$
$$\vdots$$
ve
$$a^{p^{a-1}(p-1)} \equiv 1 (\mbox{mod } p^a)$$
elde ederiz.
Kanıt 3. Grup kavramından yararlanacağız.
$$M=\{k:(k,m)=1 \mbox{ ve } 1\leq k<m\}$$
olsun. $M$ üzerinde şöyle bir $\cdot$ işlemi tanımlayalım. $a\in M$ ve $b\in M$ alalım. $1\leq c<m$ için $ab\equiv c (\mbox{mod } m)$ ise $a\cdot b=c$ olsun. $M$ nin bir grup olduğunu gözleyeceğiz. Birleşme özelliği doğal olarak var. $M$ nin kapalı olduğunu görelim. $a,b\in M$ ise $a\cdot b=c\in M$ olduğunu görelim.$(a,m)=(b,m)=1, 1\leq c<m$, $ab\equiv c(\mbox{mod } m), m | ab-c$ ve $(m,c)>1$ ise $q<1$ için $q\mid ab$ ve $q\mid m$ elde edilir. Fakat $(ab,m)=1$ olduğundan bir çelişki elde ederiz. $a\in M$ için $a1\equiv a(\mbox{mod } m)$ olduğundan 1 etkisiz elemandır. Ters elemanın varlığı için, $a\cdot a^{-1}=1$ yani $ax\equiv 1 (\mbox{mod } m)$ olacak şekilde bir $x$ lazım. $(a,m)=1$ ise $ax_0+m y_0=1$ olacak şekilde $x_0,y_0\in\mathbb{Z}$ vardır (bu sayılar Öklit algoritmasıyla bulunabilir) $ax_0\equiv 1(\mbox{mod } m)$ dir. $x_0\equiv z_0 (\mbox{mod } m)$ ve $1\leq z_0<m$ olacak şekilde bir $z_0$ alırsak $a^{-1}=z_0$ olur. $M$ bir gruptur. Bu grubun eleman sayısı $\phi(m)$ dir. Bir $a\in M$ alalım. $M$ sonlu olduğu için $a^t=1$ olacak şekilde minimum bir $t$ sayısı vardır. Böylece $1,a^1,\ldots,a^{t-1}$ elemanları $M$ nin bir çembersel alt grubunu oluştururlar. Alt grubun eleman sayısı $\phi(m)$ nin bir böleni olduğundan $a^{\phi(m)}=1$ ve $a^{\phi(m)}\equiv 1 (\mbox{mod } m)$ elde edilir.
Son olarak $\phi(x)$ fonksiyonundan söz edelim.
Teorem. $(a,b)=1$ ise $\phi(ab)=\phi(a)\phi(b)$.
Kanıt. $s_1,s_2,\ldots, s_{\phi(b)}$ sayıları $b$ ile aralarında asal sayılar $r_1,r_2,\ldots,r_{\phi(a)}$ ise $a$ ile aralarında asal sayılar olsun. $as_i+br_j$ sayılarına $(\mbox{mod } ab)$ de bakalım.
$$as_i+br_j\equiv as_{i’}+br_{j’} (\mbox{mod } ab)$$
olur ve buradan da
$$s_i\equiv s_{i’} (\mbox{mod } b)$$
$$r_j\equiv r_{j’} (\mbox{mod } b)$$
$$i=i’$$
$$j=j’$$
elde edilir. $(as_i+br_j,ab)=d$ olsun. $d\mid as_i+br_j, d\mid ab, p\mid d$ ve $p$ asal olacak şekilde bir $p$ alalım. $p|ab$ ise $p|a$ veya $p|b$ dir. $p|as_i+br_j$ ve $p|a$ ise $p|br_j$ ve $(a,r_j)=1$ vereceğinden $p|b$ olur, fakat bu mümkün değil. $p|b$ hali de aynı; dolayısıyla $d=1$ olmalı. Böylece $\phi(a)\cdot \phi(b)\leq \phi(ab)$ elde edilir. Eğer $(x,ab)=1$ ise $(x,a)=1$ ve $(x,b)=1$ olduğu görülebilir. Böylece $\phi(ab)\leq \phi(a)\cdot\phi(b)$ ve $\phi(ab)=\phi(a)\cdot\phi(b)$ elde ederiz, ve kanıt sona erer.
$\phi(x)$ fonksiyonu çarpımı koruyan bir aritmetik fonksiyon örneğidir.
$$m=p_1^{r_1}\cdots p_k^{r_k}$$
ise
$$\phi(m)=\phi(p_1^{r_1})\cdots \phi(p_k^{r_k})$$
elde edilir. Kolayca
$$\phi(p_i^{r_i})=p_i^{r_i}\bigg(1-\frac{1}{p_i}\bigg)$$
olduğundan
$$\phi(m)=m\prod_{p|m}\bigg(1-\frac{1}{p}\bigg)$$
elde edilir.
Teorem. $\sum_{d|n}\phi(d)=n$ olur.
Kanıt. Sağ taraf $1\leq x\leq n$ şeklindeki sayıların sayısı; şimdi bu sayıları bir şekilde sayalım. $(x,n)=d$ ise $\bigg(\frac{x}{d},\frac{n}{d}\bigg)=1$ olur. Bu tür sayıların sayısı $\phi\bigg(\frac{n}{d}\bigg)$ dir. Böylece
$$n=\sum_{d|n}\phi\bigg(\frac{n}{d}\bigg)=\sum_{d|n}\phi(d)$$
elde ederiz.
$\phi(a)\cdot\phi(b)=\phi(ab)$ olduğu kullanılarak da
$$\sum_{d|n}\phi(d)=n$$
olduğu gösterilebilir. Bunu okuyucuya bırakacağız.
KAYNAKÇA
[1] G.H. Hardy & E.M.Wright, An Introduction to the Theory of Numbers, 5.baskı, Oxford.
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 İsmail Üçağıl‘a 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.
