Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show that there exist infinitely many values $n\in \mathbb{N}$ such that $8n^2+5$ is divisible by $7$ and $11$, without using diophantine equations.

I have $8n^2+5=8(n^2-9)+77$ and since $7\mid 77$ and $11\mid77$, I am searching for those natural numbers $n$ such that $7\mid(n^{2}-9)$ and $11\mid(n^2-9)$. From the first one I get $n=4+7k$ and the second one $n=8+11l$. Then I have to solve the following diophantine equation $7k-11l=4$, which I know that got infinitely many solutions.

But I would like to know a way to show this without the diophantine equations. Is that possible?

share|cite|improve this question
Find all $n$ from $0$ to $76,$ inclusive, for which this works. This will be a short finite list. Then, adding a multiple of $77$ to any of these numbers gives another solution. – Will Jagy Aug 10 '12 at 20:19
Observe that $(8)(3^2)+5=77$. This yields infinitely many solutions. For another bunch, use $(8)(-3)^2+5=77$. There are less crude families. – André Nicolas Aug 10 '12 at 20:27
I changed "$7|77$" to "$7\mid77$". The latter is considered standard, if I'm not mistaken. – Michael Hardy Aug 10 '12 at 23:20
up vote 5 down vote accepted

Hint $\rm\,\ 7,11\:|\:n^2\!-\!9 = (n\!-\!3)(n\!+\!3)\!\iff\! 77\:|\:n\!-\!3\ \ or\ \ 77\:|\:n\!+\!3\ \ or\ \ \begin{eqnarray}7\:|\:n\!&-&\!3\\ \rm 11\:|\:n\!&+&\!3\end{eqnarray}\ \ \ or\ \ \begin{eqnarray}7\:|\:n\!&+&\!3\\ \rm 11\:|\:n\!&-&\!3\end{eqnarray}$
Thus $\rm\,\ mod\ 77\!:\ n \equiv \sqrt{9}\equiv \pm3,\, \pm 25,\ $ i.e $\rm\:\pm(3,3),\, \pm(-3,3)\ mod\ (7,11)\:$

share|cite|improve this answer

If $n$ solves a polynomial equation $\mod m$ then the whole residue class of $n$ modulo $m$ solves this polynomial equation. you can try all residue classes $0,\ldots,m-1$ to check if there exists a residue class that solves the equation.

In your problem $n=3$ is a solution of $$8n^2+5=0 \mod 77$$ and therefore $$n=\cdots-74,3,80,\ldots$$ are also soluions

share|cite|improve this answer

Your Answer


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.