How to calculate all the four solutions to $(p+5)(p-1) \equiv 0 \pmod {16}$? This is a kind of a plain question, but I just can't get something.
For the congruence and a prime number $p$: $(p+5)(p-1) \equiv 0\pmod {16}$.
How come that the in addition to the solutions 
$$\begin{align*}
p &\equiv 11\pmod{16}\\
p &\equiv 1\pmod {16}
\end{align*}$$ 
we also have
$$\begin{align*}
p &\equiv 9\pmod {16}\\
 p &\equiv 3\pmod {16}\ ?
\end{align*}$$
Where do the last two come from? It is always 4 solutions? I can see that they are satisfy  the equation, but how can I calculate them?
Thanks
 A: First note that $p$ has to be odd. Else, $(p+5)$ and $(p-1)$ are both odd.
Let $p = 2k+1$. Then we need $16 \vert (2k+6)(2k)$ i.e. $4 \vert k(k+3)$.
Since $k$ and $k+3$ are of opposite parity, we need $4|k$ or $4|(k+3)$.
Hence, $k = 4m$ or $k = 4m+1$. This gives us $ p = 2(4m) + 1$ or $p = 2(4m+1)+1$.
Hence, we get that $$p = 8m +1 \text{ or }8m+3$$ which is what your claim is as well.
EDIT
You have obtained the first two solutions i.e. $p = 16m+1$ and $p=16m + 11$ by looking at the cases $16 \vert (p-1)$ (or) $16 \vert (p+5)$ respectively.
However, note that you are leaving out the following possibilities.


*

*$2 \vert (p+5)$ and $8 \vert (p-1)$. This combination also implies $16 \vert (p+5)(p-1)$

*$4 \vert (p+5)$ and $4 \vert (p-1)$. This combination also implies $16 \vert (p+5)(p-1)$

*$8 \vert (p+5)$ and $2 \vert (p-1)$. This combination also implies $16 \vert (p+5)(p-1)$


Out of the above possibilities, the second one can be ruled out since $4 \vert (p+5)$ and $4 \vert (p-1)$, then $4 \vert ((p+5)-(p-1))$ i.e. $4 \vert 6$ which is not possible.
The first possibility gives us $ p = 8m+1$ while the second possibility gives us $p = 8m +3$.
Combining this with your answer, we get that $$p = 8m +1 \text{ or }8m+3$$
In general, when you want to analyze $a \vert bc$, you need to write $a = d_1 d_2$, where $d_1,d_2 \in \mathbb{Z}$ and then look at the cases $d_1 \vert a$ and $d_2 \vert b$.
A: The assertion $(p+5)(p-1) \equiv 0 \pmod{16}$ is equivalent to $16 \mid (p+5)(p-1)$. Then you consider cases: $2^4 \mid (p+5)$, $2^3 \mid (p+5)$ and $2 \mid p-1$, $2^2 \mid p+5$ and $2^2 \mid p-1$, etc. 
A: $$(p+5)(p-1) \equiv 0 \text{ (mod 16)} $$
$$\Leftrightarrow (p+5)(p-1)=16k $$
$$\Leftrightarrow p^{2}+4p+(-5-16k)=0$$
$$\Rightarrow p=-2 \pm\frac{1}{2}\sqrt{36+64k}$$
$$\Rightarrow p=-2 \pm \sqrt{9+16k}$$
$$k=0: p=-2\pm 3 \Rightarrow p \in \{1,-5\} \equiv \{1,11\} \text{ (mod 16)}$$
$$k=1: p=-2 \pm 5 \Rightarrow p \in \{3,-7\} \equiv \{3,9\} \text{ (mod 16)}$$
No other values of $k$ will yield unique integer solutions for $p \text{ (mod 16)}$. To see this, note that in order for $p$ to be an integer, we need $9+16k=q^{2}$ for some $q$. But mod 16, this reduces to $q^{2} \equiv 9 \text{ (mod 16)}$. Now a quick check shows that $q=3$ and $q=5$ are the only solutions. These correspond to $k=0$ and $k=1$, which yield the only 4 possible values: $p \in \{1,3,9,11\}$.
A: The first two solution can be seen easily , ie you have $p=-5,1=11,17 \pmod{16}$. To find the next two solution , as we know $p$ should satisfy $(p+5)(p-1)=16$ then the solution of this quadratic equation as $p=3,-7 =3,9\pmod {16}$
A: Hint : We can use the existence and unicity of  decomposition of all non zero integer $N$ as  $N=2^m q$  where $m$  is  an  integer  and  $q$  an  odd integer.
We  write  :
$p+5=2^k u $ and  $p-1 = 2^l v $ where $u$  and  $v$  are odd, that  implies  $u2^k-5 = v 2^l +1$  implies $u2^k-v 2^l = 6$, then we ca deduce that $\inf(k,l) \leq 1$
A: In the Theorem below put $\rm\:p\!=\!2,\ c=-5,\ d = 1\:$ to deduce that $\rm\:mod\ 16,\ (x\!+\!5)(x\!-\!1)\:$ has roots $\rm\:x \equiv -5,1\pmod 8,\:$ which are $\rm\:x,x\!+\!8 \equiv -5,1,3,9\pmod{16}.$ It has $\rm\,4\ (\!vs.\,2)$ roots by $\rm\:x\!+\!5 \equiv x\!-\!1\pmod{2},\:$ so both are divisible by $2$, so the other need be divisible only by $\rm8\ (\!vs. 16).$ Choosing larger primes $\rm\:p\:$ yields a quadratic with as many roots as you desire. These matters are much clearer $\rm\:p$-adically, e.g. google Hensel's Lemma.
Theorem $\ $ If prime $\rm\:p\:|\:c\!-\!d\:$ but $\rm\:p^2\nmid c\!-\!d\:$ then $\rm\:(x\!-\!c)(x\!-\!d)\:$ has $\rm\:2\!\;p\:$ roots mod $\rm\:p^4,\:$ namely $\rm\:x \equiv c+j\,p^3\:$ and $\rm\: x\equiv d+j\,p^3,\:$ for $\rm\:0\le j \le p\!-\!1.$
Proof $\ $ Note $\rm\: a = x\!-\!d,\ b = x\!-\!c\:$ satisfy the hypotheses of the Lemma below, thus we deduce $\rm\:p^4\:|\:(x\!-\!c)(x\!-\!d)\iff p^3\:|\:x\!-\!c\:$ or $\rm\:p^3\:|\:x\!-\!d,\:$ i.e. $\rm\:x\equiv c,d\pmod{p^3}.\:$ This yields the claimed roots $\rm\:mod\,\ p^4,\:$ which are all distinct since $\rm\:c+jp^3\equiv d+kp^3\:$ $\Rightarrow$ $\rm\:p^4\:|\:c\!-\!d+(j\!-\!k)p^3\:$ $\Rightarrow$ $\rm\: p^3\:|\:c\!-\!d,\:$ contra hypothesis. $\quad$ QED
Lemma $\ $ If prime $\rm\:p\:|\:a\!-\!b\:$ but $\rm\:p^2\nmid a\!-\!b\:$ then $\rm\:p^4\:|\:ab\iff p^3\:|\:a\ $ or $\rm\:p^3\:|\:b.$
Proof $\rm\,\ (\Rightarrow) \ \ p\:|\:ab\:\Rightarrow\:p\:|\:a\:$ or $\rm\:p\:|\:b,\:$ so $\rm\:p\:|\:a,b\:$ by $\rm\:a\equiv b\pmod p.$ But not $\rm\:p^2\:|\:a,b\:$ else $\rm\:p^2\:|\:a\!-\!b.\:$ So one of $\rm\:a,b\:$ is not divisible by $\rm\:p^2,\:$ hence the other is divisible by $\rm\:p^3.$  
$(\Leftarrow)\ \ $ As above, $\rm\:p\:|\:a,b.\:$ Since one is divisible by $\rm\:p^3,\:$ then $\rm\:p^4\:$ divides their product. $\ \ $ QED
A: (If you know a little abstract algebra.) 
The equation $$(p+5)(p−1)\equiv 0\pmod{16}$$ implies that either $p+5$ or $p-1$ is a zero divisor in $\mathbb{Z}/16\mathbb{Z}$; these are $$\{0,2,4,6,8,10,12,14\}.$$ However, you have some restrictions, e.g. if $p+5\equiv 2$, then $p-1$ should be congruent to $8$, which it isn't. Hence, this strategy is more arduous, but it gives the big picture.
