Az A. 843. feladat (2023. január)

A. 843. Legyen \(\displaystyle N\) azon \(\displaystyle n\) pozitív egészek halmaza, melyekre tetszőleges \(\displaystyle k\) pozitív egész esetén teljesül, hogy ha \(\displaystyle n\mid k^k-1\), akkor \(\displaystyle n\mid k-1\). Bizonyítsuk be, hogy ha \(\displaystyle n_1, n_2\in N\), akkor a legnagyobb közös osztójuk is \(\displaystyle N\)-ben van.

(7 pont)

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

Ha \(\displaystyle n\notin N\), akkor van egy \(\displaystyle k\) szám, amelyre \(\displaystyle k^k \equiv 1 \pmod{n}\), de \(\displaystyle k \not \equiv 1 \pmod{n}\). Tehát \(\displaystyle 1 \neq o_{n} (k) \mid k, \varphi(n)\), így \(\displaystyle \varphi(n)\)-nek van közös prímosztója \(\displaystyle k\)-val. Másrészt \(\displaystyle k\) relatív prím \(\displaystyle n\)-hez. Ez azt jelenti, hogy \(\displaystyle \varphi(n)\)-nek van olyan prímosztója, ami nem osztja \(\displaystyle n\)-et.

A \(\displaystyle \varphi(n)\) prímdosztói vagy \(\displaystyle n\) prímosztói vagy \(\displaystyle q-1\) prímosztói, ahol \(\displaystyle q\) egy prímosztója \(\displaystyle n\)-nek. Tehát ha \(\displaystyle n\notin N\), akkor léteznek olyan prímek \(\displaystyle q|n\) és \(\displaystyle p|q-1\), amelyekre \(\displaystyle p\nmid n\).

Megfordítva, tegyük föl, hogy léteznek prímek \(\displaystyle q|n\) és \(\displaystyle p|q-1\), hogy \(\displaystyle p\nmid n\). Ekkor konstruálunk egy \(\displaystyle k\)-t, amelyre \(\displaystyle n|k^k-1\) de \(\displaystyle n\nmid k-1\), így bizonyítva, hogy \(\displaystyle n\notin N\).

Legyen \(\displaystyle e\) a \(\displaystyle q\) kitevője \(\displaystyle n\) prímfelbontásában. Ha \(\displaystyle k\) kongruens \(\displaystyle 1\) modulo minden \(\displaystyle n\)-t osztó prímhatványra, \(\displaystyle q^e\) kivételével, akkor a kínai maradéktétel szerint elég annyi, hogy \(\displaystyle k \not \equiv 1 \pmod{q^e}\) és \(\displaystyle k^k \equiv 1 \pmod{q^e}\).

Modulo \(\displaystyle q^e\) prímhatvány létezik egy primitív gyök \(\displaystyle g\). Legyen

\(\displaystyle k \equiv g^{\frac{q^{e-1}(q-1)}{p}} \pmod{q^e}.\)

és \(\displaystyle p|k\) legyen. Ez a kínai maradéktétel szerint lehetséges, mivel feltettük, hogy \(\displaystyle p\) nincs az \(\displaystyle n\) prímosztói között. Ezzel elértük, hogy \(\displaystyle k \not \equiv 1 \pmod{q^e}\) és \(\displaystyle k^k \equiv 1 \pmod{q^e}\) feltételek teljesülnek.

Együttvéve, azt kaptuk, hogy \(\displaystyle N\) azon \(\displaystyle n\) számok halmaza, amikre ha \(\displaystyle q, p\) prímekre \(\displaystyle q|n\) és \(\displaystyle p|q-1\) esetén \(\displaystyle p|n\) is igaz. A probléma állítása ezután már könnyen következik: ha \(\displaystyle n_1, n_2 \in N\) és \(\displaystyle n=\gcd(n_1, n_2)\), akkor minden \(\displaystyle q|n\) és \(\displaystyle p|q-1\) prímek esetén \(\displaystyle q\) osztja \(\displaystyle n_1\) és \(\displaystyle n_2\) számokat is, tehát \(\displaystyle n_1, n_2\in N\) miatt következik, hogy \(\displaystyle p|n_1\) és \(\displaystyle p|n_2\), így \(\displaystyle p|n\). Ez azt jelenti, hogy \(\displaystyle n\in N\).

—

A feladat Evan Chen egy, az Online Math Open-en kitűzött feladatának enyhén átdolgozott változata.

Statisztika:

11 dolgozat érkezett.
7 pontot kapott:	Bodor Mátyás, Diaconescu Tashi, Móricz Benjámin, Németh Márton, Szakács Ábel, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Sida Li.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2023. januári matematika feladatai