7
$\begingroup$

I saw this problem recently and found an elegant solution to it, and was curious to see if anybody would think of something else. Nice solutions to nice problems are fun to see!

Problem: Prove that, for all non-negative integers $k$, there exist integers $a$, $b$ such that $a^2+b^2=5^k$.

Bonus: Prove that $(a,b)=1$.

$\endgroup$
8
$\begingroup$

At heart, $a^2+b^2$ can be seen as the square if the distance of $a+bi$ to $0$ in the complex numbers. And if $w,z$ are complex numbers, then $|wz|=|w|\cdot |z|$, so $|wz|^2 = |w|^2\cdot |z|^2$.

That means that if $a+bi = (2+i)^n$ then $a^2+b^2 = |a+bi|^2 = \left(|2+i|^2\right)^n = 5^n$.

This approach gets you $a,b$ relatively prime and non-zero.

The other way is just to take the case of $n=2m$ even first:

$$5^{2m} = \left(5^m\right)^2 +0^2$$

For $n=2m+1$ odd, you get:

$$5^{2m+1} = \left(2\cdot 5^m\right)^2 + \left(1\cdot 5^m\right)^2$$

There is another way, closely associated with the complex answer, using determinants of matrices of the form:

$$\begin{pmatrix}x&y\\-y&x\end{pmatrix}$$

Such matrices are closed under multiplication, and the determinant is $x^2+y^2$.

Since the product of determinants is the determinant of the product, you only need to find a solution of $x^2+y^2=5$ and raise that matrix to the $n$th power.

This gives you exactly the same answer(s) as my first approach, since the ring of matrices of this form is "isomorphic" to the complex numbers. But the determinant is in some ways an "algebraic" answer, compared to the distance property.

$\endgroup$
  • $\begingroup$ Yes, this is essentially the approach I used to obtain $(a,b)=1$. $\endgroup$ – Ahaan S. Rungta Aug 20 '13 at 18:11
  • $\begingroup$ Which? I've listed three approaches. :) $\endgroup$ – Thomas Andrews Aug 20 '13 at 18:11
  • $\begingroup$ Oh, derp. I didn't finish reading when I posted that. The first one, where you say "this approach gets you $a,b$ relatively prime and non-zero". My approach was more along the lines of the Binomial theorem, but your approach boils down to the same thing. $\endgroup$ – Ahaan S. Rungta Aug 20 '13 at 18:12
19
$\begingroup$

HINT:

Using induction:

$5^1=2^2+1^2$

Let $5^k=a^2+b^2$

$5^{k+1}=(a^2+b^2)(2^2+1^2)=(2a\pm b)^2+(2b\mp a)^2$ (Brahmagupta–Fibonacci identity)

This invites a little generalization: as we which numbers are expressible as the sum of two squares.

$\endgroup$
  • $\begingroup$ Yes, this is what I did. I posted the question, though for people to post their full solutions, so as to discuss, not because I wanted a hint. I solved this problem already. :) $\endgroup$ – Ahaan S. Rungta Aug 20 '13 at 17:58
  • $\begingroup$ @Ahaan You should have written your solution. $\endgroup$ – Git Gud Aug 20 '13 at 17:59
  • $\begingroup$ It's essentially the same as Lab's solution. $\endgroup$ – Ahaan S. Rungta Aug 20 '13 at 17:59
  • $\begingroup$ The most simplest! $\endgroup$ – thesagniksaha Jun 24 '14 at 12:16
3
$\begingroup$

Take the ring $\mathbb{Z}[i]$ and the norm function $$ N(x+iy) = x^2 + y^2 $$ Then $N(z_1z_2) = N(z_1)N(z_2)$. So just take $$ z = (2+i)^k = a+bi $$ Then $a^2+b^2 = N(z) = N(2+i)^k = 5^k$

$\endgroup$
  • $\begingroup$ Agh! I was posted this as an answer when I got the update that you posted this. Yes, this is exactly what I did. It's the same idea as Lab's solution but your solution mirrors mine. I've added a bonus to the OP. $\endgroup$ – Ahaan S. Rungta Aug 20 '13 at 18:03

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.