# Simple looking diophantine equation…

I recently found myself asking if the following (diophantine) expression ever evaluates to a square number:

$$5+12n$$

I was surprised both to be unable to stumble across an integer value for $n$ that results in a square number, and then surprised not see an obvious, eloquent, proof showing why this expression can never be square.

I would be interested in any pointers to work on the question of if/when equations of the form:

$$A + Bn = c^2$$

have a (non-trivial) solution. I'm assuming the convention that capital variables are constants, while non-capitals are free variables.

• For fixed $B$ this is straightforward: once you know that multiplication respects remainders $\bmod B$, you only have to check whether there is a solution with $c = 0, 1, 2, ... N-1$ to check whether there is any solution. – Qiaochu Yuan Apr 24 '13 at 0:54

## 1 Answer

Look modulo $B$: $$A\equiv c^2\text{ (mod }B\text{)}$$ I don't know whether or not you're familiar with Quadratic Reciprocity, but there is plenty of information on that Wikipedia article about conditions for $A$ to be a square modulo $B$ if $B$ is an odd prime. If there is no solution modulo $B$, then there is no solution in general.

In your specific case, $5$ is not a square modulo $12$ (you can easily check that squaring the numbers $1$ to $11$, and then finding their remainder when divided by $12$ will never give you $5$), so there is no solution.

• Thanks for the reply. Quadratic Reciprocity looks very relevant – was/am not (properly) familiar. :) While I can accept that there is no solution for 5+12x=y^2 I would still like to know why I can be sure that checking up-to 11 is sufficient. Why, for different constants, couldn't there be a solution where c>B despite no solution for c<B? – aSteve Apr 24 '13 at 20:46
• @aSteve If there exists an integer $c$ such that $c^2=A+Bn$, then $c^2\equiv A$ (mod $B$). If you take the contrapositive of that statement, then $c^2\equiv A$ (mod $B$) having no solutions implies that $c^2=A+Bn$ has no solutions. It's not about whether or not it has a solution $<B$, it's about whether or not it has a solution modulo $B$ (there is a difference!). There are only $B$ integers modulo $B$ (every integer, when divided by $B$, will leave a remainder $0\le r\le B-1$), so that's why you only check up to $B-1$. – Warren Moore Apr 24 '13 at 21:15
• I suspect I should read a text-book on modular arithmetic. (Recommendations welcome...) I can accept that it is sufficient to check up to B-1 (as values for c) but I still can't picture this justification for myself. – aSteve Apr 26 '13 at 22:08
• @aSteve Suppose that the integers $A+Bn$ and $c^2$ are equal. Then when you divide them by ANY integer, they leave the same remainder. That's what you're doing when you consider the equation modulo $B$. You're saying that if $A+Bn=c^2$, then $A+Bn$ and $c^2$ leave the same remainder when you divide by $B$. Since $Bn$ is perfectly divisible by $B$ with no remainder, we know that $A$ and $c^2$ must leave the same remainder when divided by $B$, i.e. $A\equiv c^2$ (mod $B$). If you can't find a solution modulo $B$ (checking up to $B-1$), then you couldn't have had a solution to start with. – Warren Moore Apr 26 '13 at 22:34
• I feel as if I'm "being difficult" - you eloquently explain those aspects of the problem I'm happy with... yet I can't reciprocate (pun) with a concise explanation of the potential problem... partly because I don't think a counter example exists. Essentially, the LHS looks "linear" - while the RHS is "more" "non-linear" - and that feels relevant. What if I replaced c^2 with f(c) - and define f(c)=A when c=13B and 0 otherwise? I can see that your approach worked, but I'm less clear about why it "must work", and the limits to which this technique can be stretched. – aSteve Apr 27 '13 at 12:25