Find all positive integers $n $ such that $n^2+n+7$ devided by 13. An idea please

Question

Find all positive integers $n $ such that $n^2+n+7$ devided by 13. An idea please

Answer 1

I'm assuming you want the value to be divisible by 13.

Since the values mod 13 (remainder when divided by 13) repeat every 13, we just need to test 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 13.

1: 1 + 1 + 7 = 9

2: 4 + 2 + 7 = 13 works

3: 9 + 3 + 7 = 19

4: 16 + 4 + 7 = 27

5: 25 + 5 + 7 = 37

6: 36 + 6 + 7 = 49

7: 49 + 7 + 7 = 63

8: 64 + 8 + 7 = 79

9: 81 + 9 + 7 = 97

10: 100 + 10 + 7 = 117 works

11: 121 + 11 + 7 = 139

12: 144 + 12 + 7 = 163

13: 169 + 13 + 7 = 189

So, the values that work should be:

2, 15, 28, 41, 54, etc.

and 10, 23, 36, 49, 62, etc.

Alternate solution:

$n^2+n+7$ in mod 13 is just $n^2+n-6$. This factors as $(n+3)(n-2)$, and then $n+3$ or $n-2$ is a multiple of 13, giving 10 and 2. We can continue as above.

Answer 2

Since $13$ is a prime number, then $\mathbb Z_{13}$ is a field. Hence the quadratic equation will work.

$$n^2+n+7 \equiv 0 \pmod {13}$$

Note that $2 \cdot 7 \equiv 1 \pmod {13}$. So $\dfrac 12 \equiv 7 \pmod{13}$.

\begin{align} n &\equiv \dfrac{-(1) \pm \sqrt{(1)^2-4(1)(7)}}{2(1)} \pmod{13} \\ n &\equiv 7 \cdot \left(-1 \pm \sqrt{1-28} \right) \pmod{13} \\ n &\equiv 7 \cdot \left(-1 \pm \sqrt{-27} \right) \pmod{13} \\ n &\equiv 7 \cdot \left(-1 \pm \sqrt{12} \right) \pmod{13} \\ n &\equiv 7 \cdot \left(-1 \pm 5 \right) \pmod{13} &\text{(Note $5^2 \equiv 25 \equiv 12 \pmod{13}$.)} \\ n &\in \{2, 10\} \end{align}

So $n^2+n+7$ is divisible by $13$ when $n$ is equivalent to $2$ or $10$ modulo $13$.

With some fooling around, you can do this without using the quadratic formula.

$$n^2 + n + 7 \equiv n^2-12n+20 \equiv (n-2)(n-10) \pmod{13}$$

so $n \in \{2,10\}$

or

$$n^2 + n + 7 \equiv n^2+n-6 \equiv (n+3)(n-2) \pmod{13}$$

so $n \in \{2,-3\} \equiv \{2,10\}$

Answer 3

Imagine taking the number $n$ and dividing by $13$ and getting a quotient $q$ and a remainder $r$.

Then $n = 13q + r = 13(q+1) + (r-13) $.

Now $r = 0,1,2,3,4,5,6,7,8,9,10,11,12$ and $r-13 = -13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1$.

So we can say $n = 13m + k$, where if $r \le 6$ then $m=q$ and $k =r$ (is between $0$ and $6$)

Or we can say $n =13m + k$ where if $r >6$ then $m=q+1$ and $k = r-13$ (is between $-1$ and $-6$).

So we can say $n =13m + k$ where $k = 0,\pm 1, pm 2,\pm 3, \pm 4, \pm 5, \pm 6$.

We don't care about $m$ but we do care about $k$.

$n^2 + n + 7=$

$(13m + k)^2 + (13m + k) +7=$

$169m^2 + 26mk + k^2 + 13m + k + 7=$

$13[13m^2 + 2mk + m] + k^2 + k + 7$.

This is divisible by $13$ if and only if $k^2 + k + 7$ is.

So the $m$ was not important and only the $k$ is. So we can go through the $k$ values one by one. There are only $12$ of them.

If $k =0$ then $k^2 + k + 7 = 7$ and that is not divisible by $13$.

If $k = \pm 1$ then $k^2 + k + 7 =1 \pm 1 + 7=$ either $7$ or $9$. Those are not divisible by $13$.

If $k =\pm 2$ then $k^2 + k + 7 = 4\pm 2 +7 =11\pm 2=$ either $9$ or $13$. $9$ is not divisible by $13$ but $13$ is. So if $n=13m+2$ for some value of $m$ then $n^2 + n+7$ is divisible by $13$. Ex if $n=2, 15, 28,etc.$

(Test them $2^2 + 2 + 7 = 13$. And $15^2 + 15 + 7= 225+15+7=247=13*19$ and so on....)

If $k =\pm 3$ then $k^2 + k + 7 = 9\pm 3 + 7= 16\pm 3=$ either $13$ or $19$. $13$ is divisible by $13$ but $19$ isn't. So if $n =13m -3$ for some value of $m$ then $n^2 + n + 7$ is divisible by $13$. Ex. if $n = 10,23, 36, .....$

(Test them. $10^2 + 10 + 7 =117 = 9*13$, $23^2 + 23 + 7 = (26 - 3)^2 + (26-3) +7= 26^2 -2*3*26 + 9 + 26-3 + 7 = 26^2-2*3*26 + 26 +9-3+7 = 13(2*13-2*3*2 + 2) + 13=13(2*13-2*3*2+2 +1)$. and so on....)

If $k=\pm 4$ then $k^2 + k + 7 = 16\pm 4+7=23\pm 4=$ either $19$ or $27$.

If $k =\pm 5$ then $k^2 + k+7 = 25\pm 5 + 7=32\pm 5=$ either $27$ or $37$.

If $k = \pm 6$ then $k^2 + k + 7 =36 \pm 6+7 =43\pm 6=$ either $37$ or $49$.

So $n^2 + n + 7$ is divisible by $13$ whenever $n =13m -3$ or $n = 13m + 2$. Or if $n \in \{10,23, 36,49, 62,......\}\cup \{2,15,28,41,....\}$.

Another way of putting this is if $n = 13m + 6\pm 4$

So $n \in \{6\pm 4, 19\pm 4, 32\pm 4,.....\} = \{2,10,15,23, 28,36,....\}$.

Answer 4

$$n^2+n+7 \equiv 0 \pmod {13}$$ which implies $$n(n+1)\equiv 6\pmod {13}$$

which by $$6=2(3)=(-3)(-2)$$

gives $$n\equiv -3,2\pmod {13}$$

which has fully positive form of $$n\equiv 2,10\pmod{13}$$

Answer 5

you see that , $13|n^2+n+7\implies13|(n+3)(n-2)+13$, that means $13|n+3\implies n\equiv 10 \pmod {13}$, or, $13|(n-2)\implies n\equiv 2\pmod {13}$.