Problem B. 5461. (April 2025)

B. 5461. Prove that for any positive integers \(\displaystyle a\), \(\displaystyle b\), \(\displaystyle c\) and \(\displaystyle d\) there exists infinitely many positive integers \(\displaystyle n\) for which \(\displaystyle a^n+bc\) and \(\displaystyle b^{n+d}-1\) are not relatively primes.

Proposed by: Géza Kós, Budapest, based on IMO2024/2

(6 pont)

Deadline expired on May 12, 2025.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

13 students sent a solution.
6 points:	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 point:	3 students.

Problems in Mathematics of KöMaL, April 2025