 |
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 (13 versenyző). 4 pontot kapott: Frankl Nóra, Lovas Lia Izabella, Mester Márton (3 versenyző). 3 pontot kapott: 2 versenyző. 1 pontot kapott: 4 versenyző. 0 pontot kapott: 6 versenyző.
A KöMaL 2009. májusi matematika feladatai