 |
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
xm−1=(x−1)(xm−1+xm−2+…+x+1)
és az
x2m+1+1=(x+1)(x2m−x2m−1+…+x2−x+1)
azonosságokat, az elsőből persze
x2m−1=(x−1)(x+1)(x2m−2+x2m−4+…+x2+1)
is leolvasható. Legyen b=a(n,k), ekkor a keresett legnagyobb közös osztó
d=(bN+1,bK+1)
alakba írható, ahol N=n/(n,k) és K=k/(n,k) már egymáshoz relatív prímek.
1. Tegyük fel először, hogy az egyik kitevő, mondjuk N, páros, a másik, K, pedig páratlan. Ekkor a fenti azonosságokból adódó oszthatósági szabályok miatt bN+1∣bNK+1 és bK+1∣bNK−1, vagyis mind bNK+1, mind bNK−1 osztható d-vel. Ezért d értéke csak 1 vagy 2 lehet, attól függően, hogy b (és így persze a is) páros, avagy páratlan.
2. Abban az esetben, ha mindkét kitevő páratlan, nyilván mind bN+1, mind bK+1 osztható b+1-gyel, vagyis b+1∣d. Másrészt
d∣(b2N−1,b2K−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
bN+1=(b+1)(bN−1−bN−2+bN−3−bN−4+…+b2−b+1),
és itt a második tényező b−1-gyel osztva 1 maradékot ad, minélfogva ahhoz relatív prím kell legyen, csakis 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
|
|