Residui quadratici

[FeddyStra]

Ecco a voi un bel problema sui residui quadratici.
Siano $ r_1, r_2, r_3, ...,r_n $ i residui quadratici modulo $ p $ primo escluso lo $ 0 $.
Si chiede di trovare $ k $, data la congruenza
$ r_1 \cdot r_2 \cdot r_3 \cdot ... \cdot r_n \equiv k $ $ (mod $ $ p) $.

[pic88]

Wilson's theorem

EDIT: più ovviamente il fatto che

i residui quadratici non nulli modulo p sono (p-1)/2

[FeddyStra]

EDIT: più ovviamente il fatto che

i residui quadratici non nulli modulo p sono (p-1)/2

Sì, ma poi non devi comunque utilizzare

il teorema di Wilson?

[pic88]

Si, nella mia soluzione uso tutti quei due fatti lì.

Non intendevo dire che il secondo portasse alla soluzione in modo più ovvio, ma che ovviamente dovevo usarlo per spiegarmi meglio!

Ciao

[HumanTorch]

O anche: dato che mod p il prodotto di più residui quadratici è un residuo quadratico e dato che se A è un residuo quadratico lo è anche A^{-1}, nel prodotto si semplificano tutti i numeri per coppie, data l'esistenza e l'unicità dell'inverso mod p. L'unico caso particolare sono quei numeri che coincidono con i propri inversi, ovvero tali che a^2=1 mod p. Ma questi sono +1 e -1, quindi |k|=1, con il segno che dipende, se -1 è residuo quadratico o meno, ovvero se (p-1)/2 è pari o dispari.