Feladat: 18.23.
Bizonyítsuk be, hogy ha
p prímszám, akkor
a) két mod
p kvadratikus maradék szorzata kvadratikus maradék;
b) egy-egy mod
p kvadratikus maradék és kvadratikus nem-maradék szorzata kvadratikus nem-maradék;
c) két mod
p kvadratikus nem-maradék szorzata kvadratikus maradék.
Megjegyzés. A feladat állításai együtt azt mondják ki, hogy a kvadratikus maradékok és nem-maradékok hasonlóan viselkednek, mint a valós számok között a pozitív és a negatív számok. Egy másik analógia, ha azt mondjuk, hogy úgy viselkednek, mint a valós és a képzetes számok, csak azzal a különbséggel, hogy itt minden szám vagy ,,valós", vagy ,,képzetes".
Megoldás: 18.23
a) következik abból, hogy két négyzetszám szorzata is négyzetszám.
b) bizonyításához tegyük fel, hogy valamely
x,y,z számokra igaz, hogy
A teljes maradékrendszerre vonatkozó tétel szerint van olyan
x', amelyre
xx'≡1modp Ennek négyzetével megszorozva a kongruencia mindkét oldalát azt kapjuk, hogy
tehát
y kvadratikus maradék. Vagyis ha egy kvadratikus maradékot valamely
y számmal szorozva kvadratikus maradékot kapunk, akkor
y is kvadratikus maradék. Azaz kvadratikus maradékot kvadratikus nem-maradékkal szorozva nem kaphatunk kvadratikus maradékot.
c) bizonyításához vegyünk egy kvadratikus nem-maradékot és szorozzuk végig minden nullától különböző maradékkal mod
p. Így
p-1 különböző (és nullától is különböző) maradékot kapunk. Amikor kvadratikus maradékkal szoroztunk, akkor b) szerint kvadratikus nem-maradékot kaptunk, tehát az így kapott
(p-1)/2 szám az előző (
18.22.) feladat megjegyzésében mondottak szerint
kimeríti az összes kvadratikus nem-maradékot. Azokra az esetekre, amikor kvadratikus nem-maradékkal szoroztunk, épp a
(p-1)/2 kvadratikus maradék maradt. Ezt akartuk bizonyítani: kvadratikus nem-maradékot kvadratikus nem-maradékkal szorozva kvadratikus maradékot kapunk.