Az A. 479. feladat (2009. április)

A. 479. Létezik-e olyan, 103-mal osztható pozitív egész n, amire

$2^{2n+1}\equiv2\pmod{n}?$

Holland versenyfeladat; szerzője Hendrik Lenstra (Leiden)

(5 pont)

A beküldési határidő 2009. május 15-én LEJÁRT.

Megoldásvázlat. Megmutatjuk, hogy nem létezik ilyen n.

Tegyük fel, hogy valamely n pozitív egészre

$2^{2n+1}\equiv2\pmod{n}.$

Mivel 103|n egész és 103 páratlan, a feltételből $2^{2n+1}\equiv2\pmod{103}$ és

$2^{2n} \equiv 1 \pmod{103}.$

(1)

A Fermat-tétel miatt (103 prím)

$2^{102} \equiv 1 \pmod{103}.$

(2)

Az (1) és (2) együtt azt mondja, hogy

$2^d \equiv 1 \pmod{103},$

(3)

ahol d=(2n,102). A 102 prímtényezős felbontása 2^.3^.17, és (3) nem teljesülhet d $\le$ 6 esetén. Tehát d nem osztója a 6-nak, következésképp 17|d és így 17|n.

A fenti gondolatmenetet ismételjük meg 103 helyett 17-tel.

$2^{2n} \equiv 1 \pmod{17},$

(4)

$2^{16} \equiv 1 \pmod{17},$

(5)

$2^e \equiv 1 \pmod{17},$

(6)

ahol e=(2n,16).

Az e=1, e=2 és e=4 esetekben (6) nem teljesül, mert 1<2^e<17.

Ha e=8 vagy e=16, akkor e|2n miatt 4|n, (*) baloldala osztható 4-gyel, (*) jobboldala viszont nem osztható 4-gyel. A (*) kongruencia ilyenkor sem teljesülhet.

Statisztika:

11 dolgozat érkezett.

5 pontot kapott: 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 pontot kapott: Backhausz Tibor.

A KöMaL 2009. áprilisi matematika feladatai

11 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	Backhausz Tibor.

Már regisztráltál?
Új vendég vagy?