Problem A. 479. (April 2009)

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 pont)

Deadline expired on May 15, 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:

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

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.

Already signed up?
New to KöMaL?