Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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

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

(5 pont)

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


A 3n+4n 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

3n+4n=3.9k+42k+1\equiv3.(-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\equiv3 (mod p). Ekkor

4n(c2n-1)=(cn-1)((4c)n+4n)\equiv(cn-1)(3n+4n)\equiv0 (mod p).

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

(1)c2n\equiv1 (mod p).

A kis Fermat-tétel szerint

(2)cp-1\equiv1!(mod p).

Legyen d a c rendje modulo p, azaz a legkisebb pozitív egész szám, amire cd\equiv1 (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|c2-1=(c+1)(c-1).

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

p|4(c+1)=4c+4\equiv3+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