Problem B. 5517. (February 2026)

B. 5517. For which prime numbers \(\displaystyle p\) does there exist a permutation \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle \dots\), \(\displaystyle a_{p-1}\) of numbers 1, 2, \(\displaystyle \ldots\), \(\displaystyle p-1\) such that numbers \(\displaystyle a_1^1\), \(\displaystyle a_2^2\), \(\displaystyle \ldots\), \(\displaystyle a_{p-1}^{p-1}\) have pairwise different remainders modulo \(\displaystyle p\)?

(Proposed by Péter Pál Pach, Budapest

(6 pont)

Deadline expired on March 10, 2026.

Sorry, the solution is available only in Hungarian. Google translation

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).\)

Statistics:

20 students sent a solution.
6 points:	Ali Richárd, Bao Nguyen Gia, Bodor Ádám, Diaconescu Tashi, Ercse Ferenc, Li Mingdao, Rajtik Sándor Barnabás, Sajter Klaus	(8 students).
2 points:	1 student.
1 point:	4 students.
0 points:	7 students.

Problems in Mathematics of KöMaL, February 2026