$qk+1$ formatındaki asal sayılar

[Metin Can Aydemir]

$q$ tek bir asal sayı olmak üzere $p\equiv 1\pmod{q}$ olan sonsuz $p$ asalı olduğunu gösteriniz.

Not: $p$ ve $q$ tek olduğundan bu soru $p\equiv 1\pmod{2q}$ olan sonsuz asal olmasına da denktir.

[Metin Can Aydemir]

İspat 1 (Metin Aydemir): $q=3$ durumu burada ispatlanmıştı. Bu yüzden $q>3$ için göstermemiz yeterlidir. $x^q\equiv -1\pmod{p}$ denkliğine bakalım. $p$'yi tek kabul edeceğiz. $x$'in mertebesi $d$ olsun. Bu durumda $d\not\mid q$ olacaktır. Yani $d\neq 1,q$'dur. Ayrıca $$x^{2q}\equiv 1\pmod{p}\implies d\mid 2q\implies d=2,2q$$ olur. $d=2$ ise $x^2\equiv 1\pmod{p}$ olur ve buradan $x\equiv -1\pmod{p}$ elde edilir. Yani $x\equiv -1\pmod{p}$ veya $d=2q$'dur.

$p$ modundaki bir sayının mertebesi her zaman $p-1$'in bir bölenidir. Dolayısıyla eğer $d=2q$ ise $2q\mid p-1$ ve $p\equiv 1\pmod{2q}$ olmalıdır. Yani $$x^q\equiv -1\pmod{p}\implies x\equiv -1\pmod{p}\text{  veya  }p\equiv 1\pmod{q}$$ olacaktır.

Şimdi ise $p\equiv 1\pmod{q}$ olan bir asal alalım. $p$ ve $q$ tek olduğundan $p\equiv 1\pmod{2q}$'dur.

Lemma: $d\mid p-1$ olan herhangi bir pozitif $d$ tamsayısı için mertebesi $d$ olan $\phi(d)$ (Euler totient fonksiyonu) kadar birbirine denk olmayan sayı vardır.

$2q\mid p-1$ olduğundan $\phi(2q)$ tane mertebesi $2q$ olan sayı vardır. Bunlardan birini alalım. $x_0$ olsun. $$x_0^{2q}\equiv 1\pmod{p}\implies (x_0^q-1)(x_0^q+1)\equiv 0\pmod{p}$$ olur. $p\mid x_0^q-1$ olamaz çünkü bu $x_0$'ın mertebesinin $2q$ olmasıyla çelişir. Dolayısıyla $$x_0^q\equiv -1\pmod{p}$$ olacaktır ve $x^q\equiv -1\pmod{p}$ denkliğinin çözümü olmuş olur. Sonuç olarak da $$x^q\equiv -1\pmod{p}\iff x\equiv -1\pmod{p}\text{  veya  }p\equiv 1\pmod{q}$$ elde edilir.

Şimdi sonlu sayıda asalın $qk+1$ formatında olduğunu kabul edelim. Bu asallar $r_1,r_2,\dots,r_k$ olsun. $$N=(2r_1r_2\cdots r_k)^q+1$$ sayısını inceleyelim. Bu sayı tektir ve $1$'den büyüktür*. Bu sayının bir asal bölenini alalım. Bu asal $p$ olsun. $$(2r_1r_2\cdots r_k)^q\equiv -1\pmod{p}\implies 2r_1r_2\cdots r_k\equiv -1\pmod{p}\text{   veya   } p\equiv 1\pmod{q}$$ olur. İkinci durumda bir $i$ için $p=r_i$ olması gerekeceğinden çelişkidir. Dolayısıyla $2r_1r_2\cdots r_k\equiv -1\pmod{p}$ olmalıdır. Bu $N$'yi bölen her asal için geçerlidir. $2r_1r_2\cdots r_k=x$ dersek, $$N=x^q+1=(x+1)(x^{q-1}-x^{q-2}+\cdots+1)$$ olduğundan ve $p\mid N$ olan her asal sayı için $p\mid x+1$ olduğundan ve $N>x+1$ olduğundan öyle bir $p$ asalı vardır ki hem $x+1$'i hem de $x^{q-1}-x^{q-2}+\cdots+1$'i bölüyordur. Bu $p$ asalı için $x\equiv -1\pmod{p}$ olduğundan $$x^{q-1}-x^{q-2}+\cdots+1\equiv (-1)^{q-1}-(-1)^{q-2}+\cdots +1\equiv q\equiv 0\pmod{p}\implies p=q$$ olur. Yani $q\mid N$ olmalıdır. $r_i\equiv 1\pmod{q}$ olduğundan $$2r_1r_2\cdots r_k\equiv 2\equiv -1\pmod{q}$$ elde edilir. Yani $q=3$ olmalıdır fakat başta $q>3$ kabul etmiştik. Bu bir çelişkidir. Dolayısıyla kabulümüz yanlıştır. Sonsuz sayıda asal $qk+1$ formatındadır.

Not*: İspatın tamamlanabilmesi için $qk+1$ formatında en az bir asal sayı olduğunu göstermeliyiz ki $N>1$ olsun. Bunun için de $2^q-1$ sayısına bakalım. Bu sayının herhangi bir asal böleni olan $p$ için $2$'nin mertebesi $d$ ise $$2^q\equiv 1\pmod{p}\implies d\mid q\implies d=1,q$$ olur. Eğer $d=1$ ise $2\equiv 1\pmod{p}$ olur, çelişki. Dolayısıyla $d=q$'dur ve buradan $d=q\mid p-1$ bulunur. Yani $qk+1$ formatında olan en az bir asal sayı vardır.

[Metin Can Aydemir]

İspat 2 (Metin Aydemir): Önceki sorunun not kısmında gösterdiğimiz gibi $2^q-1$ sayısının asal böleni $qk+1$ formatında olmalıdır. Şimdi daha genel hali olan $(n+1)^q-n^q$ sayısına bakalım. Bu soruda ispatlanıldığı gibi $(n+1)^q-n^q$'nun herhangi bir pozitif böleni $m$ için $q\mid m-1$ olmalıdır. Yani $(n+1)^q-n^q$ sayısının her asal böleni $qk+1$ formatındadır.

Sonlu sayıda $qk+1$ formatında asal sayısı olduğunu varsayalım. Bu asallar $p_1,p_2,\dots,p_k$ olsun. Bu durumda $n=p_1p_2\dots p_k$ seçersek, $(n+1)^q-n^q$ sayısının asal böleni $p_i$'lerden biri olmalıdır ($(n+1)^q-n^q>1$ olduğu barizdir). Ancak bu durumda $(p_1p_2\cdots p_k+1)^q-(p_1p_2\cdots p_k)^q\equiv 1\pmod{p_i}$ çelişkisi elde edilir. Dolaysıyla kabulumuz yanlıştır ve sonsuz sayıda $qk+1$ formatında asal sayı vardır.

[Metin Can Aydemir]

İspat 3 (Metin Aydemir): Sonlu sayıda $qm+1$ formatında asal sayı olduğunu varsayalım. $n_k=2^{q^k}-1$ sayılarını tanımlayalım. $k\geq 1$ için bu sayılar $1$'den büyük tek sayılardır. Eğer $p\mid n_k$ ise $p\neq q$ olmalıdır çünkü fermat teoreminden $$2^{q^{k}}-1\equiv \left(2^{q^{k-1}}\right)^q-1\equiv 2^{q^{k-1}}-1\equiv \cdots\equiv 2-1\equiv 1\pmod{q}$$ olacaktır. $2$'nin $p$ modundaki mertebesi $d$ ise $p\mid 2^{q^k}-1$ olduğundan $d\mid q^k$ olmalıdır. $d\neq 1$ olması gerektiğinden $d=q^a$ formatındadır. $d\mid p-1$ olduğundan $q^a\mid p-1$ ve $q\mid p-1$'dir. Yani $n_k$ sayılarını bölen her asal sayı $qm+1$ formatındadır. Eğer sonlu sayıda $qm+1$ formatında asal sayı varsa, $(n_k)$ dizisinin terimlerini bölen farklı asal sayılar sonlu sayıda olmalıdır. Öyle bir $K$ doğal sayısı vardır ki $n_1,n_2,\cdots, n_K$ terimleri olası tüm asal bölenleri içerecektir. $$n_{K+1}=2^{q^{K+1}}-1=(2^{q^K}-1)\left(\left(2^{q^K}\right)^{q-1}+\left(2^{q^K}\right)^{q-2}+\cdots+2^{q^K}+1\right)=n_K\left(\left(2^{q^K}\right)^{q-1}+\left(2^{q^K}\right)^{q-2}+\cdots+2^{q^K}+1\right)$$ olacaktır. $n_{K}\mid n_{K+1}$ olduğundan aynı işlemi tekrarlarsak, $i=1,2,\dots,K$ için $n_i\mid n_{K}$ olacaktır. Yani $n_{K}$ sayısı olası tüm asallara bölünüyordur. $n_{K+1}$ sayısı da olası tüm asallara bölüneceğinden, $n_K$ ile ikinci çarpan aralarında asal olamaz. Ancak $$\left(2^{q^K}\right)^{q-1}+\left(2^{q^K}\right)^{q-2}+\cdots+2^{q^K}+1\equiv 1+1+\cdots+1\equiv q\pmod{n_K}$$ olduğundan $$\text{EBOB}\left(n_K,\left(\left(2^{q^K}\right)^{q-1}+\left(2^{q^K}\right)^{q-2}+\cdots+2^{q^K}+1\right)\right)=1,q$$ olabilir. Aralarında asal olmadığından $\text{EBOB}=q$ olmalıdır. Ancak $q$'nun $n_K$'yı bölmediğini göstermiştik. Bu bir çelişkidir. $(n_k)$ dizisinin farklı asal bölenleri sonsuz tane olmalıdır. Bu da $qk+1$ formatında sonsuz asal sayı olduğunu kanıtlar.