You seem to have misspoken. You know that if you square $3^{500001}$ you get $3^{1000002}$, which by Fermat's Little Theorem must be $1$ modulo $1000003$; there is no possibility of the square of $3^{1000002}$ being $-1$ modulo $1000003$.
But, since there are only two congruence classes whose square modulo $p$ is $1$, namely $1$ and $-1$, you know that $3^{500001}$ itself is either $1$ or $-1$ modulo $p$.
The key to this is Euler's Criterion:
Euler's Criterion. If $p$ is an odd prime and $\gcd(a,p)=1$, then $x^2 \equiv a\pmod{p}$ has two solutions if $a^{(p-1)/2}\equiv 1 \pmod{p}$, and no solutions if $a^{(p-1)/2}\equiv -1 \pmod{p}$.
So: $3^{500001} \equiv 1 \pmod{p}$ if and and only if $3$ is a square modulo $1000003$, and $3^{500001}\equiv -1\pmod{p}$ if and only if $3$ is not a square modulo $1000003$.
The question then transforms into "How do we tell if $3$ is a square modulo $1000003$?", or more generally:
Given $a$ and a large prime $P$, $1\lt a\lt P$, how do we tell if $a$ is a square modulo $P$?
The answer is that we do it pretty easily using Legendre or Jacobi symbols, as noted by Bill.
For instance, here, since $3$ and $1000003$ are both congruent to $3$ modulo $4$, quadratic reciprocity says that $\left(\frac{3}{1000003}\right) = -\left(\frac{1000003}{3}\right) = -\left(\frac{1}{3}\right) = -1,$ so $3$ is not a square modulo $1000003$, hence $3^{500001}\equiv -1\pmod{1000003}$.