KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4078. (March 2008)

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

(5 pont)

Deadline expired on 15 April 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 an 1 maradékot ad p-vel osztva. Mivel a nem lehet osztható p-vel, a kis Fermat tétel szerint ap-1 is 1 maradékot ad p-vel osztva. Legyen k a legkisebb pozitív egész, amelyre ak 1 maradékot ad p-vel osztva. Könnyen látható, hogy am pontosan akkor ad 1 maradékot p-vel osztva, ha m osztható k-val. Legyen ugyanis m=qk+r, ahol 0\ler<k, ekkor am=(ak)q 1 maradékot ad p-vel osztva, vagyis am pontosan akkor ad 1 maradékot ad p-vel osztva, ha ar 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 q\mid k\mid n miatt q\gep lenne, viszont q\mid k\mid p-1 miatt q\lep-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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley