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 a^k 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 a^r $\equiv$ 1 (mod p). (Az a $\equiv$ 1 (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)^ka^k² 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)^ka^k² sorozat r szerint periodikus modulo p. Mivel (a^s+1)(a^s-1)=(a^r-1) $\equiv$ 0 (mod p), azt is tudjuk, hogy a^s $\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 a^2m $\equiv$ 1 (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, -a^m $\equiv$ -1 mod p), és (-a^m)^-m $\equiv$ ((-1)²)^m/2 $\equiv$ 1 (mod p).

Ha pedig m/s páratlan egész, akkor a^m $\equiv$ (a^s)^m/s $\equiv$ -1 (mod p) és (-a^m)^-m $\equiv$ 1^m $\equiv$ 1 (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

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

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