Diffie-Hellman and the last bit

$5$ is a Primitive root $\text{ (mod 10007)}$ . Thus, $\text{ord}_{10007} 5 = 10006$ .

Hence, $5^x \equiv 1 \text{ (mod 10007)} \Rightarrow \text{10006 | x}$ .

$$

Since $10006 = 2 \times 5003$ ,

$5^{5003m} \equiv 2^{5003} \equiv 1 \text{ (mod 10007)}$ if $m$ is even and $5^{5003m} \equiv 2^{5003} \equiv -1 \text{ (mod 10007)}$ if $m$ is odd.

$5^{5003n} \equiv 3^{5003} \equiv 1 \text{ (mod 10007)}$ if $n$ is even and $5^{5003n} \equiv 3^{5003} \equiv -1 \text{ (mod 10007)}$ if $n$ is odd.

$$

Euler's criterion tells that $\left(\frac{2}{10007}\right)_L \equiv 2^{5003} \text{ (mod 10007)}$ and $\left(\frac{3}{10007}\right)_L \equiv 3^{5003} \text{ (mod 10007)}$ .

Second Supplement to Quadratic Reciprocity tells that $\left(\frac{2}{10007}\right)_L = 1$ , since $10007 \equiv -1 \text{ (mod 8)}$ .

Law of Quadratic Reciprocity tells that $\left(\frac{3}{10007}\right)_L = \left(\frac{-10007}{3}\right)_L = \left(\frac{1}{3}\right)_L = 1$ , since $10007 \equiv 3 \text{ (mod 4)}$ and $3 \equiv 3 \text{ (mod 4)}$ .

$$

Thus, $2^{5003} \equiv 3^{5003} \equiv 1 \text{ (mod 10007)}$ .

$$

$$

Since $2^{5003} \equiv 1 \text{ (mod 10007)}$ and $3^{5003} \equiv 1 \text{ (mod 10007)}$ , $\boxed{\text{m, n are both even}}$ .