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

$\begingroup$

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?

$\endgroup$ 0

2 Answers

$\begingroup$

Use the law of quadratic reciprocity.

$\endgroup$ 9 $\begingroup$

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

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy