4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – saulspatz Jan 31 at 17:08
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ More generally there are algorithms to compute modular square roots such as those of Tonelli-Shanks and Cipolla. But they are overkill for small numbers like this. $\endgroup$ – Bill Dubuque Jan 31 at 19:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you meant 6 instead of 64 $\endgroup$ – J. W. Tanner Jan 31 at 18:15
  • $\begingroup$ @J.W.Tanner:yes. Thanks $\endgroup$ – Ross Millikan Jan 31 at 19:59
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why the down-vote? I was trying to explain in language OP could understand. (Note, e.g., that OP did not say "mod".) $\endgroup$ – J. W. Tanner Feb 3 at 13:36
-1
$\begingroup$

Solution

Check that image, I have tried solving for x = 13i + 3. You can try similarly for x = 13i + 8

$\endgroup$
  • $\begingroup$ Welcome to MathStackExchange. Your help is appreciated, but if you could please type down your solution, this would be much better for the posterity than an image. The idea here is to create a usable knowledge database structures as questions and answers. $\endgroup$ – Mefitico Jan 31 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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