4

For the equation $y = 4x^2 + 8x + 5$, what are the integer values of x such that y/13 is an integer?

For example, if x = 3, $y = 4(3^2) + 8(3) + 5$ = 65 which is divisible by 13

if x = 8, y = 325 which is divisible by 13

if x = 16, y = 1157 which is divisible by 13

if x = 21, y = 1937 which is divisible by 13

I am guessing that values of x = 13i + 3 or x = 13i + 8 where i is an integer will result in a value of y that is evenly divisible by 13.

How do you prove that x = 13i + 3 or x = 13i + 8 will result in a value of y that is evenly divisible by 13?

Is there a general proof to find values of x that will result in a value of y that is evenly divisible by an odd integer p?

temp watts
  • 333
  • You want to solve $4x^2+8x+5\equiv0\pmod{13}$ For such a small problem, you can just substitute the values $0,1,2,\dots,12$ and see which give solutions. Otherwise, write $4x^2+8x+5=(2x+2)^2+1$ and analyze $(2x+2)^2\equiv-1\pmod{13}$ – saulspatz Jan 31 '19 at 17:08

5 Answers5

4

Let us try with this approach:

$\begin{align} 4x^2+8x+5 &= 4(x+1)^2+1 &\equiv 0 &\quad(\text{mod} 13)\\ &\Rightarrow 4(x+1)^2 &\equiv 12 &\quad(\text{mod} 13)\\ &\Rightarrow (x+1)^2 &\equiv 3 &\quad(\text{mod} 13)\end{align}\\$

Substituting for $x+1 = f$ we are looking to take the square-root of 3 modulo 13. The following holds true: $$n^2 \equiv (13-n)^2 \quad (\text{mod} 13)$$

It suffices to look at numbers from 0 to 6:

$\begin{align} 0^2 &\equiv 0 (\text{mod} 13),\\ 1^2 &\equiv 1 (\text{mod} 13),\\ 2^2 &\equiv 4 (\text{mod} 13),\\ 3^2 &\equiv 9 (\text{mod} 13),\\ 4^2 &\equiv 3 (\text{mod} 13),\\ 5^2 &\equiv 12 (\text{mod} 13),\\ 6^2 &\equiv 10 (\text{mod} 13). \end{align}$

Thus numbers of the form $f = 13m + 4$ solve the problem. Then also $f = 13m + 9$ will solve the problem. Since $x = f-1$ our solutions are numbers of the form: $x \in \{13m + 3, 13m +8, \text{where } m\geq 0\}$.

Snake707
  • 1,041
  • 5
  • 7
1

You are looking for solutions to $4x^2+8x+5\equiv 0 \pmod {13}$. You can do the usual quadratic formula and find $x=\frac {-8 \pm \sqrt{64-80}}8$. Don't let the negative number under the square root bother you because $\pmod {13}$ we have $-16 \equiv 10$. You need to find whether $10$ is a square $\bmod 13$. One way is to just try them. Here we find $6^2 \equiv 7^2 \equiv 10 \pmod {13}$. Now noting that $8\cdot 5 \equiv 1 \pmod {13}$ we can say that $x=5(-8\pm 6)\equiv 3,8 \pmod {13}$

There is a whole theory of quadratic reciprocity that says when things are square roots in rings of integers. I have not studied it.

Ross Millikan
  • 374,822
1

Hint $\bmod 13\!:\,\ 0\equiv -3(4x^2\!+\!8x+5)\equiv x^2\! +\!2x\!-\!15\equiv (x\!+\!5)(x\!-\!3)\ $ so $\,x\equiv -5,3$

Bill Dubuque
  • 272,048
0

You're on the right track.

When $x=13i+3$, $y=4(13i+3)^2+8(13i+3)+5= 4(169i^2+78i+9)+8(13i+3)+5$.

Leaving out some multiples of $13$, this is $4\times 9+8\times3+5=36+24+5=65=5 \times 13$.

This shows that, when $x=13i+3$, $y$ is a multiple of $13.$

(I'll leave $x=13i+8$ as an exercise.)

J. W. Tanner
  • 60,406
  • Why the down-vote? I was trying to explain in language OP could understand. (Note, e.g., that OP did not say "mod".) – J. W. Tanner Feb 03 '19 at 13:36
0

Completing the square; $$4x^2+8x+5=(2x+2)^2+1,$$ so solving the congruence $\;4x^2+8x+5\equiv 0\mod 13$ amounts to solving $$\bigl(2(x+1)\bigr)^2\equiv -1\mod 13,$$ and ultimately to finding the square roots $y$ of $-1\bmod 13$ (we know this is possible because $13\equiv 1\mod 4$).

Note that $5^2\equiv -1\mod 13$, hence the other square root is $-5\equiv 8$, and since $2^{-1}\equiv 7\mod 13$, the solutions in $x$ are $$ x\equiv 7\cdot\pm 5 -1\equiv 8,3\mod 13.$$

Bernard
  • 175,478