DEÇEM 2019 Lise 13.Soru

[muuurat]

$\phi(n)|(n-1)$ olmak üzere $n$ aşağıdakilerden hangisine bölünebilir?
A) 16       B) 18        C) 25       D) 34        E) 72

[Metin Can Aydemir]

$p_1<p_2<\cdots< p_k$ olmak üzere $n=p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ şeklinde yazılsın. $$\phi(n)=(p_1^{\alpha_1}-p_1^{\alpha_1-1})\cdot (p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots (p_k^{\alpha_k}-p_k^{\alpha_k-1})$$ olacağından, eğer en az bir $i=1,2,\dots k$ için $\alpha_i>1$ ise $p_i|\phi(n)$ olur buradan $p_i|n-1$ olması gerektiği görülebilir, fakat $EBOB(n,n-1)=1$ olduğundan $p_i$ asalı $n-1$'i bölemez. Dolayısıyla $n$ sayısı kare bölensiz bir sayı olmalıdır. Dolayısıyla $16=2^4$, $18=2\cdot 3^2$, $25=5^2$ ve $72=2^3\cdot 3^2$ sayıları $n$'yi bölemez. DEÇEM'in cevap anahtarına da bakınca cevap $34$ olarak gözüküyor fakat bu da olamaz çünkü,

Eğer $n$ sayısı $34$'e bölünüyorsa çifttir. Dolayısıyla $n-1$ tek olacaktır. $\phi(n)$ ifadesinin tek bir sayıyı tam bölebilmesi için onun da tek olması gerekir. Fakat sayı aynı zamanda $17$ ile de bölüneceğinden $17-1=16$ sayısı $\phi(n)$ ifadesini böler, bu durumda $\phi(n)$ ifadesi çifttir ve $n-1$'i bölemez. Çelişki.

Dolayısıyla cevap $34$ olarak verilse de doğru cevap bu değildir.

[Lokman Gökçe]

Sorunun seçenekleri nasıl hazırlanmalıydı? Bu soruya cevap arayalım.

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. $n$ nin bölenleri istendiğinden seçeneklere $1$ veya $n=p$ asalı koyulmalıdı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>2$ 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<r $ 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. Daha kısa yolları da olabilir, yeni çözümlere açığız...

[Squidward]

Soru literatürde Lehmer's Totient Problem olarak geçiyor ve kendisi hala çözülememiş bir problem, tabii problem $n$ bileşik sayısını arıyor kaça bölündüğünü aramıyor.

[Lokman Gökçe]

Problem ile ilgili birkaç bilgiyi derleyerek ifade edelim.

[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.

[Metin Can Aydemir]

Ben de problemde ufak bir uğraş ile elde edilebilecek bir eşitsizlik paylaşmak isterim,

Önceki yorumlarda da bulduğumuz gibi $n$ kare-bölensiz ve tek bir sayı olmalıdır.  $\dfrac{n-1}{\phi(n)}$ tamsayı olmasını istiyoruz. Eğer $n=p_1\cdot p_2\cdots p_k$ ise ve $q_i$, $i.$ asal sayı olmak üzere, $$\dfrac{n-1}{\phi(n)}=\dfrac{p_1\cdot p_2\cdots p_k-1}{(p_1-1)\cdot (p_2-1)\cdots (p_k-1)}\leq \prod_{i=2}^{k}\dfrac{q_i}{q_i-1} \leq \dfrac{(2k+1)!-2^k\cdot k!}{(2^k\cdot k!)^2}$$ olur. $\dfrac{(2k+1)!-2^k\cdot k!}{(2^k\cdot k!)^2}$ ve $\displaystyle \prod_{i=2}^{k}\dfrac{q_i}{q_i-1}$ ifadeleri çok yavaş bir şekilde artan iki ifadedir fakat limitleri sonsuza gidiyor. Ayrıca $k=20$ gibi bir değer için bile $\displaystyle \prod_{i=2}^{k}\dfrac{q_i}{q_i-1}$ ifadesi yaklaşık $3.9$ olur yani $n$ sayısının $20$ farklı asal böleni varsa $\dfrac{n-1}{\phi(n)}$ ifadesi $1,2$ ve $3$ değerlerini alabilir. (ifadenin $1$ eşit olması için $n$'nin asal sayı olması gerekir. ) Bu değerleri inceleyerek Lokman hocamın belirttiği en az $14$ asal çarpanı olması gerektiği bilgisini $20$ veya daha fazla değerlere taşıyabiliriz.

Not: $k=100$ gibi çok daha büyük bir değer için bile $\dfrac{(2k+1)!-2^k\cdot k!}{(2^k\cdot k!)^2}$ ifadesi yaklaşık olarak $11,3$ sayısına eşit, yani yukarıdaki iki $k$'ya bağlı fonksiyon ifadeyi olabildiğince sınırlamakta.