# The first $4$ primes $p$ for which $15347$ has a square root mod $p$ are $2, 17, 23,$ and $29$

The first $4$ primes $p$ for which $15347$ has a square root mod $p$ are
$2, 17, 23,$ and $29$
How $2,17,23,$ and $29$ been calculated? If you can, please explain me the idea and the exact calculation.
#### Solutions Collecting From Web of "The first $4$ primes $p$ for which $15347$ has a square root mod $p$ are $2, 17, 23,$ and $29$"
You could use quadratic reciprocity, as suggested in the comments, but those primes are so small that a brute-force approach is also reasonable. To find out whether a large $n$ has a square root modulo a small prime $p$, first compute $x = n \bmod p$, and then check whether $y^2 \equiv x \bmod p$ for some $y \in \{0,1,\ldots,(p-1)/2\}$.