2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Apr 24 '13 at 0:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – aSteve Apr 24 '13 at 20:46
  • $\begingroup$ @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$. $\endgroup$ – Warren Moore Apr 24 '13 at 21:15
  • $\begingroup$ 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. $\endgroup$ – aSteve Apr 26 '13 at 22:08
  • $\begingroup$ @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. $\endgroup$ – Warren Moore Apr 26 '13 at 22:34
  • $\begingroup$ 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. $\endgroup$ – aSteve Apr 27 '13 at 12:25

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.