Az A. 393. feladat (2006. február)

A. 393. Igazoljuk, hogy ha n>1 egész szám, és 3ⁿ+4ⁿ osztható n-nel, akkor n osztható 7-tel.

(5 pont)

A beküldési határidő 2006. március 16-án LEJÁRT.

A 3ⁿ+4ⁿ páratlan és 3-mal sem osztható, ezért az n nem osztható sem 2-vel, sem 3-mal.

Az n páratlan, n=2k+1 és

3ⁿ+4ⁿ=3^.9^k+4^2k+1 $\equiv$ 3^.(-1)^k-1 (mod 5).

Ez a szám semmilyen k-ra nem osztható 5-tel, tehát az n nem osztható 5-tel sem.

Legyen p az n legkisebb prímosztója, és legyen c az a modulo p maradékosztály, amire 4c $\equiv$ 3 (mod p). Ekkor

4ⁿ(c²ⁿ-1)=(cⁿ-1)((4c)ⁿ+4ⁿ) $\equiv$ (cⁿ-1)(3ⁿ+4ⁿ) $\equiv$ 0 (mod p).

A 4ⁿ nem osztható p-vel, ezért

(1)	c²ⁿ $\equiv$ 1 (mod p).

A kis Fermat-tétel szerint

(2)	c^p-1 $\equiv$ 1!(mod p).

Legyen d a c rendje modulo p, azaz a legkisebb pozitív egész szám, amire c^d $\equiv$ 1 (mod p). Ekkor (1) alapján d osztója 2n-nek, (2) alapján pedig (p-1)-nek is, tehát osztója a két szám legnagyobb közös osztójának. Az n relatív prím (p-1)-gyel, mert nincs p-nél kisebb prímosztója. Ezért lnko(2n,p-1)=2. Tehát d|2,

p|c²-1=(c+1)(c-1).

Az nem lehet, hogy p|c-1, mert ez azt jelentené, hogy 4 $\equiv$ 4c $\equiv$ 3 (mod p). Tehát p|c+1 és

p|4(c+1)=4c+4 $\equiv$ 3+4=7 (mod p).

Ez pedig csak p=7 esetén teljesülhet.

Statisztika:

10 dolgozat érkezett.

5 pontot kapott: Erdélyi Márton, Estélyi István, Fischer Richárd, Gyenizse Gergő, Jankó Zsuzsanna, Kisfaludi-Bak Sándor, Nagy 224 Csaba, Paulin Roland, Tomon István.

1 pontot kapott: 1 versenyző.

A KöMaL 2006. februári matematika feladatai

10 dolgozat érkezett.
5 pontot kapott:	Erdélyi Márton, Estélyi István, Fischer Richárd, Gyenizse Gergő, Jankó Zsuzsanna, Kisfaludi-Bak Sándor, Nagy 224 Csaba, Paulin Roland, Tomon István.
1 pontot kapott:	1 versenyző.

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