Problem A. 479. (April 2009)
A. 479. Decide whether there exists a positive integer n that is divisible by 103 and satisfies .
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 , and since 103 is odd we conclude
. Furthermore 103 is prime, and Fermat's theorem yields
. For d=gcd(2n,102) this yields
. Note that 102=6×17. If n is not divisible by 17, then d must be a divisor of 6, and
would imply
; a contradiction. Hence n is divisible by 17.
The original congruence yields
, and since 17 is odd we conclude
. Furthermore 17 is prime, and little Fermat yields
. For e=gcd(2n,16) this yields
. 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 yields
. 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