Az A. 635. feladat (2015. február)

A. 635. Mutassuk meg, hogy minden \(\displaystyle c>0\) valós számhoz létezik olyan \(\displaystyle n\) pozitív egész, amire \(\displaystyle \varphi\big(\sigma(n)\big)>cn\). (Tetszőleges \(\displaystyle k\) pozitív egészre \(\displaystyle \varphi(k)\) a \(\displaystyle k\)-nál nem nagyobb, \(\displaystyle k\)-hoz relatív prím pozitív egészek számát, \(\displaystyle \sigma(k)\) pedig a \(\displaystyle k\) pozitív osztóinak összegét jelöli.)

Javasolta: Szabó Barnabás (Budapest)

(5 pont)

A beküldési határidő 2015. március 10-én LEJÁRT.

Megoldás. Olyan \(\displaystyle n\) számokat fogunk konstruálni, amiknek sok kicsi prímosztója van, -- ezzel érjük el, hogy \(\displaystyle \frac{\sigma(n)}{n}\) nagy legyen --, továbbá azt is biztosítjuk, hogy \(\displaystyle \sigma(n)\)-nek viszont ne legyenek kicsi prímosztói -- ezzel biztosítjuk, hogy \(\displaystyle \varphi(\sigma(n))\) ne lehessen sokkal kisebb, mint \(\displaystyle \sigma(n)\).

Azt, hogy \(\displaystyle \sigma(n)\)-nek ne legyen kis prímosztója, a következő jól ismert tétel alkalmazásával érjük el: ha \(\displaystyle q\) páratlan prím és \(\displaystyle a\) egész szám, akkor \(\displaystyle 1+a+a^2+\ldots+a^{q-1}\) minden prímosztója \(\displaystyle q\) vagy \(\displaystyle 2kq+1\) alakú. (Ld. pl. itt.) Ebből most csak arra lesz szükségünk, hogy az \(\displaystyle 1+a+a^2+\ldots+a^{q-1}\) alakú számoknak nincs \(\displaystyle q\)-nál kisebb prímosztója.

Fel fogjuk használni azt az elemi tényt is, hogy bármely \(\displaystyle x\ge 2\) számra, az \(\displaystyle x\)-nél nem nagyobb prímszámok szorzata kisebb, mint \(\displaystyle 4^x\). (Lásd pl itt.)

A konstrukció. Vegyünk egy nagy pozitív egész \(\displaystyle N\) számot, és legyen \(\displaystyle A\) az \(\displaystyle N\)-nél nem nagyobb prímszámok szorzata: \(\displaystyle A = \prod_{p\le N} p\). Az idézett becslés szerint \(\displaystyle A<4^N\). Legyen \(\displaystyle Q\) nagy páratlan prím. (Az \(\displaystyle N\) és a \(\displaystyle Q\) értékét az utolsó lépésben fogjuk pontosan definiálni.) Végül legyen \(\displaystyle n=A^{Q-1}\). Ekkor tehát \(\displaystyle n < 4^{N(Q-1)}\), vagy logaritmálva \(\displaystyle \ln n < \ln4 \cdot N(Q-1)\).

A \(\displaystyle \sigma(n)/n\) becslése. Ha \(\displaystyle Q\)-t \(\displaystyle (\log_2N)\)-nél nagyobbnak választjuk, akkor az \(\displaystyle n\) számnak az \(\displaystyle 1,2,3,\dots,N\) mind osztója lesz, mert az \(\displaystyle N\)-nél nem nagyobb prímek mind szerepelnek az \(\displaystyle n\) definíciójában, elegendően magas kitevőn. Így a \(\displaystyle \frac{n}{1}\), \(\displaystyle \frac{n}{2}\), ..., \(\displaystyle \frac{n}{N}\) számok is mind osztói \(\displaystyle n\)-nek, és

A \(\displaystyle \sigma(n)\) prímtényezős felbontása. Az \(\displaystyle n\) prímtényezős alakjából felírhatjuk \(\displaystyle \sigma(n)\)-et:

\(\displaystyle \sigma(n) = \sigma\left(\prod_{p\le N} p^{Q-1}\right) = \prod_{p\le N} (1+p+p^2+\dots+p^{Q-1}). \)

Tudjuk, hogy ennek nem lehet \(\displaystyle Q\)-nál kisebb prímosztója.

Legyen \(\displaystyle \sigma(n)\) prímtényezős felbontása \(\displaystyle \sigma(n) = r_1^{\alpha_1} r_2^{\alpha_2} \ldots r_m^{\alpha_m}\); ekkor tehát \(\displaystyle r_1,\ldots,r_m\ge Q\). Az \(\displaystyle m\)-re a következő becslést kaphatjuk:

\(\displaystyle Q^m \le r_1r_2\ldots r_m \le \sigma(n) < n^2 < (4^{N(Q-1)})^2 = 16^{N(Q-1)}, \)

\(\displaystyle m < (\ln 16) \frac{N(Q-1)}{\ln Q}. \)

A \(\displaystyle \varphi(\sigma(n))/\sigma(n)\) becslése.

Beírva a \(\displaystyle \varphi(\sigma(n))\) szokásos előállítását,

\(\displaystyle \varphi(\sigma(n)) = \varphi( r_1^{\alpha_1} \ldots r_m^{\alpha_m} ) = \prod_{i=1}^m r_i^{\alpha_i-1} (r_i-1) = \sigma(n) \prod_{i=1}^m \left(1-\frac1{r_i}\right). \)

Az \(\displaystyle e^x\ge 1+x\) egyenlőtlenség alapján, minden egyes \(\displaystyle r_i\) prímre

\(\displaystyle 1-\frac1{r_i} \ge 1-\frac1Q = \left(1+\frac1{Q-1}\right)^{-1} \ge e^{-\frac1{Q-1}}. \)

Ezért

Az \(\displaystyle N\) és a \(\displaystyle Q\) megválasztása. Az (1) és (2) becsléseket kombinálva,

\(\displaystyle \frac{\varphi(\sigma(n))}{n} = \frac{\varphi(\sigma(n))}{\varphi(n)} \cdot \frac{\varphi(n)}{n} > \left(\frac1{16}\right)^{\frac{N}{\ln Q}} \cdot \ln N. \)

Válasszunk olyan \(\displaystyle N\)-et, amire \(\displaystyle N>e^{16c}\), utána pedig válasszunk olyan \(\displaystyle Q\) prímet, amire \(\displaystyle Q>e^N\) (erre persze a korábban felhasznált \(\displaystyle Q\ge\log_2N\) feltétel is teljesül). Ilyen választással

\(\displaystyle \frac{\varphi(\sigma(n))}{n} > \left(\frac1{16}\right)^{\frac{N}{\ln Q}} \cdot \ln N > \frac1{16} \cdot 16c = c. \)

Statisztika:

4 dolgozat érkezett.
5 pontot kapott:	Fehér Zsombor, Janzer Barnabás, Szabó 789 Barnabás, Williams Kada.

A KöMaL 2015. februári matematika feladatai