Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4187. (May 2009)

B. 4187. Let a, k and n be positive integers. Find the greatest common divisor of the numbers an+1 and ak+1.

(5 pont)

Deadline expired on June 15, 2009.


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

Megoldás. A megoldás során felhasználjuk az

\(\displaystyle x^m-1=(x-1)(x^{m-1}+x^{m-2}+\ldots+x+1)\)

és az

\(\displaystyle x^{2m+1}+1=(x+1)(x^{2m}-x^{2m-1}+\ldots+x2-x+1)\)

azonosságokat, az elsőből persze

\(\displaystyle x^{2m}-1=(x-1)(x+1)(x^{2m-2}+x^{2m-4}+\ldots+x2+1)\)

is leolvasható. Legyen \(\displaystyle b=a^{(n,k)}\), ekkor a keresett legnagyobb közös osztó

\(\displaystyle d=(b^N+1,b^K+1)\)

alakba írható, ahol \(\displaystyle N=n/(n,k)\) és \(\displaystyle K=k/(n,k)\) már egymáshoz relatív prímek.

1. Tegyük fel először, hogy az egyik kitevő, mondjuk \(\displaystyle N\), páros, a másik, \(\displaystyle K\), pedig páratlan. Ekkor a fenti azonosságokból adódó oszthatósági szabályok miatt \(\displaystyle b^N+1\mid b^{NK}+1\) és \(\displaystyle b^K+1\mid b^{NK}-1\), vagyis mind \(\displaystyle b^{NK}+1\), mind \(\displaystyle b^{NK}-1\) osztható \(\displaystyle d\)-vel. Ezért \(\displaystyle d\) értéke csak 1 vagy 2 lehet, attól függően, hogy \(\displaystyle b\) (és így persze \(\displaystyle a\) is) páros, avagy páratlan.

2. Abban az esetben, ha mindkét kitevő páratlan, nyilván mind \(\displaystyle b^N+1\), mind \(\displaystyle b^K+1\) osztható \(\displaystyle b+1\)-gyel, vagyis \(\displaystyle b+1\mid d\). Másrészt

\(\displaystyle d\mid (b^{2N}-1,b^{2K}-1)=b^{(2N,2K)}-1=b2-1=(b-1)(b+1),\)

ahol az első egyenlőség könnyen igazolható például az ún. euklideszi algoritmus segítségével. Mivel azonban

\(\displaystyle b^N+1=(b+1)(b^{N-1}-b^{N-2}+b^{N-3}-b^{N-4}+\ldots+b2-b+1),\)

és itt a második tényező \(\displaystyle b-1\)-gyel osztva 1 maradékot ad, minélfogva ahhoz relatív prím kell legyen, csakis \(\displaystyle d=b+1\) lehetséges.


Statistics:

28 students sent a solution.
5 points:Ágoston Tamás, Blázsik Zoltán, Bodor Bertalan, Dinh Hoangthanh Attila, Éles András, Fonyó Dávid, Huszár Kristóf, Nagy 648 Donát, Somogyi Ákos, Tuan Nhat Le, Varga 171 László, Weisz Ágoston, Weisz Gellért.
4 points:Frankl Nóra, Lovas Lia Izabella, Mester Márton.
3 points:2 students.
1 point:4 students.
0 point:6 students.

Problems in Mathematics of KöMaL, May 2009