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. 462. feladat (2008. október)

A. 462. Legyen p páratlan prímszám és 1<a<p egész. Bizonyítsuk be, hogy


\sum_{k=0}^{p-2} {(-1)}^k a^{k^2}

akkor és csak akkor osztható p-vel, ha létezik olyan páratlan k pozitív egész, amelyre az ak szám 1 maradékot ad p-vel osztva.

(5 pont)

A beküldési határidő 2008. december 15-én LEJÁRT.


Megoldás. Legyen r az a maradék rendre modulo p, azaz a legkisebb nemnegatív egész, amire ar\equiv1 (mod p). (Az a\equiv1 (mod p) esetben r=0.) Az álítás tehát az, hogy az S=\sum_{k=0}^{p-2} (-1)^k a^{k^2} összeg akkor és csak akor osztható p-vel, ha r páratlan.

Ha 1<a<p, akkor r pozitív egész, ami a kis Fermat-tétel miatt osztója (p-1)-nek.

(a) Ha r páratlan, akkor az (-1)kak2 sorozat 2r szerint periodikus modulo p, és


S=\sum_{k=0}^{p-2} {(-1)}^k a^{k^2} \equiv
\frac{p-1}{2r} \sum_{k=0}^{2r-1} {(-1)}^k a^{k^2} =
\frac{p-1}{2r} \left(
\sum_{k=0}^{r-1} (-1)^k a^{k^2} +
\sum_{k=0}^{r-1} (-1)^{k+r} a^{(k+r)^2} \right) =


= \frac{p-1}{2r} \left( \sum_{k=0}^{r-1} (-1)^k a^{k^2} +
(-1)^r\sum_{k=0}^{r-1} (-1)^k a^{k^2} \cdot (a^r)^{2k+r} \right)
\equiv

 \equiv \frac{p-1}{2r} \left( \sum_{k=0}^{r-1} (-1)^k a^{k^2} -
\sum_{k=0}^{r-1} (-1)^k a^{k^2} \right) = 0 \pmod{p}.

(Röviden, a k-adik és a (k+r)-edik tag kiejti egymást.)

(b) Ha r páros, r=2s, akkor az (-1)kak2 sorozat r szerint periodikus modulo p. Mivel (as+1)(as-1)=(ar-1)\equiv0 (mod p), azt is tudjuk, hogy as\equiv-1 (mod p).

Legyen T = \sum_{k=0}^{p-2} (-1)^k a^{-k^2}, és vizsgáljuk az ST szorzatot. Megmutatjuk, hogy ST nem osztható p-vel.


ST =
\left( \sum_{k=0}^{p-2} (-1)^k a^{k^2} \right)
\left( \sum_{\ell=0}^{p-2} (-1)^\ell a^{-\ell^2} \right) =
\sum_{k=0}^{p-2} \sum_{l=0}^{p-2} (-1)^{k+\ell} a^{k^2-\ell^2} \equiv


\sum_{k=0}^{p-2} \sum_{m=0}^{p-2} (-1)^{m} a^{k^2-(m-k)^2} \equiv
\sum_{m=0}^{p-2} (-a^m)^{-m} \sum_{k=0}^{p-2} (a^{2m})^k
\pmod{p}

Ha 2m osztható r-rel, azaz m osztható s-sel, akkor a2m\equiv1 (mod p), és \sum_{k=0}^{p-2} (a^{2m})^k \equiv -1~(\mod p). Minden más esetben


\sum_{k=0}^{p-2} (a^{2m})^k \equiv
\left((a^{2m})^{p-1}-1\right)
\left(a^{2m}-1\right)^{-1}
\equiv 0 \pmod{p}.

Ha m/s páros egész, akkor m is páros, -am\equiv-1 mod p), és (-am)-m\equiv((-1)2)m/2\equiv1 (mod p).

Ha pedig m/s páratlan egész, akkor am\equiv(as)m/s\equiv-1 (mod p) és (-am)-m\equiv1m\equiv1 (mod p).

Ezzel azt kapjuk, hogy az összegben csak az s-sel osztható m-ekhez kapunk 0-tól különböző maradékot, és ez a maradék mindig -1. Tehát


ST \equiv \frac{p-1}{s}\cdot(-1) = -\frac{p-1}s \pmod{p}.

Mivel 0<\frac{p-1}{s}<p, ez a maradék nem lehet a 0.


Statisztika:

5 dolgozat érkezett.
5 pontot kapott:Nagy 235 János, Tomon István.
2 pontot kapott:3 versenyző.

A KöMaL 2008. októberi matematika feladatai