Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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