show that if p is a prime divisor of $839$ and $(5/p)=1$ then $839$ is a prime number

Question

Show that if p is a prime divisor of $839$ = $38^2$ - $5*11^2$ then $(5/p)=1$. Use this fact to conclude that $839$ is a prime number.

Answer 1

Noting that $\sqrt{839} \sim 28.9$, it suffices to consider cases for those prime numbers less than $29$. All primes less than $29$ are: $2,3,5,7,11,13,17,19,23$ none of which divide $839$. Hence, it is prime.

Answer 2

Reverse engineering the hint the best I can:

• We have $839=38^2-5\cdot11^2$. So if $p$ is any prime divisor of $839$, then $$5\cdot11^2\equiv38^2\pmod p.$$ This implies that $5$ is a quadratic residue modulo $p$.
• By quadratic reciprocity $p$ is then a quadratic residue modulo $5$. In other words $p\equiv\pm1\pmod5$.
• The only primes $<\sqrt{839}$ and $\equiv\pm1\pmod5$ are $11$ and $19$. If $839$ were not a prime it would have a prime factor less than $\sqrt{839}$. But neither $11$ nor $19$ works (see Daniel's comment below!), so such a prime does not exist.
• Conclusion: $839$ is a prime.

In other words, my guess is that the hint is supposed to help you sieve out some of the candidate prime factors with a view of speeding up the verification that $839$ is a prime.