Feladat:	2025. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bodor Mátyás, Csíkszereda
Füzet:	2025/október, 406 - 408. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Különleges függvények, Oszthatóság, Matematika
Hivatkozás(ok):	Feladatok: 2025/szeptember: 2025. évi Nemzetközi Matematika Diákolimpia 13. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. (Bodor Mátyás) Megmutatjuk, hogy $c$ legkisebb lehetséges értéke a $4$. Bármely $p$ prímszámra és nemnulla $x$ egészre jelöljük $v_p\left(x\right)$-szel az $x$ prímtényezős felbontásában a $p$ kitevőjét. A megoldás során többször is használni fogjuk a Lifting The Exponent (LTE) lemmát: * Ha $p$ páratlan prímszám és $x\mathrm{,}y$ egészek úgy, hogy $p\nmid x\mathrm{,}y$ és $p\mid x-y$, akkor tetszőleges $n$ pozitív egészre $\begin{array}{c}{\displaystyle v_p\left(x^n-y^n\right)=v_p\left(x-y\right)+v_p\left(n\right)\mathrm{.}}\end{array}$ * $p=2$-re: ha $x\mathrm{,}y$ páratlanok és $n$ páros, akkor $\begin{array}{c}{\displaystyle v_2\left(x^n-y^n\right)=v_2\left(x-y\right)+v_2\left(x+y\right)+v_2\left(n\right)-1.}\end{array}$ (Bővebben lásd például a https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma oldalt.) Nekünk csak a $p=2$ az esetre lesz szükségünk.   Először megmutatjuk, hogy $c\ge 4$. Ehhez tekintsük a következő függvényt: $\begin{array}{c}{\displaystyle g\left(x\right)=\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle \mathrm{1,}}& {\displaystyle \text{ha }x\text{ páratlan}\mathrm{,}}\hfill \\ \hfill {\displaystyle \mathrm{2,}}& {\displaystyle \text{ha }x=\mathrm{2,}}\hfill \\ \hfill {\displaystyle 2^{v_2\left(x\right)+2}\mathrm{,}}& {\displaystyle \text{ha }x\text{ páros és }x>2.}\hfill \end{array}}}\end{array}$ A $g$ függvény pöpec, mert: * Ha $a$ páratlan, akkor $g\left(a\right)=1\mid b^a-g\left(b\right)$. * Ha $a=2$, akkor az kell, hogy $g\left(a\right)=2\mid b^2-g{\left(b\right)}^2$, ami igaz, mert a konstrukcióból látható, hogy $b$ és $g\left(b\right)$ paritása mindig megegyezik. * Ha $a$ páros, $a\ge 4$ és $b$ páros, akkor az kell, hogy $g\left(a\right)=2^{v_2\left(a\right)+2}\mid b^a-g{\left(b\right)}^{2^{v_2\left(a\right)+2}}$. Mivel $2\mid g\left(b\right)$ páros, $v_2\left(g{\left(b\right)}^{2^{v_2\left(a\right)+2}}\right)\ge 2^{v_2\left(a\right)+2}>v_2\left(a\right)+2$, ezért $2^{v_2\left(a\right)+2}\mid g{\left(b\right)}^{2^{v_2\left(a\right)+2}}$; másrészt $2\mid b$ miatt $v_2\left(b^a\right)\ge a\ge v_2\left(a\right)+2$ (például a $2$, $3$, $\text{...}$, $a$ számok között legfeljebb $a-2$ darab $2$-hatvány lehet, mert a $3$ nem $2$-hatvány, ezért $v_2\left(a\right)\le a-2$). Vagyis $2^{v_2\left(a\right)+2}\mid b^a$, ahonnan következik a kívánt oszthatóság. * Végül, ha $a$ páros, $a\ge 4$ és $b$ páratlan, akkor a feltétel $g\left(a\right)=2^{v_2\left(a\right)+2}\mid b^a-1$, ez pedig következik az LTE lemmából: $v_2\left(b^a-1\right)=v_2\left(b+1\right)+v_2\left(b-1\right)+v_2\left(a\right)-1\ge v_2\left(a\right)+2$, hiszen $b+1$ és $b-1$ mindegyike páros, és pontosan az egyik osztható $4$-gyel is, tehát 2-es kitevője legalább $2$. Összegezve, a $g$ függvény valóban pöpec. Emellett $g\left(4\right)=2^{2+2}=16$, így $4c\ge g\left(4\right)=16$, tehát biztosan $c\ge 4$.   Most pedig megmutatjuk, hogy $c=4$ eleget tesz a feltételeknek. Tekintsünk egy tetszőleges pöpec $f$ függvényt. Belátjuk, hogy minden pozitív egész $n$-re $f\left(n\right)\le 4n$, innen készen leszünk. Tetszőleges $a\mathrm{,}b$ pozitív egészre legyen $P\left(a\mathrm{,}b\right)$ az oszthatósági feltétel, tehát $P\left(a\mathrm{,}b\right)$ annak a rövidítése, hogy $f\left(a\right)\mid b^a-f{\left(b\right)}^{f\left(a\right)}$. A $P\left(a\mathrm{,}a\right)$ szerint $f\left(a\right)\mid a^a-f{\left(a\right)}^{f\left(a\right)}$, ezért $f\left(a\right)\mid a^a$. Ha most $a=p$ prímszám, akkor $f\left(p\right)\mid p^p$. Ezért $f\left(p\right)$ értéke vagy $1$, vagy pedig $p$-hatvány minden $p$ prímre. Legyen $f\left(p\right)=p^{i_p}$, ahol $i_p\ge 0$ egész. Tegyük fel, hogy van végtelen sok olyan $p$ prím, hogy $i_p>0$. Legyen emellett $b$ tetszőleges pozitív egész. Válasszunk egy olyan nagy $p$ prímet, hogy $i_p>0$ és $p>|b-f\left(b\right)|$; ilyen van a feltevésünk miatt. Így $P\left(p\mathrm{,}b\right)$$$-$$ből $p\mid p^{i_p}=f\left(p\right)\mid b^p-f{\left(b\right)}^{f\left(p\right)}$. De mind $p$, mind $f\left(p\right)$ egy $p$-hatvány, ezért a kis Fermat-tételből $b^p\equiv b\left(\text{mod}p\right)$ és $f{\left(b\right)}^{f\left(p\right)}\equiv f\left(b\right)\left(\text{mod}p\right)$. A fentiek alapján $p\mid b-f\left(b\right)$ és $p>|b-f\left(b\right)|$, ami csak úgy lehetséges, ha $b-f\left(b\right)=0$, vagyis $f\left(b\right)=b$. De $b$ tetszőlegesen volt megválasztva, tehát $f\left(b\right)=b\le 4b$ minden $b$-re.   Marad az az eset, amikor nincs végtelen sok olyan $p$ prím, hogy $i_p>0$, vagyis véges sok van, legyenek ezek $p_1<p_2<\text{...}<p_k$, és ekkor minden $p>p_k$ prímszámra $f\left(p\right)=1$. Ha egyáltalán nincsenek ilyen $p_1<\text{...}<p_k$ prímek, akkor $f\left(p\right)=1$, minden $p$ prímre. Ha van olyan $a$, amelyre $f\left(a\right)>1$, akkor legyen $p$ az $f\left(a\right)$ egyik prímosztója. $P\left(a\mathrm{,}p\right)$-ből $p\mid f\left(a\right)\mid p^a-1^{f\left(a\right)}=p^a-1$ miatt $p\mid 1$, ellentmondás. Tehát ilyen $a$ nem létezhet; $f\left(n\right)=1\le 4n$ minden $n$-re. Ha $k\ge 1$, és $p_k>2$, akkor válasszunk egy $p>p_k$ prímet a $p\equiv 2\left(\text{mod}{p}_k\right)$ tulajdonsággal; ezt meg tudjuk tenni a Dirichlet-tétel miatt, hiszen $p_k$ és a $2$ relatív prímek. De $P\left(p_k\mathrm{,}p\right)$ miatt $p_k\mid f\left(p_k\right)\mid p^{p_k}-f{\left(p\right)}^{p_k}=p^{p_k}-1$, de $p^{p_k}-1\equiv p-1\equiv 1\left(\text{mod}{p}_k\right)$ a kis Fermat-tételből, ami ellentmondás. Az az eset marad, amikor $k=\mathrm{1,}f\left(2\right)$ páros, és $f\left(p\right)=1$ minden $p>2$ prímre. Ha van olyan $a$, hogy $p\mid f\left(a\right)$ valamilyen páratlan $p$ prímre, akkor $P\left(a\mathrm{,}p\right)$ miatt $p\mid f\left(a\right)\mid p^a-1^{f\left(a\right)}=p^a-1$, ellentmondás. Ez azzal egyenértékű, hogy $f\left(a\right)$ minden $a$-ra vagy $1$, vagy pedig $2$-hatvány. A $P\left(a\mathrm{,3}\right)$-ból $f\left(a\right)\mid 3^a-f{\left(3\right)}^{f\left(a\right)}=3^a-1$, így páratlan $a$-ra $4\nmid 3^a-1$ miatt $f\left(a\right)\le 2<4a$. Ha pedig $a$ páros, akkor az LTE lemmából $v_2\left(3^a-1\right)=v_2\left(3-1\right)+v_2\left(3+1\right)+v_2\left(a\right)-1=v_2\left(a\right)+2$, ezért $v_2\left(a\right)+2\ge v_2\left(f\left(a\right)\right)=\text{log}{}_{2}f\left(a\right)$, ezért $f\left(a\right)\le 2^{v_2\left(a\right)+2}=4\cdot 2^{v_2\left(a\right)}\le 4a$. Tehát az $f\left(n\right)\le 4n$ egyenlőtlenség minden $n\in \text{N}$ számra fennáll, és ez igazolja, hogy $c=4$ megfelelő.