A B. 5517. feladat (2026. február)

B. 5517. Mely \(\displaystyle p\) prímszámok esetén létezik az \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle \ldots\), \(\displaystyle p-1\) számoknak olyan \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle \ldots\), \(\displaystyle a_{p-1}\) permutációja, amelyre \(\displaystyle a_1^1\), \(\displaystyle a_2^2\), \(\displaystyle \ldots\), \(\displaystyle a_{p-1}^{p-1}\) páronként különböző maradékot adnak \(\displaystyle p\)-vel osztva?

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

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

Megoldás. Felhasználjuk azt az ismert állítást, hogy tetszőleges \(\displaystyle p\) prímszám esetén létezik primitív gyök modulo \(\displaystyle p\), azaz olyan \(\displaystyle g\) egész szám, amelyre az

\(\displaystyle 1, g, g^2, g^3, \ldots, g^{p-2} \)

számok csupa különböző maradékot adnak \(\displaystyle p\)-vel osztva.

Legyen \(\displaystyle g\) egy primitív gyök mod \(\displaystyle p\). Továbbá legyen \(\displaystyle b_n\) az az \(\displaystyle 1\) és \(\displaystyle p-1\) közti szám, melyre \(\displaystyle g^{b_n} \equiv a_n\) mod \(\displaystyle p\). Ekkor \(\displaystyle a_n^n \equiv g^{n \cdot b_n}\) minden \(\displaystyle n\)-re \(\displaystyle 1\) és \(\displaystyle p-1\) között. Egy primitív gyök két hatványa akkor és csak akkor kongruens, ha a kitevők kongruensek mod \(\displaystyle p-1\). Tehát a feladat ekvivalens azzal, hogy létezik-e az \(\displaystyle 1,2,\ldots,p-1\) számoknak olyan \(\displaystyle b_1, b_2, \ldots, b_{p-1}\) permutációja, hogy az \(\displaystyle 1 \cdot b_1,2 \cdot b_2,\ldots,(p-2) \cdot b_{p-1}\) számok mind különböző maradékot adnak mod \(\displaystyle p-1\), azaz teljes maradékrendszert alkotnak.

Tegyük fel, hogy létezik egy ilyen \(\displaystyle b_1,b_2,\ldots,b_{p-1}\) permutáció.

Legyen \(\displaystyle q\) egy egész szám, amely osztja \(\displaystyle (p-1)\)-et. Először belátjuk a következő lemmát:

Lemma: \(\displaystyle q \mid n \Leftrightarrow q \mid b_n\).

Bizonyítás: Ha van olyan \(\displaystyle n\), amelyre \(\displaystyle q \mid n\), de \(\displaystyle q \nmid b_n\), akkor van egy \(\displaystyle k\) is, amelyre \(\displaystyle q \nmid k\) de \(\displaystyle q \mid b_k\). Ekkor több, mint \(\displaystyle \frac{p-1}{q}\) darab \(\displaystyle q\)-val osztható \(\displaystyle n \cdot b_n\) lesz: ha \(\displaystyle q \mid n\), akkor \(\displaystyle q \mid n \cdot b_n\) (ez \(\displaystyle \frac{p-1}{q}\) darab), és \(\displaystyle q \mid k \cdot b_k\). Ekkor viszont nem alkothatnának az \(\displaystyle n \cdot b_n\) alakú számok teljes maradékrendszert, mivel túl sok \(\displaystyle q\)-val osztható szám lenne köztük. Tehát ha \(\displaystyle q \mid n\), akkor \(\displaystyle q \mid b_n\), és mivel a \(\displaystyle b_n\)-ek az \(\displaystyle 1,2,\dots,p-1\) számok egy permutációját alkotják, ezért ugyanannyi \(\displaystyle q\)-val osztható van köztük, mint az \(\displaystyle 1,2,\dots,p-1\) számok közt, tehát \(\displaystyle q \mid n \Leftrightarrow q \mid b_n\). Ezzel a lemmát bizonyítottuk.

Most belátjuk, hogy \(\displaystyle (p-1)\) négyzetmentes. Tegyük fel, hogy \(\displaystyle q^2 \mid p-1\) és \(\displaystyle q\) prím. Ekkor ha \(\displaystyle q\) osztja \(\displaystyle n \cdot b_n\)-et, akkor osztja \(\displaystyle n\) és \(\displaystyle b_n\) közül az egyiket, tehát a lemma miatt mindkettőt osztja, azaz \(\displaystyle q^2 \mid n \cdot b_n\). Ekkor viszont nem lesz olyan \(\displaystyle n\), amelyre \(\displaystyle q \equiv n \cdot b_n\), tehát ellentmondásra jutottunk.

Most is legyen \(\displaystyle q\) egy prím, ami osztja \(\displaystyle (p-1)\)-et, és legyen \(\displaystyle p-1=qd\). Mivel \(\displaystyle p-1\) négyzetmentes, ezért \(\displaystyle (q,d)=1\). A lemma szerint a \(\displaystyle d, 2d,\dots, qd\) számoknak egy permutációja a \(\displaystyle b_d,b_{2d},\dots, b_{qd}\) számok, és a szorzataikon kívül nincs más \(\displaystyle d\)-vel osztható szám, tehát meg kell kapnunk belőlük az összes \(\displaystyle d\)-vel osztható maradékot mod \(\displaystyle p-1\). Tehát mivel \(\displaystyle (q,d)=1\), ezért a \(\displaystyle d, 2d,\dots, qd\) alakú számok teljes maradékrendszert alkotnak mod \(\displaystyle q\). Tehát a \(\displaystyle 0,1, \dots, q-1\) számokat összepárosítva egy permutációjukkal, a szorzatok teljes maradékrendszert alkotnak. A \(\displaystyle 0\)-nak \(\displaystyle 0\) a párja (mivel \(\displaystyle q\) prím), tehát a nemnulla maradékokat egy permutációjukkal párosítva a szorzatok pontosan a nemnulla maradékokat adják, mindegyiket egyszer. Ha nézzük a nemnulla tagok szorzatát, akkor:

\(\displaystyle (q-1)! \cdot (q-1)! \equiv (q-1)! \Rightarrow 1 \equiv (q-1)! \equiv -1 \text{ (mod } q) \)

a Wilson-tétel miatt és mivel \(\displaystyle (q,(q-1)!)=1\).

Tehát \(\displaystyle q \mid 2 \Rightarrow q=2\) az egyetlen prímosztója \(\displaystyle (p-1)\)-nek, és \(\displaystyle 4 \nmid (p-1)\) mivel \(\displaystyle (p-1)\) négyzetmentes. Tehát \(\displaystyle p=3\) az egyetlen jó prím, és erre létezik is jó permutáció:

\(\displaystyle a_1=2, a_2=1 \Rightarrow a_1^1 \equiv 2 \not\equiv 1 \equiv a_2^2 \text{ (mod }3).\)

Statisztika:

20 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Bao Nguyen Gia, Bodor Ádám, Diaconescu Tashi, Ercse Ferenc, Li Mingdao, Rajtik Sándor Barnabás, Sajter Klaus.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2026. februári matematika feladatai