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. 746. feladat (2019. március)

A. 746. Legyen \(\displaystyle p\) prímszám. Hány megoldása van az \(\displaystyle x^2+y^2+z^2+1\equiv 0\pmod{p}\) kongruenciának a modulo \(\displaystyle p\) maradékosztályok körében?

Javasolta: Gyenes Zoltán (Budapest)

(7 pont)

A beküldési határidő 2019. április 10-én LEJÁRT.


Megoldás. Ha \(\displaystyle p=2\), akkor pontosan \(\displaystyle 4\) megoldása van a kongruenciának.

Számoljuk meg a megoldásokat \(\displaystyle z\) értéke szerint! Az összes megoldás száma

\(\displaystyle N=\sum_{z=0}^{p-1} n(-1-z^2),\)

ahol \(\displaystyle n(a)\) jelöli azt, hogy az \(\displaystyle a\) mod \(\displaystyle p\) maradék hányféleképpen áll elő \(\displaystyle x^2+y^2\) alakban.

Lemma. Az összes nem nulla \(\displaystyle a\) maradékra \(\displaystyle n(a)\) értéke megegyezik.

Bizonyítás. Először is, \(\displaystyle n(a)\ge 1\) minden \(\displaystyle a\)-ra, hiszen az \(\displaystyle \{x^2\}\) és \(\displaystyle \{a-y^2\}\) maradékosztály-halmazoknak egyaránt \(\displaystyle \frac{p+1}{2}\) eleme van, s így nem lehetnek diszjunktak. (A négyzetszámok maradékai \(\displaystyle p\)-vel osztva \(\displaystyle \frac{p+1}{2}\)-félék lehetnek, mert \(\displaystyle x^2\equiv x'^2\) mod \(\displaystyle p\) pontosan akkor, ha \(\displaystyle x\equiv \pm x'\) mod \(\displaystyle p\).)

Továbbá \(\displaystyle (x+yi)(u+vi)=(xu-yv)+(xv+yu)i\) azonosságot konjugálva és összeszorozva (igen, itt \(\displaystyle i=\sqrt{-1}\): vö. Euler-azonosság) megkapjuk, hogy

\(\displaystyle (x^2+y^2)\cdot (u^2+v^2)=(xu-yv)^2+(xv+yu)^2.\)

Emiatt az \(\displaystyle x^2+y^2\equiv a\) minden megoldásához hozzárendelhető egy megoldása az \(\displaystyle X^2+Y^2\equiv a(u^2+v^2)\)-nek, ami különböző megoldáshoz különböző megoldást rendel \(\displaystyle u^2+v^2\not\equiv 0\) esetén, hisz \(\displaystyle (x+yi)(u+vi)\) ismeretében \(\displaystyle (u-vi)\)-vel s majd \(\displaystyle u^2+v^2\) mod \(\displaystyle p\) vett inverzével szorozva \(\displaystyle x+yi\) visszanyerhető. Mivel \(\displaystyle u^2+v^2\) az összes maradékosztályt befutja, így \(\displaystyle a(u^2+v^2)\) is befutja az összes maradékosztályt (ha \(\displaystyle a\not\equiv 0\)), s így \(\displaystyle n(a)\le n(b)\) bármely két nem nulla maradékosztályra, ahonnan kész. \(\displaystyle \blacksquare\)

A befejezést két esetben végezzük.

1. eset. Van \(\displaystyle c\) megoldása az \(\displaystyle x^2+1\equiv 0\) mod \(\displaystyle p\) kongruenciának. Ekkor pontosan két megoldása van: \(\displaystyle x\equiv \pm c\).

Ez esetben \(\displaystyle n(0)=1+2(p-1)=2p-1\), mert \(\displaystyle x^2+y^2\equiv 0\) pontosan akkor, ha \(\displaystyle y\equiv 0\) s \(\displaystyle x\equiv 0\) vagy \(\displaystyle y\not\equiv 0\) s így \(\displaystyle (xy^{-1})^2+1\equiv 0\), azaz \(\displaystyle x\equiv \pm yc\). Innen nem nulla maradékokra \(\displaystyle n(a)=\frac{p^2-(2p-1)}{p-1}=p-1\).

Az \(\displaystyle n(-1-z^2)\) értéke \(\displaystyle z\equiv \pm c\)-re \(\displaystyle n(0)=2p-1\) lesz, a többi \(\displaystyle z\) értékre pedig \(\displaystyle p-1\). Emiatt

\(\displaystyle N=2(2p-1)+(p-2)(p-1)=p^2+p.\)

2. eset. Nincs megoldása az \(\displaystyle x^2+1\equiv 0\) mod \(\displaystyle p\) kongruenciának.

Ez esetben \(\displaystyle n(0)=1\), mert \(\displaystyle x^2+y^2\equiv 0\) nem állhat fent nem zérus \(\displaystyle x,y\)-ra. Innen nem nulla maradékokra \(\displaystyle n(a)=\frac{p^2-1}{p-1}=p+1\). Továbbá \(\displaystyle -1-z^2\) értéke sosem lesz zérus, így

\(\displaystyle N=p\cdot (p+1)=p^2+p.\)

Tehát a megoldás \(\displaystyle p=2\)-re \(\displaystyle 4\), \(\displaystyle p>2\)-re pedig vicces módon mindig \(\displaystyle p^2+p\).


Statisztika:

Az A. 746. feladat értékelése még nem fejeződött be.


A KöMaL 2019. márciusi matematika feladatai