I am solving CRYPTO1 problem. This problem requires to solve following equation:
$$x^2=q(\mod p)$$
where I am given $p=4,000,000,007$ and q is also given. I followed http://mathworld.wolfram.com/QuadraticResidue.html to solve this. I am able to understand Fermat's little Theorem but confused at equation 10 of the given link:
$x=a^{k+1} (\mod p)$ | when $p=4\ast K+3$
Can someone please help me in understanding this part of the equation?