# The Miller-Rabin Test clarification

I'm teaching myself cryptography but have realised that it has a lot of number theory as a part of it, one area which I'm a bit confused over is the Miller-Rabin test and how to use it in questions. A question which I have come across is:

Prove that $n^2=4 \space mod \space p$ if $p$ {is an odd prime?} then there are two solutions $n = \pm2$ if $p$ is an odd prime

Find an example of p where $n^2 = 9 \space mod \space p$ has one solution for $n \space mod \space p$

the part in curly brackets is missing from the question I am assuming that this is a mistake and what is inside the brackets should, in fact, be there.

Any help with this question would be extremely helpful and really appreciated!

EDIT: Forgot to add in this line:

The Miller-Rabin Test uses the fact that the only two solutions to the equation $n^2=1 \space mod \space p$ are $n=\pm1$ if $p$ is an odd prime

• How are those questions related to the Miller-Rabin-Test ? – Peter Mar 29 '17 at 11:43
• @Peter The Miller-Rabin Test uses the fact that the only two solutions to the equation $n^2=1 \space mod \space p$ are $n= \pm 1$ if $p$ is an odd prime – Unblazon Mar 29 '17 at 11:51
• $n^2\equiv 4\mod p$ means $p|n^2-4=(n-2)(n+2)$. A prime divides a product if and only if it divides one of the factors. If $p$ is odd, then $-2\ne 2\mod p$, so we have two distinct solutions. For the second question, you can choose $p=2$ or $p=3$. For every $p>3$, we have again two distinct solutions. – Peter Mar 29 '17 at 12:16