KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 479. Decide whether there exists a positive integer n that is divisible by 103 and satisfies 2^{2n+1}\equiv2\pmod{n}.

Dutch competition problem, composed by Hendrik Lenstra, Leiden

(5 points)

Deadline expired on 15 May 2009.


Solution. Suppose such an n exists. Since n is divisible by 103 we conclude 2^{2n+1}\equiv2\pmod{103}, and since 103 is odd we conclude 2^{2n}\equiv 1\pmod{103}. Furthermore 103 is prime, and Fermat's theorem yields 2^{102}\equiv1\pmod{103}. For d=gcd(2n,102) this yields 2^d\equiv1\pmod{103}. Note that 102=6×17. If n is not divisible by 17, then d must be a divisor of 6, and 2^d\equiv1\pmod{103} would imply 2^6\equiv1\pmod{103}; a contradiction. Hence n is divisible by 17.

The original congruence 2^{2n+1}\equiv2\pmod{n} yields 2^{2n+1}\equiv2\pmod{17}, and since 17 is odd we conclude 2^{2n}\equiv1\pmod{17}. Furthermore 17 is prime, and little Fermat yields 2^16\equiv1\pmod{17}. For e=gcd(2n,16) this yields 2^e\equiv1\pmod{17}. The cases e=1, e=2, e=4 yield immediate contradictions. Hence e is divisible by 8, and n is divisible by 4.

The original congruence 2^{2n+1}\equiv2\pmod{n} yields 2^{2n+1}\equiv2\pmod4. But now the LHS is divisible by 4, whereas the RHS is not. This contradiction shows that no such n exists.


Statistics on problem A. 479.
11 students sent a solution.
5 points:Bodor Bertalan, Éles András, Nagy 235 János, Nagy 314 Dániel, Nagy 648 Donát, Somogyi Ákos, Tomon István, Tossenberger Anna, Varga 171 László, Weisz Ágoston.
4 points:Backhausz Tibor.


  • Problems in Mathematics of KöMaL, April 2009

  • Támogatóink:   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