Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is $p$ a prime there ? –  Iyengar Jun 17 '12 at 18:16
    
I added it, thanks. –  Jozef Jun 17 '12 at 18:41
1  
@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
1  
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
add comment

8 Answers

up vote 8 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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$

share|improve this answer
add comment

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

share|improve this answer
add comment

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

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.