Pagina 1 di 1
Residui quadratici
Inviato: 02 giu 2007, 14:47
da 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) $.
Inviato: 02 giu 2007, 15:08
da pic88
Wilson's theorem
EDIT: più ovviamente il fatto che
i residui quadratici non nulli modulo p sono (p-1)/2
Inviato: 02 giu 2007, 18:23
da FeddyStra
pic88 ha scritto: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?
Inviato: 02 giu 2007, 19:59
da 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
Inviato: 02 giu 2007, 22:01
da 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.