How to check if $5$ is a square $\mod 701$ without a calculator

The Legendre symbol tells us to calculate $5^{350} \mod 701$, but this question was on an exam where no calculators are allowed, so I wasn't able to do this question. How can you find if $5$ is a square $\mod 701$ without a calculator if $701$ is prime? What if it's not a prime number?

Use the law of quadratic reciprocity.

• Since $5\equiv 1(4)$, 5 is a quadratic residue $\mod 701$ iff $701$ is a quadratic residue $\mod 5$. Can you check if 701 is a quadratic residue $\mod 5$? – LASV Mar 24 '15 at 20:15
• The formula you put above my first comment answers your question: Let $p=5, q=701$. Since $5$ is congruent to 1 mod 4, $p-1/2$ is even and hence the right side is equal to one. Now you know ${5 \choose 701} {701 \choose 5}=1$. But ${701 \choose 5}$ is easy to compute, right? – LASV Mar 24 '15 at 20:24
• The Legendre symbol is only for odd primes, correct? An odd prime is of the type $p\equiv 1 \mod 4$ or $p\equiv 3 \mod 4$. If $p\equiv 1 \mod 4$, the exponent on the right side is even, hence you get a value of 1 (Is this clear? $p-1$ is divisible by 4). – LASV Mar 24 '15 at 20:30
• The law of quadratic reciprocity splits the behavior of the primes in 2 categories: 1 mod 4 and 3 mod 4. – LASV Mar 24 '15 at 20:31
• The sign on the right side is still positive if either prime is congruent to 1 mod 4. – LASV Mar 25 '15 at 2:45

Is there anyway to solve this using Fermat's little theorem? a^(p-1) ≡ 1 mod p.

5^700 ≡ 1 mod 701

(5^350)^2 ≡ 1 mod 701

But I'm not sure if this tells us anything about 5^350 mod 701