A prime number $p$ is a moderate number if for every $2$ positive integers $k > 1$ and $m$, there exists k positive integers $n_1, n_2, ..., n_k $ such that \[ n_1^2+n_2^2+ ... +n_k^2=p^{k+m} \] If $q$ is the smallest moderate number, then determine the smallest prime $r$ which is not moderate and $q < r$.
Problem
Source: Indonesian IMO TST 2011
Tags: modular arithmetic, induction, number theory unsolved, number theory
14.07.2011 13:26
The prime number $p = 2$ is immoderate since for $k=2$ and $m=2$ the number $16 = 2^{2+2}$ cannot be expressed as sum of two non-zero squares. So in the sequel we will assume $p>2$. To have the "moderation" condition for $k=2$ and $m=1$ we need to be able to represent $p^3 = a^2 + b^2$. If p divides both $a$ and $b$, that means $p = (a/p)^2 + (b/p)^2$, thus $p\equiv 1 \pmod{4}$. If not, say $p\nmid b$, then $(ab^{-1})^2 \equiv -1 \pmod{p}$, and again that implies $p\equiv 1 \pmod{4}$, so numbers of the form $p\equiv 3 \pmod{4}$ are immoderate. Finally, for a prime $p\equiv 1 \pmod{4}$, it is known it can be represented as $p=a^2 + b^2$ (with $a\neq b$). Moreover, products of sums of two non-zero squares are sums of two non-zero squares, by the known $(x^2+y^2)(z^2+t^2) = (xz \pm yt)^2 + (xt \mp yz)^2$ identity (the reason this is not true for $2$ is because $2 = 1+1$, the sum of two equal squares), so $p^{2+m}$ is sum of two squares for any $m$. In particular we have $p^2 = (a^2+b^2)^2 = (a^2-b^2)^2 + (2ab)^2 = A^2 + B^2$. Lemma. For any $k\geq 1$ the number $p^k$ can be represented as a sum of $k$ non-zero squares. Proof. We have $p=a^2+b^2$, $p^2 = A^2 + B^2$. Now, proceeding by induction for $k>2$, for $\ell \geq 1$, we have $p^{2\ell + 1} =$ $ p\cdot p^{2\ell} =$ $ (a^2+b^2)p^{2\ell} =$ $ (ap^{\ell})^2 + \sum_{j=1}^{2\ell} (ba_j)^2$, a sum of $2\ell + 1$ non-zero squares, and we have $p^{2\ell + 2} =$ $ p^2\cdot p^{2\ell} =$ $ p^2\sum_{j=1}^{2\ell} a_j^2 =$ $ \sum_{j=1}^{2\ell-2} (pa_j)^2 + (Aa_{2\ell-1})^2+(Aa_{2\ell})^2 + (Ba_{2\ell-1})^2 + (Ba_{2\ell})^2$, a sum of $2\ell + 2$ non-zero squares.$\ \square$ Now we can take care of $k$ for any $m>0$, by doing induction on $k$ (the base case $k=2$ having been dealt with in the above). For any $m\geq 1$, from $\sum_{j=1}^k n_j^2 = p^{k+(m-1)}$ (either for $m-1 \geq 1$ by the induction hypothesis, or for $m-1=0$ by the above Lemma) we get $p^{(k+1)+m} =$ $ p^2\cdot p^{k + (m-1)} =$ $ p^2\sum_{j=1}^{k-1} n_j^2 + p^2n_k^2 =$ $ \sum_{j=1}^{k-1} (pn_j)^2 + (An_k)^2 + (Bn_k)^2$, the sum of $k+1$ non-zero squares. Therefore we fully characterized the moderate and immoderate primes. Thus $q = 5$ is the least moderate prime, and $r = 7$ is the least immoderate prime such that $q<r$.