Prove that for any $n \in \mathbb{Z}^+$ the equation $x^2+15y^2=4^n$ has at least $n$ non-negative integer solutions.

I tried to solve it by mathematical induction.

When $n=1$ we can easily find a solution $(2,0)$.

Let $(x_k, y_k)$ be a solution when $n=k$, we have $(x_{k+1}, y_{k+1}) = (2x_k, 2y_k)$ which is available when $n=k+1$.

Therefore, when $n=k+1$ we get $k$ solutions, if we can find another solution which is different from the other $k$ solutions, the proof is done.

I found that the solutions in $n=k+1$ which are generated from $n=k$ are always even, so I try to find an odd solution to make it different.

I suppose that the odd solution can exist when $n\geq 2$. For example, $(x_2,y_2)=(1,1)$, $(x_3,y_3)=(7,1)$, $(x_4,y_4)=(11,3)$, $(x_5,y_5)=(17,7)$ and so on.

I tried to figure out the relation between $n$ and $y_n$, and got an answer on OEIS:A106853, a strange sequence for me.

And I don't know how to do next. Could you help me?

What's more, I wonder whether the number of solutions is exactly $n$.

  • $\begingroup$ Where did you find this problem? :) $\endgroup$ – Sawarnik Mar 8 '15 at 9:02
  • $\begingroup$ Any questions/thoughts about my answer, Jingyi? $\endgroup$ – Gerry Myerson Mar 9 '15 at 12:08

As OP notes, it suffices to prove that there is an odd solution.

It is not hard to show that if $x=a$, $y=b$ is a solution to $x^2+15y^2=4^n$ with $x$ and $y$ odd and $x-y$ a multiple of $4$, then $x=(a-15b)/2$, $y=(a+b)/2$ is a solution to $x^2+15y^2=4^{n+1}$ with $x$ and $y$ odd and $x-y$ a multiple of $4$.

Now notice that $x=1$, $y=1$ is a solution to $x^2+15y^2=4$ with $x$ and $y$ odd and $x-y$ a multiple of $4$, and we have a proof by induction that there's always an odd solution.

[Note: the formula will sometimes give you negative values for $x$ and/or $y$, but if there's a solution in negative odd integers then there's one in positive odd integers as well, as you can replace any negative number by its absolute value.]


We need $n\ge2$

Use Generalized Brahmagupta–Fibonacci identity, $$(ac\pm mbd)^2+m(ad\mp bc)^2=(a^2+mb^2)(c^2+md^2)$$

Here $m=15$

Use induction:

Set $a=b=1$ $$(c\pm15d)^2+15(d\mp c)^2=(1^2+15\cdot1^2)(c^2+15d^2)$$

Now the base cases : $4^2=1^2+15\cdot1^2(i),4^2+15\cdot0^2(ii)$


$4^3=2^2(4^2)=2^2(1^2+15\cdot1^2)=2^2+15\cdot2^2(i)$ and $4^3=8^2(ii)=7^2+15\cdot1^2(iii)$

  • $\begingroup$ Sorry, I don't understand. It seems that this method can only generate even solutions? I have tried induction and $(x_{k+1}, y_{k+1}) = (2x_k, 2y_k)$. $\endgroup$ – J. XU Mar 8 '15 at 6:24
  • $\begingroup$ @JingyiXu, You already have $2^2+2\cdot15=4^3$ $\endgroup$ – lab bhattacharjee Mar 8 '15 at 6:28
  • $\begingroup$ But, for $4^3$ I need $3$ solutions. $\endgroup$ – J. XU Mar 8 '15 at 6:31
  • $\begingroup$ @JingyiXu, Updated the solution $\endgroup$ – lab bhattacharjee Mar 9 '15 at 13:53

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.