 |
A B. 4187. feladat (2009. május) |
B. 4187. Legyenek a, k és n pozitív egész számok. Határozzuk meg az an+1 és ak+1 számok legnagyobb közös osztóját.
(5 pont)
A beküldési határidő 2009. június 15-én LEJÁRT.
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.
Statisztika:
28 dolgozat érkezett. 5 pontot kapott: Á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 pontot kapott: Frankl Nóra, Lovas Lia Izabella, Mester Márton. 3 pontot kapott: 2 versenyző. 1 pontot kapott: 4 versenyző. 0 pontot kapott: 6 versenyző.
A KöMaL 2009. májusi matematika feladatai