A B. 4078. feladat (2008. március)

B. 4078. Az a és n pozitív egész számokra n>1 és . Igazoljuk, hogy (a-1;n)>1.

(5 pont)

A beküldési határidő 2008. április 15-én LEJÁRT.

Megoldás: Legyen p az n szám legkisebb prímosztója. A feltétel miatt aⁿ 1 maradékot ad p-vel osztva. Mivel a nem lehet osztható p-vel, a kis Fermat tétel szerint a^p-1 is 1 maradékot ad p-vel osztva. Legyen k a legkisebb pozitív egész, amelyre a^k 1 maradékot ad p-vel osztva. Könnyen látható, hogy a^m pontosan akkor ad 1 maradékot p-vel osztva, ha m osztható k-val. Legyen ugyanis m=qk+r, ahol 0r<k, ekkor a^m=(a^k)^q 1 maradékot ad p-vel osztva, vagyis a^m pontosan akkor ad 1 maradékot ad p-vel osztva, ha a^r 1 maradékot ad p-vel osztva, ami r<k miatt éppen r=0 esetén teljesül.

Mindenezek alapján megállapítható, hogy k osztója n-nek és p-1-nek is. Ha most q a k szám egy prímosztója lenne, akkor miatt qp lenne, viszont miatt qp-1 is fennállna, ami lehetetlen. Ezért k-nak nincsen egyetlen prímosztója sem, vagyis k=1, az a szám tehát p-vel osztva 1 maradékot ad, vagyis a-1 és n legnagyobb közös osztója osztható p-vel.

Statisztika:

35 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Bodor Bertalan, Cséke Balázs, Dinh Hoangthanh Attila, Éles András, Fonyó Dávid, Huszár Kristóf, Márkus Bence, Nagy 648 Donát, Nagy-Baló András, Réti Dávid, Somogyi Ákos, Szabó 895 Dávid, Szőke Nóra, Tossenberger Anna, Tóth 369 László Márton, Varga 171 László, Véges Márton, Wagner Zsolt, Wang Daqian, Zieger Milán.
4 pontot kapott:	Kovács 729 Gergely.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2008. márciusi matematika feladatai