A B. 5461. feladat (2025. április)

B. 5461. Bizonyítsuk be, hogy bármely \(\displaystyle a\), \(\displaystyle b\), \(\displaystyle c\) és \(\displaystyle d\) pozitív egészekhez végtelen sok olyan pozitív egész \(\displaystyle n\) létezik, amelyre \(\displaystyle a^n+bc\) és \(\displaystyle b^{n+d}-1\) nem relatív prímek.

Javasolta: Kós Géza (Budapest) IMO2024/2 alapján

(6 pont)

A beküldési határidő 2025. május 12-én LEJÁRT.

Megoldás. Az a célunk, hogy igazoljuk végtelen sok olyan \(\displaystyle n\) pozitív egész szám létezését, melyhez található olyan \(\displaystyle p\) prímszám, amire \(\displaystyle p\mid a^n+bc\) és \(\displaystyle p\mid b^{n+d}-1\) egyaránt teljesül.

A kis Fermat-tétel szerint, ha egy \(\displaystyle p\) prímre \(\displaystyle p\nmid b\) és \(\displaystyle p-1\mid n+d\), akkor \(\displaystyle p\mid b^{n+d}-1\), vagyis a második oszthatóság fennáll.

Ha \(\displaystyle p\nmid a\), akkor a \(\displaystyle p\mid a^n+bc\) oszthatóság pontosan akkor teljesül, ha \(\displaystyle p\) osztja az \(\displaystyle (a^n+bc)a^d=a^{n+d}+a^dbc\) számot. A kis Fermat-tétel alapján, ha \(\displaystyle p-1\mid n+d\), akkor \(\displaystyle p\mid a^{n+d}-1\), így ez pontosan akkor teljesül, ha \(\displaystyle p\mid a^dbc+1\).

Tehát, ha \(\displaystyle p\nmid ab\), \(\displaystyle p\mid a^dbc+1\) és \(\displaystyle p-1\mid n+d\), akkor \(\displaystyle p\) osztja az \(\displaystyle a^n+bc\) és \(\displaystyle b^{n+d}-1\) számokat, vagyis azok nem relatív prímek.

Mivel \(\displaystyle a\), \(\displaystyle b\), \(\displaystyle c\), \(\displaystyle d\) pozitív egész számok, ezért \(\displaystyle 1<a^dbc+1\) egész számnak létezik \(\displaystyle p\) prímosztója. Világos, hogy \(\displaystyle p\nmid ab\). Ha az \(\displaystyle n\) számot \(\displaystyle n=(p-1)k-d\) alakúnak választjuk, akkor \(\displaystyle p-1\mid n+d\) is teljesül, és \(\displaystyle n\) pozitív egész szám lesz, ha a \(\displaystyle k\) pozitív egész számra \(\displaystyle k>d/(p-1)\).

Ezzel igazoltuk, hogy végtelen sok \(\displaystyle n\) pozitív egész számra teljesül az előírt feltétel.

Statisztika:

13 dolgozat érkezett.
6 pontot kapott:	Aravin Peter, Bencze Mátyás, Bodor Ádám, Pázmándi József Áron, Péter Hanna, Rajtik Sándor Barnabás, Sajter Klaus, Sha Jingyuan, Wágner Márton.
0 pontot kapott:	3 versenyző.

A KöMaL 2025. áprilisi matematika feladatai