Thread: 2^x in a congruence equation

1. 2^x in a congruence equation

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.

2. Originally Posted by jimmyjimmyjimmy
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.

An idea: As $\displaystyle (2,5003)=1$, Fermat's Little Theorem tells us that $\displaystyle 2^{5002}=1\!\!\!\!\pmod{5003}\Longrightarrow 2^{2501}=\pm 1\!\!\!\!\pmod{5003}$

Tonio

3. 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?