2

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.

aSteve
  • 147
  • 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 00:54

1 Answers1

4

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.

Warren Moore
  • 3,931
  • 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
  • @aSteve You're not being difficult at all! This method works for any polynomial (linear or not) with integer coefficients. The $f$ that you've concocted there isn't a polynomial. You can rewrite $5+12n=c^2$ as $f(x,y)=5+12x-y^2$ for example. If you really want to see a limitation, consider $g(x)=(x^2-2)(x^2-17)(x^2-34)$. This polynomial has solutions modulo $n$ for all n, but has no integer solutions in general. So in a sense, this method doesn't tell you anything about $g(x)$. This method will only help you decide if an equation doesn't have solutions, it won't work the other way around! – Warren Moore Apr 27 '13 at 16:22
  • Ta again... 'any polynomial' makes sense to me. Your g(x) looks curious - though it raises questions orthogonal to what I was originally interested in. My instinct makes it hard for me to accept that knowledge about an equation modulo-N tells you "nothing" about it 'in general' - though I do recognise that any relationship might be perilously complicated. – aSteve Apr 28 '13 at 11:35
  • @aSteve Certain polynomials have integral solutions if and only if they have real solutions in $\mathbb{R}$, and solutions modulo $p^n$ for every prime $p$ and every $n>0$. Such polynomials are said to satisfy the Hasse principle. It is a natural question to ask when you can piece together modular solutions (local solutions) to give you an integer solution (global solution), but as you have quite rightly said yourself, the relationship is in general quite complicated! I do feel that I've digressed from your original point, so I do apologise. – Warren Moore Apr 28 '13 at 11:51
  • @aSteve Also, you might find this link useful. It talks through some of the basic ideas behind trying to solve Diophantine equations, including examples using modular arithmetic and quadratic residues to prove no solutions exist. – Warren Moore Apr 28 '13 at 11:59
  • Ta again... lots of reading for me to do. This might take some time. :) The www.mathdb.org site looks as if it might be generally useful - if only I could read Chinese (I assume). – aSteve Apr 28 '13 at 15:26