# First problems from text on number theory

Express $635,318,657$ as sum of two fourth powers in two different ways. It is the smallest number with this property?

and

$1105$ can be expressed as the sum of two squares in 4 different ways. Find them.

The solution to these problems wouldn't be of any help but how to think about such problems and what tools to use?

Source: "Elementary Numebr Theory with applications" by Thomas Koshy

-
Please do not combine unrelated questions into one post. – Zev Chonoles Jun 25 '11 at 5:53
@Zev I felt the questions had a common theme, and I am not looking for solutions (which I can find by brute forcing I guess) but ways to approach them. (They were first exercises of an elementary number theory text) If you think these can qualify as three seperate questions, without appearing as spam, I will do so. – kuch nahi Jun 25 '11 at 6:00
@kuch nani: I think the question about Kapreckar numbers can go on its own, and the other two could go together in another post. Also, I would recommend that you explain where these questions are coming from. – Zev Chonoles Jun 25 '11 at 6:04
@Zev New question here – kuch nahi Jun 25 '11 at 6:15
@kuch nahi: For the sum of $2$ fourth powers, there is no pleasant general theory. But the candidates cannot be very large, and congruential considerations can be used to rule out most of them. – André Nicolas Jun 25 '11 at 7:09

Question $3$ is the only one that is connected to long-established theory.

Note that $1105=5 \times 13\times 17$, and that each of $5$, $13$, and $17$ is easily seen to be a sum of two squares.

By an identity that is a special case of Brahmagupta's Identity, the product of two sums of two squares is itself a sum of two squares. The identity is $$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2=(ad-bc)^2 +(ac+bd)^2.$$

You can use the above identity to generate the representations of $1105$ as a sum of squares. Do it!

The identity is interesting in many ways, and is less "magic" than it looks. Let $p+qi$ be a complex number. Then $|p+qi|^2$, the square of the norm of $a+bi$, is precisely $p^2+q^2$. The Brahmagupta Identity then can be interpreted as saying that $$|(a+bi)(c+di)|^2 =|a+bi|^2|c+di|^2$$ (the square of the norm of a product is the product of the squares of the norms, or, taking square roots, the norm of a product is the product of the norms.)

Expressing $1105$ as a sum of two squares can be thought of as finding all the ways to express $$(2-i)(2+i)(3-2i)(3+2i)(4-i)(4+i)$$ in the form $(a-bi)(a+bi)$, where $a$ and $b$ are integers.

There is a quite thoroughly worked out theory of sums of two squares, that you can find in most books on Elementary Number Theory. For example, a prime of the form $4k+1$ can be expressed in essentially one way as a sum of two squares. This is a result of Fermat. The proof, though "elementary", is not all that easy.

-
For the sum of two fourth powers, express as the sum of two squares and then check whether these squares are in fact fourth powers. – Mark Bennet Jun 25 '11 at 16:47
@Mark, how do you propose to find those two squares? Is there a way that takes less computation than the alternative method where you just try directly to express the number as a sum of two 4th powers? – Gerry Myerson Jun 26 '11 at 1:17
Maybe the identity of Jacobsthal is helpful in finding the two integers? Of course this could be proposed as a hopeless way of finding the representations, which might just prove the theorem, not all that easy indeed. See here for a special case: docs.google.com/document/d/… – awllower Aug 21 '11 at 8:13
@awllower: There are good algorithms for expressing a prime of form $4k+1$ as a sum of two squares. Any thorough book on Computational Number Theory will have information. One way I know uses continued fraction expansion of $\sqrt{p}$. There are others. – André Nicolas Aug 21 '11 at 8:40
@André Nicolas: Thanks for your information. Indeed I am almost completely unfamiliar with the computational number-theory; I thought I might well learn it later, but it appears attractive to me now. – awllower Aug 21 '11 at 8:58

Nowadays, the best (anyway, most efficient) way to solve the first problem is to type the number into Google to see what turns up. Alternatively, type it into the search window at the Online Encyclopedia of Integer Sequences, and it will lead you to http://oeis.org/A018786 which has some useful citations.

-