Soru: n bir pozitif tam sayı ve ϕ(n) Euler fonksiyonu olmak üzere ϕ(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 p2|n olsaydı ϕ(n) ifadesi de p çarpanı içerirdi. p|ϕ(n) ve ϕ(n)|n−1 olduğundan p|n−1 olur. Halbuki iki ardışık tamsayı aralarında asal olduğundan 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 ϕ(n)=p−1 olduğundan ϕ(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: ϕ(n)=ϕ(2p)=p−1 dir. Bu halde ϕ(n)|n−1 olması için 2p−1p−1 tamsayı olmalıdır. 2p−1p−1=2+1p−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: ϕ(n)=ϕ(pq)=(p−1)(q−1) dir. ϕ(n)|n−1 olması için 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≥2, y≥4 olmak üzere f(x,y)=(x+1)(y+1)−1xy=xy+x+yxy=1+1x+1y>1 ifadesi tamsayı olmalıdır. Yani en az 2 ye eşit olmalıdır. Öte taraftan 1x+1y≤12+14=34 olduğundan 1<f(x,y)≤74 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: ϕ(n)=ϕ(pqr)=(p−1)(q−1)(r−1) dir. ϕ(n)|n−1 olması için 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≥2, y≥4, z≥6 olmak üzere f(x,y,z)=(x+1)(y+1)(z+1)−1xyz=xyz+xy+yz+zx+x+y+zxyz=1+1xy+1yz+1xz+1x+1y+1z>1 ifadesi tamsayı olmalıdır. Öte taraftan 1xy+1yz+1xz+1x+1y+1z≤3424 tür. Yani yalnızca 1'e eşit olabilir.
Burada x=2 için xy+yz+zx+x+y+zxyz=1 denklemini çözelim. 3y+3z+2=yz olup z=3y+2y−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≠2 ise bu durumda x≥4, y≥6, z≥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 ϕ(n) çift sayı olduğundan ϕ(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.