Yazan: Emre Alkan (Boğaziçi Üniversitesi Matematik Bölümü öğrencisi)
Yıl: 1995-3
Sayı: 23
Fermat ve Euler teoremlerini daha önce kanıtlarıyla beraber vermiştik [1]. Bu teoremlerin kullanılışını sergilemek amacıyla bu yazıda bir dizi uygulama yapacağız. Bu yazıda sayı kelimesi tamsayı anlamında kullanılacak.
Lemma: $(a, m)=1$ olsun. $a^{x} \equiv 1 \pmod{m}$ olacak şekildeki en küçük $x$ sayısı $n$ olsun. $a^{k} \equiv 1 \pmod{m}$ ise $n \mid k$ olur.
Kanıt: $a^{x} \equiv 1\pmod{m}$ olacak şekilde en küçük bir $x$ sayısı vardır, çünkü Euler teoremiyle $a^{\phi(m)} \equiv 1\pmod{m} $ olduğunu biliyoruz. Bu en küçük sayı $n$ olsun. Bölme algoritmasıyla $k=q n+r$ $(0 \leq r<n)$ yazılabilir. Böylece $a^{k} \equiv a^{q n+r} \equiv a^{r} \equiv 1\pmod{m}$ elde edilir. $n$ en küçük pozitif sayı olduğundan $r=0$, dolayısıyla $n \mid k$ elde edilir.
Problem: $p$ bir asal sayı ve $(p, m)=1$ olmak üzere $n=p^{k} m$ olsun. $p \mid 2^{n}-1$ ise, $p \mid 2^{m}-1$ olduğunu gösteriniz.
Çözüm: $n=p t$ olsun.
$$2^{t p}-1=\left(2^{p}-1\right)\left(2^{(t-1) p}+2^{(t-2) p}+\cdots+2^{p}+1\right).$$
Fermat teoremiyle $2^{p} \equiv 2\pmod{p}$ olduğundan $p$, $2^{p}-1$ ‘i bölmez. Böylece
$$
p \mid 2^{(t-1) p}+2^{(t-2) p}+\cdots+2^{p}+1 . $$ Kolayca
$$ 2^{(t-1) p}+2^{(t-2) p}+\cdots+2^{p}+1 \equiv 2^{t-1}+2^{t-2}+\cdots+2+1 \equiv 2^{t}-1\pmod{p}$$ olduğundan, $p \mid 2^{t}-1$ elde edilir. Bu sonucu yineleyerek $p \mid 2^{m}-1$ elde ederiz.
Problem: $n>1$ ise $n$, $2^{n}-1$’i bölmez.
Çözüm: $n>1$ ise $n$ asal çarpanlarına ayrılabilir. En küçük asal çarpan $p$ olsun. $n=p^{k} p_{1}^{k_{1}} \cdots p_{r}^{k r}$ yazalım. $n \mid 2^{n}-1$ kabul edelim. Böylece $2^{n} \equiv 1\pmod{p}$ ve Fermat teoremiyle $2^{p-1} \equiv 1\pmod{p}$ elde ederiz. Lemma ile $2^{k} \equiv 1\pmod{p}$ olacak şekilde en küçük $k>1$ sayısı vardır. $k=1$ olamaz; $k \mid n$ ve $k \mid p-1$ olur. Fakat böyle bir $k$ sayısının olamayacağı açıktır. Dolayısıyla $n$, $2^{n}-1$’i bölmez.
Problem: $n_{1}, n_{2}, \ldots, n_{k}$ pozitif tamsayıları için $n_{1}\mid 2^{n_{2}}-1, \, n_{2} \mid 2^{n_{3}}-1,\, \ldots,\, n_{k-1} \mid 2^{n_{k}}-1$ ve $n_{k} \mid 2^{n_{1}}-1$ ise, $n_{1}=n_{2}=\cdots=n_{k}=1$ olduğunu gösteriniz.
Çözüm: $n_1 > 1$ olsun. $n_1$, asal çarpanlarına ayrılabilir. $n_1$’in en küçük asal çarpanı $p_1$ olsun. $p_1\mid 2^{n_2}-1$ şeklinde ifade edilebilir, yani $2^{n_2} \equiv 1 \pmod{p_1}$ ve $2^{p_1-1} \equiv 1\pmod{p_1}$ Fermat teoremi sayesinde yazılabilir. Bir lemma ile $2^d \equiv 1\pmod{p_1}$ olacak şekilde en küçük bir $d > 1$ sayısı bulabiliriz. Bu, $p_2$ adında bir asal sayısı bulunduğu anlamına gelir, ki $p_2 \mid n_2$ ve $p_2 \mid p_1-1$. Bu düşünceyi devam ettirerek şöyle bir asal sayılar dizisi elde edilir: $p_3 \mid n_3$ ve $p_3 \mid p_2-1,\, \ldots,\, p_k \mid n_k$ ve $p_k \mid p_{k-1}-1$. Sonuç olarak, $n_k \mid 2^{n_1}-1$ olduğundan, $p_k \mid 2^{n_1}-1$ olur ve bundan dolayı öyle bir asal $p’$ bulunur ki $p’ \mid n_1$ ve $p’ \mid p_k-1$ olur. Bu nedenle $p_1-1 > p_2,\, p_2-1 > p_3,\, \ldots, \, p_k-1 > p_k$ ve $p_k-1 > p’$ elde edilir. Fakat $p’ \geq p_1$ olduğundan, bu durum mümkün değildir. Dolayısıyla, $n_1 = 1$ olur ve böylece $n_1 = n_2 = \cdots = n_k = 1$ elde edilir.
Problem: Bir $m$ pozitif sayısı veriliyor. $M$, $2^{k}-2^{m}-1$ $(k=1,2, \ldots)$ şeklindeki sayıların kümesi olsun. $M$’nin herhangi iki elemanı arasında asal bir sonsuz alt kümesi olduğunu gösteriniz.
Çözüm: İstenen alt kümeyi tümevarımla kuracağız. Herhangi bir $a_{1} \in M$ ile başlayalım. Kabul edelim ki ilk $n$ sayı $a_{1}, a_{2}, \ldots, a_{n} \in M$ şartını sağlasın. $a_{n+1}$ için, $\left(a_{n+1}, a_{i}\right)=1$ $(i=1,2, \ldots, n)$ olmalıdır. $a_{1}, a_{2}, \ldots, a_{n}$ elemanlarının hepsinin asal çarpanlara ayrılışında geçen asal sayılar $p_{1}, p_{2}, \ldots, p_{\text {r }}$ olsun. $$a_{n+1}=2^{\left(p_{1}-1\right)\left(p_{2}-1\right) \cdots\left(p_{r}-1\right)}-2^{m}-1 $$
olarak seçelim. Eğer $\left(a_{n+1}, a_{i}\right)>1$ ise ${1,2, \ldots, r}$ içinde bir $j$ için $p_{j} \mid a_{n+1}$ olmalıdır. Kolayca
$$
2^{\left(p_{1}-1\right)\left(p_{2}-1\right) \cdots\left(p_{r}-1\right)} \equiv 2^{m}+1 \pmod{p_j}
$$
elde edilir. Öte yandan $2^{p_{j}-1} \equiv 1 \pmod{p_{j}}$ Fermat teoremiyle yazılabilir. Bu iki denklikten $2^{m}+1 \equiv 1\pmod{p_{j}}$ ve $p_{j}=2$ elde edilir ki bu mümkün değildir. $\left(a_{n+1}, a_{i}\right)=1$ olur. Dolayısıyla tümevarımla $M$’nin böyle bir sonsuz alt kümesinin varlığı anlaşılır.
Problem: (1990 Uluslararası Matematik Olimpiyatı) $n^{2} \mid 2^{n}+1$ olacak şekildeki tüm $n>1$ sayılarını bulunuz.
Çözüm: $n^{2} \mid 2^{n}+1$ ise $n \mid 2^{n}+1$ olur. $n>p$ ise $3 \mid n$ olduğunu görelim. $n$ ‘nin en küçük asal çarpanı $p$ olsun. $2^{2 n} \equiv 1\pmod{p}$ ve $2^{p-1} \equiv 1\pmod{p}$ Fermat teoremiyle yazılabilir. $2^{d} \equiv 1 \pmod{p}$ olacak şekilde en küçük bir $d>1$ sayısı vardır. $d \mid 2 n$ ve $d \mid p-1$ ‘den kolayca $d=2$ elde edilir. Dolayısıyla $p=3$ ve $3 \mid n$ olur. $n=3^{k} d$, $(d, 3)=1$ ve $k \geq 1$ alalım. $3^{2 k} \mid 2^{3^{k} d}+1$ yazılabilir. Çarpanlara ayırma ile
$$
2^{3^{k} d}+1=\left(2^{d}+1\right) \prod_{t=0}^{k-1}\left(2^{3^{t} 2 d}-2^{3^{t} d}+1\right)
$$
yazılabilir. Şunları gözleyelim:
$$
2^{3^{t} 2 d}-2^{3^{t} d}+1 \equiv 2^{3^{t} d}-2 \equiv 0\pmod{3}
$$
ve $2^{3^{t} d} \equiv 2\pmod{9}$ ise, $(-1)^{d} \equiv 2\pmod{9}$ olur ki bu mümkün değildir. Öte yandan $(d, 3)=1$ olduğundan $2^{d} \equiv-1\pmod{3}$ ve $2^{d} \not \equiv-1\pmod{9}$ olur. Böylece $2^{3^{k} d}+1$, tam olarak $3^{k+1}$ ile bölünür. Kolayca $2 k \leq k+1$ ve $k \geq 1$’den $k=1$ elde ederiz. $n=3 d$ şeklinde olmalıdır. $d>1$ ise $d$’nin en küçük asal çarpanı $p_{1}$ olsun. Kolayca $2^{2 \cdot 3 d} \equiv 1\pmod{p_{1}}$ ve $2^{p_{1}-1} \equiv 1\pmod{p_{1}}$ Fermat teoremiyle yazılabilir. Öte yandan $p_{1} \geq 5$ olmalıdır. $2^{a} \equiv 1 \pmod{p_{1}}$ olacak şekilde en küçük bir $a>1$ sayısı vardır. $a \mid 6 d$ ve $a \mid p-1$ olduğundan $a=2,3$ veya $6$ olur. $a=2$ ise $p_{1}=3$ olur. $a=3$ veya $6$ ise de $p_{1}=7$ elde edilir. Fakat her $s \in \mathbb{Z}^{+}$için $7 \nmid 2^{s}+1$ olduğundan, $d>1$ olamaz; $d=1$ elde edilir. $n^{2} \mid 2^{n}+1$ olacak şekildeki tek sayı $n=3$ olarak bulunur.
Problem: $a$ ve $b$ pozitif sayıları için, $2 a-1$, $2 b-1$ ve $a+b$ asal sayılar iseler, $a+b$ ‘nin $a^{b}+b^{a}$ ve $a^{a}+b^{b}$ sayılarını bölmediğini gösteriniz.
Çözüm: $(a, a+b)=(b, a+b)=(a b, a+b)=1$ ve
$$a+b \mid\left(a^{a}+b^{b}\right)\left(a^{b}+b^{a}\right)=a^{a+b}+b^{a+b}+(a b)^{a}+(a b)^{b}$$ olur. $a>b$ ve Fermat teoremiyle
$$
a^{a+b}+b^{a+b} \equiv a+b \equiv 0 \pmod{ a+b}
$$
kabul edebiliriz. Kolayca $(a b)^{a-b} \equiv-1\pmod{ a+b}$, yani $(a b)^{2 a-2 b} \equiv 1\pmod{ a+b}$ elde edilir. Öte yandan yine Fermat teoremiyle $(a b)^{a+b-1} \equiv1\pmod{ a+b}$ olur. $(a b)^{d} \equiv 1\pmod{ a+b}$ sağlayan en küçük bir $d$ sayısı vardır. $d=1$ ise $a b \equiv 1\pmod{ a+b}$ ve $(a b)^{a-b} \equiv 1\pmod{ a+b}$ olur ki bu mümkün değildir. $d \mid 2 a-2 b$ ve $d \mid a+b-1$ ‘den kolayca $d \mid 2(2 a-1)$ ve $d \mid 2(2 b-1), 2 a-1$ ve $2 b-1$ de asal olduğundan $d=2$ buluruz. $(a b)^{2} \equiv 1\pmod{ a+b}$ ve $a b \not \equiv 1\pmod{a+b}$ olduğundan $a b \equiv-1\pmod{ a+b}$. yani $a+b \mid a b+1$ elde edilir. Öte yandan $a+b\mid a^{2}+a b,\, a+b\mid(a-1)(a+1)$, ve $a+b$ asal olduğundan $a+b \mid a-1$ veya $a+b \mid a+1$ elde edilir ki her iki durum da mümkün değildir.
Problem: $a, m$ pozitif sayıları için $x_{0}=1$ ve $x_{n+1}=a^{x_{n}}$ olacak şekilde bir $x_{n}$ dizisi tanımlanıyor. Öyle bir $N$ pozitif sayısının varlığını gösteriniz ki $N \leq h \leq k$ için $x_{h} \equiv x_{k} \pmod{m}$ olsun [7].
Çözüm: $\langle a \rangle = \{a, a^2, a^3, \ldots\}$ kümesi $\pmod{m}$de periyodik olur. Periyot uzunluğu $b$ olsun. Bu kümede periyodik olmayan terimler olabilir, ama belli bir sınırdan sonra kümenin kendisi periyodik olmalıdir. Belli bir $a^{k}$ ‘den sonra
$$
x_{h}=a^{a^{a^{\cdot^{\cdot^{\cdot}}}}} \quad \text { ve } \quad x_{k}=a^{a^{a^{\cdot^{\cdot^{\cdot}}}}}
$$
olduğundan $x_{h}=x_{k}\pmod{m}$ ancak ve ancak $x_{h-1} \equiv x_{k-1}\pmod{b}$ elde ederiz. $(a, m)>1$ ise $a^{x} \equiv 1\pmod{m}$ olacak şekilde bir $x$ pozitif sayısı yoktur. Böylece $b<m$ olur. Öte yandan $(a, m)=1$ ise, Euler teoremiyle $a^{\phi(m)} \equiv 1 \pmod{m}$ olur ki bundan yine $b \leq \phi(m)<m$ elde edilir. Dolayısıyla bu akıl yürütme tekrarlanarak, elde edilen modül tabanları azalan bir dizi oluştururlar. Sonlu sayıda adımdan sonra (diyelim ki $t$ ‘yinci adım) $x_{h-t} \equiv x_{k-t}\pmod{2}$ eşdeğer koşulu elde edilir. Fakat $\pmod{2}$ ‘de dizinin tüm terimlerinin, $x_{0}$ terimi hariç, denk olacağı açıktır. Eğer $N$ sayısı, $N \geq t$ olacak şekilde seçilirse istenen $N \leq h \leq k$ için $x_{h} \equiv x_{k}\pmod{m}$ elde edilir.
Şimdi $N \leq h \leq k$ ve $x_{h} \equiv x_{k}\pmod{m}$ olacak şekilde bir $N$ bulmak istiyoruz. Azalan bir modül dizisi bulduk. Böylece $\pmod{2}$’ye indirgeme en fazla $m$ adımda biter. Fakat her adımda bir sonraki modüle geçebilmek için bazı şartlar vardır. $x_{h} \equiv x_{k}\pmod{m}$ ise $x_{h-1} \equiv x_{k-1}\pmod{b}$, $a^{i} \equiv a^{j}\pmod{m}$ ve $i< j$ olacak şekilde en küçük sayı $i$ ise, $x_{h-1}\geq i$ olmalıdır. Elde edelen azalan modül dizisi $b_1,\ldots, b_s$ olsun. Her defasında $a_i \equiv b_i \pmod{b_i}$ ve $i<j$ olacak şekilde en küçük $i$ sayısı için $i < b_i < m$ olur. Şimdi başlangıç için $x_h$’yi $x_{h}=a^{a^{a^{\cdot^{\cdot^{\cdot}}}}}$ olarak seçebiliriz. $a^{a^{a}} > m$ olacak şekilde bir $x$ sayısı bulabiliriz. İndirgeme en fazla $m$ adım sürebileceğinden (her adımda bir $a$ eksiliyor), $x_{h}$ ‘yi $x_{h}=a^{a^{a^{a^{\cdot^{\cdot^{\cdot}}}}}} a^{a^{a^{\cdot^{\cdot^{\cdot}}}}}$ olarak seçeriz. $\quad h-1=x+m$ olacağından $N=x+m+1$ almak işimizi görür.
Problem: $a, b$ pozitif sayılar ve $p$ asal olmak üzere, $a^{p} \equiv b^{p}\pmod{p}$ ise, $a^{p} \equiv b^{p} \pmod{p^2}$ olduğunu gösteriniz.
Çözüm: Fermat teoremiyle $a^{p} \equiv a\pmod{p}$ ve $b^{p} \equiv b\pmod{p}$ olduğundan, $a \equiv b\pmod{p}$ ve $p \mid a-b$ elde ederiz.
$$a^{p}-b^{p}=(a-b)\left(a^{p-1}+a^{p-2} b+\cdots+a b^{p-2}+b^{p-1}\right)$$
ve $i=1,2, \ldots, p$ için $a^{p-i} b^{i-1} \equiv a^{p-1} \equiv 1\pmod{p}$ olduğundan,
$$
p \mid \frac{a^{p}-b^{p}}{a-b}
$$
elde edilir. Dolayısıyla $a^{p} \equiv b^{p}\pmod{p^2}$ olur. Burada $(a, p)=(b, p)=1$ olduğunu kabul ettik. Eğer $p \mid a$ ve $p \mid b$ ise $p^{p} \mid a^{p}-b^{p}$ olur ki $p \geq 2$ olduğundan yine $a^{p} \equiv b^{p}\pmod{p^2}$ elde ederiz.
Şimdi Euler teoreminin bir genellemesini vereceğiz. Önce bir Lemma.
Lemma: $n$ pozitif sayısının pozitif bir böleni $d$ ise, $n-\phi(n) \geq d-\phi(d)$ olur.
Kanıt: Sol taraf $n$ ile ortak asal böleni olan sayıların sayısıdır. Sağ taraf da aynı şekilde belirtilebilir. $d \mid n$ olduğundan $d$ ile ortak asal böleni olan bir sayının, $n$ ile de ortak asal böleni olacaktır.
Teorem: Herhangi $a$ ve $m$ pozitif sayıları için $a^{m} \equiv a^{m-\phi(m)}\pmod{m}$ olur.
Kanıt: $m \mid a^{m-\phi(m)}\left(a^{\phi(m)}-1\right)$ olduğunu göreceğiz. $m=p_{1}^{\alpha_{1}} \cdots p_{r}^{\alpha_{r}} q_{1}^{\beta_{1}} \cdots q_{k}^{\beta_{k}}$ olacak şekilde çarpanlara ayıralım. Burada $p_{1}, p_{2}, \ldots, p_{r}$, $a$ ‘nın da asal bölenleri olsunlar. $i \in\{1,2, \ldots, k\}$ için Euler teoremiyle $a^{\phi\left(q_{i}^{\beta_{i}}\right)}-1 \mid a^{\phi(m)}-1$ ve $q_{i}^{\beta_{1}} \mid$ $a^{\phi\left(q_{i}^{\beta_{i}}\right)}-1$ olduğundan, $q_{i}^{\beta_{i}} \mid a^{m-\phi(m)}\left(a^{\phi(m)}-1\right)$ elde ederiz. Şimdi bir $p_{i}^{\alpha_{i}}$ alalım. $p_{i}^{\alpha_{i}} \mid a^{m-\phi(m)}$ olduğunu göstereceğiz. $p_{i} \mid a$ olduğundan $\alpha_{i} \leq$ $m-\phi(m)$ olduğunu görmek yeter. Lemma ile $m-\phi(m) \geq p_{i}^{\alpha_{i}}-\phi\left(p_{i}^{\alpha_{i}}\right)=p_{i}^{\alpha_{i}-1}$ elde ederiz. $p_{i} \geq 2$ olduğundan $2^{\alpha_{i}-1} \geq \alpha_{i}$ olduğunu görmek yeter. $n \geq 1$ için $2^{n-1} \geq n$ olduğu tümevarımla gösterilebilir.
Şu sonucu daha önce göstermiştik [2].
Teorem: Tamsayı katsayılı, sabit olmayan bir $p(n)$ polinomu, belli bir sınırdan sonraki her $n$ sayısı için asal olamaz.
Bu sonucu benzer daha ilginç bir teoremi göstereceğiz.
Teorem: $1 \leq a_{1}<a_{2}<\cdots<a_{m}$ tamsayılar ve $Q_{j}(x)$ ‘ler tamsayı katsayılı polinomlar olsun.
$$ f(n)=Q_{1}(n) a_{1}^{n}+Q_{2}(n) a_{2}^{n}+\cdots+Q_{m}(n) a_{m}^{n} $$ ise, $f(n)$ sonsuz sayıda tamsayı $n$ için asal değerler almaz. $(n \rightarrow \infty$ iken $f(n) \rightarrow \infty$ olduğu kabul ediliyor.)
Kanıt: Tersine $f(n)$’nin belli bir sınırdan sonra hep asal olduğunu kabul edelim. $f(n) \rightarrow \infty$ olduğundan öyle bir $n$ bulunabilir ki $p$ asal olmak üzere, $f(n)=p>a_{m}$ olsun. Her $k$ tamsayısı için $Q_{i}(n+k p) \equiv Q_{i}(n) \pmod{ p}$ olduğunu biliyoruz. Öte yandan $\left(a_{i}, p\right)=1$ olduğundan, Fermat teoremiyle $a_{i}^{p-1} \equiv 1\pmod{ p}$ yazabiliriz. Bu iki sonucu aynı anda kullanabilmek için, $f(n+k p(p-1))$ sayılarına bakılırsa,
$$
f(n+k p(p-1)) \equiv f(n) \pmod{ p}
$$
olduğu görülür ki $f$ hep asal kabul edildiğinden, $f(n+k p(p-1))=p$ elde edilir. Bu ise $n \rightarrow \infty$ iken $f(n) \rightarrow \infty$ olmasıyla çelişir.
Şimdi Fermat teoreminin tersinden bahsedeceğiz. $a, m$ pozitif sayıları için, $a^{m-1} \equiv 1$ $\pmod{m}$ ise $m$ asal olur mu? Bunun her zaman doğru olmadığını görelim.
Teorem: $a$ pozitif bir sayı ise, $a^{m-1} \equiv 1\pmod{ m}$ olacak şekilde asal olmayan sonsuz tane $m$ sayısı bulunabilir.
Kanıt: $(a, p)=1$ olacak şekilde bir $p \geq 3$ asal sayısı alalım.
$$
m=\frac{a^{2 p}-1}{a^{2}-1}=\left(\frac{a^{p}-1}{a-1}\right)\left(\frac{a^{p}+1}{a+1}\right)
$$
olsun; $m$ asal değildir. Kolayca, $a^{2 p} \equiv 1 \pmod{m}$ olur. Eğer $2 p \mid m-1$, eşdeğer olarak
$$
2 p\left(a^{2}-1\right) \mid a^{2}\left(a^{p-1}-1\right)\left(a^{p-1}+1\right)
$$
olmasını sağlarsak teorem kanıtlanmış olacak. Fermat teoremiyle, $p \mid a^{p-1}-1$. Öte yandan $p-1$ çift olacağından $a^{2}-1 \mid a^{p-1}-1$, ve $p$ üzerine $p \nmid a^{2}-1$ şartı da getirilirse, $p\left(a^{2}-1\right) \mid$ $a^{p-1}-1$ elde edilir. $2 \mid a^{2}\left(a^{p-1}+1\right)$ olduğu açıktır. $p \nmid a\left(a^{2}-1\right)$ olacak şekilde sonsuz tane $p$ seçimi bulunacağından teorem elde edilir.
Tanım: $a^{m-1} \equiv 1\pmod{ m}$ ve $m$ asal olmayacak şekildeki $m$ sayılarına yalancı asal denir.
Şu sonuç Fermat teoreminin tersi olarak kabul edilebilir.
Teorem: $a^{m-1} \equiv 1\pmod{ m}$, $x<m-1$ ve $x \mid m-1$ için $a^{x} \not \equiv 1 \pmod{m}$ ise, $m$ asaldır.
Kanıt: $a^{d} \equiv 1 \pmod{m}$ olacak şekilde en küçük bir $d$ sayısı vardır. $d \mid m-1$ olacağından $d=m-1$ olmalıdır. Öte yandan $(a, m)=$ 1 olduğundan, Euler teoremiyle $a^{\phi(m)} \equiv 1 \pmod{ m}$ yazılabilir ve kolayca $m-1 \mid \phi(m)$ olur. Fakat $\phi(m) \leq m-1$ olduğundan $\phi(m)=m-1$ olur ki bu $m$ ‘nin asal olması demektir.
Problem: $n>3$ bir tek sayı olsun. $p \mid 2^{\phi(n)}-1$ ve $p \nmid n$ olacak şekilde bir $p$ asal sayısının var olduğunu gösteriniz [5].
Çözüm: $n=p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{r}^{k_r}$ ve $p_{i}$ ‘ler asal olsun.
$$
\phi(n)=p_{1}^{k_{1}-1} p_{2}^{k_{2}-1} \cdots p_{r}^{k_{r}-1}\left(p_{1}-1\right) \cdots\left(p_{r}-1\right)
$$
olur. $2^{\left(p_{1}-1\right) \cdots\left(p_{r}-1\right)}-1$ sayısını ele alalım. Bu sayının $p_{1}, p_{2}, \ldots, p_{r}$ sayılarından farklı bir asal böleni olduğunu gösterirsek,
$$
2^{\left(p_{1}-1\right) \cdots\left(p_{r}-1\right)}-1 \mid 2^{\phi(n)}-1
$$
olacağından problem sonuçlanmış olur. Eğer her $i=1,2, \ldots, r$ için $p_{i} \geq 5$ sağlanırsa, kolayca $3 \mid 2^{\left(p_{1}-1\right) \cdots\left(p_{r}-1\right)}-1$ elde edilir. Bu halde işimiz biter.
Öteki durumda genelliği bozmadan $p_{1}=3$ kabul edelim. Elimizdeki sayı $2^{2\left(p_{2}-1\right) \cdots\left(p_{r}-1\right)}-1$ olur; veya $n$ sayısında 3’ten başka asal sayı yoktur, yani $n=3^{k}$ ‘tür.
$$\begin{aligned} 2^{2(p_2-1) \dots (p_r-1)} – 1 &= \underbrace{\left(2^{(p_2-1) \dots (p_r-1)} – 1\right)}_a \cdot \underbrace{\left(2^{(p_2-1) \dots (p_r-1)} + 1\right)}_b \end{aligned}$$
ve $(a, b)=1$ olur. Öte yandan Fermat teoremiyle $p_{2} p_{3} \cdots p_{r} \mid a$ elde edilir. $b \equiv 2 \pmod{ 3}$ olduğundan $3 \nmid b$. Ayrıca $i=2,3, \ldots, r$ için $p_{i} \mid a$ olduğundan, $b$ sayısının yeni bir asal bölene ihtiyacı vardır: $p_{r+1} \mid b$. Kolayca $p_{r+1} \mid 2^{\phi(n)}-1$ ve $p_{r+1} \nmid n$ olur.
$n=3^{k}$ durumunda ise, $k \geq 1$ ise
$$
2^{\phi(n)}-1=2^{2 \cdot 3^{k-1}}-1
$$
olur. $k \geq 2$ ise $7 \mid 2^{\phi(n)}-1$ ve $7 \nmid n$ elde edilir. $k=1$ ise $n=3$ olmak üzere problemin şartı sağlanmaz. Dolayısıyla $n>3$ olan her tek $n$ sayısı için $p \mid 2^{\phi(n)}-1$ ve $p \nmid n$ olacak şekilde bir $p$ asal sayısı vardır.
Fermat ve Wilson teoremleri aynı teoremde birleştirilebilirler [3]:
Teorem: (Leo & Moser) Her $a$ pozitif sayısı ve $p$ asal sayısı için $p \mid(p-1) ! a^{p}+a$ olur.
Kanıt: $(p-1) ! a^{p}+a \equiv-a^{p}+a \equiv 0 \pmod{ p}$ Fermat ve Wilson teoremleriyle elde edilir. Tersine her $a$ için $p \mid(p-1) ! a^{p}+a$ ise $a=1$ alarak $p \mid(p-1) !+1$ Wilson teoremiyle elde edilir. Böylece $p \mid(p-1) ! a^{p}+a^{p}$ ve $p \mid a^{p}-a$ elde edilir ki bu da Fermat teoremidir.
Not: $[1]$’de sondan bir önceki teoremde $\phi(a b)=\phi(a) \phi(b)$ olduğunu gösterirken nasıl $\phi(a b) \leq \phi(a) \phi(b)$ elde ettiğimizi belirgin bir şekilde şöyle gösterebiliriz: $(x, a b)=1$ ise $(x, a)=(x, b)=1$ olur. Şu halde $x \equiv r_{i}\pmod{a}$ ve $x \equiv s_{j}\pmod{b}$ yazılabilir. $(a, b)=1$ olduğundan Çinli Kalan Teoremi’yle bu sistemin bir $x$ çözümü vardır ve $x$, $a$ ve $b$ ‘nin lineer kombinasyonu olarak yazılabilir. $x \equiv 1\pmod{a}$ ve $x \equiv 0\pmod{b}$ denkliklerinden $x=b t$ ve $b t \equiv 1\pmod{a}$ olacak şekilde bir $t$ bulunabilir, çünkü $(a, b)=1$ ‘dir. $(t, a)=1$ olduğundan $t \in \{r_1, r_2, \ldots, r_{\phi(a)}\}$. Benzer sekilde $x \equiv 0 \pmod{a}$ ve $x \equiv 1 \pmod{b}$ denkliklerinden $x=a t^{\prime}$ ve $a t^{\prime} \equiv 1\pmod{b}$ olacak şekilde bir $t^{\prime}$ bulunabilir; $\left(t^{\prime}, b\right)=1$ olduğundan $t^{\prime} \in \{s_{1}, s_{2}, \ldots, s_{\phi(b)}\}$. Şimdi $b t \equiv 1\pmod{a},\, t^{\prime} \equiv 0\pmod{a},\, t \equiv 0\pmod{b}$ ve $a t^{\prime} \equiv 1\pmod{b}$ denkliklerinden
$$
\begin{aligned}
b t r_{i} & \equiv r_{i}\pmod{a} & a t^{\prime} s_{j} & \equiv 0\pmod{a} \\
b t r_{i} & \equiv 0\pmod{b} & a t^{\prime} s_{j} & \equiv s_{j}\pmod{b}
\end{aligned}
$$
bulunur. Bunlar taraf tarafa toplanarak $b t r_{i}+a t^{\prime} s_{j} \equiv r_{i}\pmod{a}$ ve $b t r_{i}+a t^{\prime} s_{j} \equiv s_{j}\pmod{b}$ elde edilir. Kolayca $\left(t r_{i}, a\right)=1$ ve $\left(t^{\prime} s_{j}, b\right)=1$ olduğundan, $x=a s_{i}+b r_{j}$ biçiminde yazılır ve $\phi(a b) \leq \phi(a) \phi(b)$ olur.
Gene [1]‘de Euler Teoremi’nin 3. kanıtında $M$ ‘nin bir grup olduğunu gözlemeye çalıştık. $(a, m)=1$ olan her $a$ için $a x_{0} \equiv 1\pmod{m}$ olacak şekilde bir $x_{0}$ bulup $x_{0} \equiv z_{0}\pmod{m}$ alarak $z_{0}=a^{-1}$ dedik. Burada $\left(z_{0}, m\right)=1$ olduğu belirtilmelidir. $\left(x_{0}, m\right)=1$ olduğundan $\left(z_{0}, m\right)=1$ olduğu açıktır. Ters elemanın varlığı yetmez, o elemanın ayrıca $M$ ‘nin bir elemanı olması gerekir.
Kaynakça:
[1] $\quad$ E. Alkan, Fermat ve Euler Teoremleri. Matematik Dünyası, 4, sayı 3, 7-8 (1994).
[2] $\quad$ E. Alkan, Sayılar Teorisinde Çözülmemiş Problemler, Matematik Dünyası, 3, sayı 3, 17-21 (1993).
[3] $\quad$ S. Alpay, Wilson Teoremi, Matematik Dünyası. 3, sayı 4, 12-14 (1993).
[4] $\quad$ G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5. baskı, Clarendon, Oxford, 1979.
[5] $\quad$ C. A. Nicol & J. L. Selfridge, Problem E3452, American Mathematical Monthly, 98, 645 (1991).
[6] $\quad$ W. Sierpinski (çeviren A. Sharma), A Selection of Problems in the Theory of Numbers, Pergamon, Oxford, 1964.
[7] $\quad$ W. P. Wardlaw, Problem 10324, American Mathematical Monthly, 100, 688 (1993).
