Hi,
How would you figure out if there is a solution to a congruence equation like 2^x = -1 mod 5003. I don't know if it's better to think about it as 2^x + 1 = 0 mod 5003 or 2^x = 5002 mod 5003 or what. Any help would be appreciated. Thanks.
Hi,
How would you figure out if there is a solution to a congruence equation like 2^x = -1 mod 5003. I don't know if it's better to think about it as 2^x + 1 = 0 mod 5003 or 2^x = 5002 mod 5003 or what. Any help would be appreciated. Thanks.
The answer to this question is given by Euler's criterion, along with Gauss's second supplement to the quadratic reciprocity law. Euler's criterion states that for an odd prime $\displaystyle p$,
$\displaystyle \left(\frac{a}{p}\right)\equiv a^{(p-1)/2} \mod p$
and Gauss's second supplement to the quadratic reciprocity law states that
$\displaystyle \left(\frac{2}{p}\right)\equiv (-1)^{(p^2-1)/8} \mod p$.
What can you conclude from this?