A B. 5436. feladat (2025. január)

B. 5436. Legyen \(\displaystyle p\) páratlan prím. Jelölje \(\displaystyle d_k(n)\) az \(\displaystyle n\) azon pozitív osztóinak számát, amelyek \(\displaystyle p\)-vel osztva \(\displaystyle k\) maradékot adnak (\(\displaystyle 0\leq k<p\)).

Legyen \(\displaystyle A\subseteq\{0,1,\dots,{p-1}\}=S\) olyan, hogy

\(\displaystyle \sum_{k\in A}d_k(n)\geq\sum_{j\in S\setminus A}d_j(n) \)

teljesül minden pozitív egész \(\displaystyle n\) számra. Legalább hány elemű az \(\displaystyle A\) halmaz?

Javasolta: Lovas Márton (Budakalász)

(6 pont)

A beküldési határidő 2025. február 10-én LEJÁRT.

Megoldás. Legyen \(\displaystyle f_A(n):=\sum\limits_{k\in A}d_k(n)\) és \(\displaystyle g_A(n):=\sum\limits_{j\in S\setminus A}d_j(n)\). Azt fogjuk igazolni, hogy ha \(\displaystyle f_A(n)\geq g_A(n)\) teljesül minden \(\displaystyle n\) pozitív egész számra, akkor \(\displaystyle |A|\geq \frac{p+1}{2}\) és létezik olyan \(\displaystyle \frac{p+1}{2}\) elemű halmaz, melyre az egyenlőtlenség mindig fennáll.

Mivel \(\displaystyle f_A(p^2)\geq g_A(p^2)\), ezért \(\displaystyle 0\in A\), különben \(\displaystyle g_A(p^2)\geq 2>1\geq f_A(p^2)\) lenne. Ismert, hogy minden \(\displaystyle p\) prímszám esetén létezik modulo \(\displaystyle p\) primitív gyök, vagyis olyan \(\displaystyle g\in S\), melyre az \(\displaystyle 1,g,g^2,\dots,g^{p-2}\) számok páronként különböző nemnulla maradékot adnak \(\displaystyle p\)-vel osztva. Dirichlet tétele szerint létezik olyan \(\displaystyle q\) prímszám, melyre \(\displaystyle q\equiv g\pmod{p}\). Ekkor \(\displaystyle f_A(q^{p-2})=|A\setminus\{0\}|\) és \(\displaystyle g_A(q^{p-2})=p-|A|\), ezért \(\displaystyle |A|-1\geq p-|A|\), ami a kívánt \(\displaystyle |A|\geq \frac{p+1}{2}\) korlátot adja.

Most mutatunk megfelelő \(\displaystyle A\) halmazt, melynek mérete \(\displaystyle \frac{p+1}{2}\): álljon \(\displaystyle A\) a kvadratikus maradékokból, vagyis azon \(\displaystyle t\in S\) elemekből, melyekre az \(\displaystyle x^2\equiv t\pmod {p}\) kongruencia megoldható. Speciálisan, \(\displaystyle 0\in A\), így ha \(\displaystyle p\mid n\), akkor az egyenlőtlenség teljesül, hiszen ha \(\displaystyle n\) prímtényezős felbontásában \(\displaystyle p\) kitevője \(\displaystyle \alpha\geq 1\), akkor osztóinak pontosan \(\displaystyle \frac{\alpha}{\alpha+1}\)-edrésze osztható \(\displaystyle p\)-vel (melyekben \(\displaystyle p\) kitevője nem 0, hanem az \(\displaystyle 1,2,\dots,\alpha\) számok valamelyike), és így \(\displaystyle \frac{f_A(n)}{g_A(n)}\geq \frac{\alpha}{1}\geq1\).

Végül tegyük fel, hogy \(\displaystyle p\nmid n\) és az \(\displaystyle n\) szám prímtényezős felbontása \(\displaystyle n=p_1^{\alpha_1}\dots p_r^{\alpha_r}\). Az \(\displaystyle n\) szám egyik osztója sem ad 0 maradékot \(\displaystyle p\)-vel osztva, azt szeretnénk belátni, hogy ezek legalább fele kvadratikus maradék. Ismert, hogy két kvadratikus maradék és két kvadratikus nemmaradék szorzata is mindig kvadratikus maradék, továbbá egy nemnulla kvadratikus maradék és egy kvadratikus nemmaradék szorzata kvadratikus nemmaradék. Az \(\displaystyle n\) szám osztói \(\displaystyle p_1^{\beta_1}\dots p_r^{\beta_r}\) alakúak, ahol minden \(\displaystyle i\)-re \(\displaystyle 0\leq \beta_i\leq \alpha_i\). A \(\displaystyle p_1,\dots,p_r\) prímosztókat szükség esetén átindexelve feltehető, hogy közülük a kvadratikus nemmaradékok \(\displaystyle p_1,\dots,p_s\). (Ha nincs köztük ilyen, akkor az összes osztó kvadratikus maradék, és készen vagyunk.) Az \(\displaystyle n\) szám minden osztója előáll úgy mint \(\displaystyle p_1^{\alpha_1}\dots p_s^{\alpha_s}\) és \(\displaystyle p_{s+1}^{\alpha_{s+1}}\dots p_r^{\alpha_r}\) egy-egy osztójának szorzata. Ez pontosan akkor kvadratikus maradék, ha \(\displaystyle p_1^{\alpha_1}\dots p_s^{\alpha_s}\) egy kvadratikus maradék osztóját választottuk, így elég belátni, hogy \(\displaystyle p_1^{\alpha_1}\dots p_s^{\alpha_s}\) osztóinak legalább fele kvadratikus maradék. Mivel \(\displaystyle p_1^{\beta_1}\dots p_s^{\beta_s}\) pontosan akkor kvadratikus maradék, ha \(\displaystyle \beta_1+\dots+\beta_s\) páros, ezért ez azzal egyenértékű, hogy

\(\displaystyle \prod\limits_{i=1}^s\sum\limits_{j=0}^{\beta_i}(-1)^j\geq 0.\)

Világos, hogy minden \(\displaystyle i\)-re \(\displaystyle \sum\limits_{j=0}^{\beta_i}(-1)^j\geq 0\), hiszen páros \(\displaystyle \beta_i\) esetén az összeg 0, páratlan \(\displaystyle \beta_i\) esetén 1, így ez valóban teljesül. Ezzel beláttuk, hogy a kvadratikus maradékok megfelelő halmazt alkotnak.

Statisztika:

22 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Bolla Donát Andor, Gyenes Károly, Holló Martin, Kovács Benedek Noel, Minh Hoang Tran, Molnár István Ádám, Prohászka Bulcsú, Szabó 721 Sámuel.
5 pontot kapott:	Hodossy Réka, Pázmándi József Áron, Sárdinecz Dóra, Vámosi Bendegúz Péter, Vigh 279 Zalán.
4 pontot kapott:	3 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2025. januári matematika feladatai