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