# 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

-
Is $p$ a prime there ? –  Iyengar Jun 17 '12 at 18:16
I added it, thanks. –  Jozef Jun 17 '12 at 18:41
@Marvis: $\LaTeX$ tip: don't use (\bmod 16), use \pmod{16}, which will produce the correct spacing and parentheses. –  Arturo Magidin Jun 17 '12 at 19:04
In answer to "is it always 4 solutions?" No. If you had instead $p(p-1) \equiv 0\pmod {16}$ either $p$ or $p-1$ would have to be divisible by 16. If you want to explore further you could examine $p(p-2) \equiv 0\pmod {15}$. Hardy and Wright "An Introduction to the Theory of Numbers" has a good chapter on congruences to composite moduli. –  Mark Bennet Jun 17 '12 at 20:12
@ArturoMagidin Thanks. You had told me earlier as well to use \pmod instead of \bmod. I will use \pmod in future. –  user17762 Jun 18 '12 at 7:52

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.

1. $2 \vert (p+5)$ and $8 \vert (p-1)$. This combination also implies $16 \vert (p+5)(p-1)$
2. $4 \vert (p+5)$ and $4 \vert (p-1)$. This combination also implies $16 \vert (p+5)(p-1)$
3. $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$.

-

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.

-

$$(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\}$.

-

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$

-

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}$

-

For the general case, one could use Hensel's lemma:

http://en.wikipedia.org/wiki/Hensel%27s_lemma

-

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

-

(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.

-