Problem B. 4078. (March 2008)

B. 4078. a and n are positive integers, such that n>1 and . Prove that (a-1;n)>1.

(5 pont)

Deadline expired on April 15, 2008.

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

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.

Statistics:

35 students sent a solution.
5 points:	Á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 points:	Kovács 729 Gergely.
3 points:	1 student.
2 points:	1 student.
1 point:	4 students.
0 point:	7 students.

Problems in Mathematics of KöMaL, March 2008