Soru: $n$ bir pozitif tam sayı ve $\phi(n)$ Euler fonksiyonu olmak üzere $\phi(n)|n-1$ koşulunu sağlayan tüm $n$ sayılarını belirleyiniz.
Çözüm İçin Uğraşı: $n$ sayısının bir asal sayının karesine bölünemeyeceğini biliyoruz. Eğer bir $p$ asalı için $p^2|n$ olsaydı $\phi(n)$ ifadesi de $p$ çarpanı içerirdi. $p|\phi(n)$ ve $\phi(n)|n-1$ olduğundan $p|n-1$ olur. Halbuki iki ardışık tamsayı aralarında asal olduğundan $\text{obeb}(n,n-1)=1$ dir. Her ikisi birden $p$ ile bölünemez, çelişki.
Demek ki $n$ nin asal çarpanlarının kuvveti $1$ olmak zorundadır. $n=prq$ ..vb biçiminde.
Açıkça $n=p$ biçiminde bir asal sayı iken $\phi (n)=p-1 $ olduğundan $\phi(n)| n-1 $ koşulu sağlanır. Tüm asal $n$ değerleri çözümdür.
$p>2$ asal sayı iken $n=2p$ biçiminde olabilir mi? Araştıralım: $\phi(n)=\phi(2p)=p-1 $ dir. Bu halde $\phi(n)| n-1 $ olması için $\dfrac{2p-1}{p-1}$ tamsayı olmalıdır. $\dfrac{2p-1}{p-1}= 2 + \dfrac{1}{p-1}$ olup $p-1=1$ ve $p=2$ dir. Bu ise $p>3$ koşuluna uymaz. Çözüm yoktur.
Şimdi $2<p<q$ asal sayıları için $n=pq$ biçiminde olabilir mi? Araştıralım: $\phi(n)=\phi(pq)=(p-1)(q-1) $ dir. $\phi(n)| n-1 $ olması için $\dfrac{pq-1}{(p-1)(q-1)}$ tamsayı olmalıdır. $p-1=x$, $q-1=y$ değişken değiştirmesi yapılırsa $x \geq 2$, $y \geq 4$ olmak üzere $f(x,y)= \dfrac{(x+1)(y+1)-1}{xy}= \dfrac{xy+x+y}{xy}= 1 + \dfrac{1}{x}+\dfrac{1}{y}>1$ ifadesi tamsayı olmalıdır. Yani en az $2$ ye eşit olmalıdır. Öte taraftan $\dfrac{1}{x}+\dfrac{1}{y} \leq \dfrac{1}{2}+\dfrac{1}{4}= \dfrac{3}{4}$ olduğundan $1< f(x,y) \leq \dfrac{7}{4}$ olur. Tamsayı çözüm yoktur.
Şimdi de $2<p<q<q $ asal sayıları için $n=pqr$ biçiminde olabilir mi? Araştıralım: $\phi(n)=\phi(pqr)=(p-1)(q-1)(r-1) $ dir. $\phi(n)| n-1 $ olması için $\dfrac{pqr-1}{(p-1)(q-1)(r-1)}$ tamsayı olmalıdır. $p-1=x$, $q-1=y$, $r-1=z$ değişken değiştirmesi yapılırsa $x \geq 2$, $y \geq 4$, $z\geq 6$ olmak üzere $f(x,y,z)= \dfrac{(x+1)(y+1)(z+1)-1}{xyz}= \dfrac{xyz+xy+yz+zx + x+y+z }{xyz}= 1 +\dfrac{1}{xy}+\dfrac{1}{yz}+ \dfrac{1}{xz}+ \dfrac{1}{x}+\dfrac{1}{y}+ \dfrac{1}{z}>1$ ifadesi tamsayı olmalıdır. Öte taraftan $\dfrac{1}{xy}+\dfrac{1}{yz}+ \dfrac{1}{xz}+ \dfrac{1}{x}+\dfrac{1}{y}+ \dfrac{1}{z} \leq \dfrac{34}{24}$ tür. Yani yalnızca $1$'e eşit olabilir.
Burada $x=2$ için $\dfrac{xy+yz+zx + x+y+z }{xyz}=1$ denklemini çözelim. $3y+3z+2=yz$ olup $z=\dfrac{3y+2}{y-3}$ denkleminden $y=4$, $z=14$ gelir. $p=3$, $q=5$ asaldır fakat $r=15$ asal değildir, çözüm yoktur.
$f(x,y,z)$ ifadesinde $x\neq 2$ ise bu durumda $x\geq 4$, $y\geq 6$, $z\geq 10$ olup $1< f(x,y,z) < 2 $ elde edilir. Yani bu durumda da çözüm yoktur.
İncelemediğim durumları da yazarak yazıyı tamamlıyorum: $n=2pq$ gibi $2$ asal çarpanını içeren diğer türler ve $n=pqrs$ gibi dört veya daha fazla tek asal çarpan içeren türler. Bunlar da incelenirse başka $n$ çözümleri olup olmadığı anlaşılabilir. Bu durumlar da yukarıda yaptığımız gibi benzer işlemlerle gösterilebilir sanıyorum. (Henüz denemedim.) Daha kısa yolları da olabilir, yeni çözümlere açığız...
Birkaç Bilgi Daha:
[1] $n$ değeri $2$ asal çarpanını da içeremez. Çünkü bu halde $n-1$ tek sayı olur. Öte taraftan $n>2$ için $\phi(n)$ çift sayı olduğundan $\phi(n) | n-1 $ durumu ile çelişir. Yani $n$ tek sayıdır. $n=pqrs$ gibi dört veya daha fazla farklı asal çarpan durumlarını incelememiz gerekiyor.
[2] Böyle bir $n$ bileşik sayısı olup olmadığı bilinmiyor. Ancak varsa, bir Carmichael sayısı olması gerekmektedir.
[3] Araştırmalara göre, böyle bir $n$ bileşik sayısı varsa en az $14$ farklı asal sayının çarpımından oluşması gerektiği gösterilmiştir. Bazı özel durumlar ile ilgili http://mathworld.wolfram.com/LehmersTotientProblem.html bağlantısında çeşitli bilgiler verilmiştir.