A positive integer $n$ is called good if for all positive integers $a$ which can be written as $a=n^2 \sum_{i=1}^n {x_i}^2$ where $x_1, x_2, \ldots ,x_n$ are integers, it is possible to express $a$ as $a=\sum_{i=1}^n {y_i}^2$ where $y_1, y_2, \ldots, y_n$ are integers with none of them is divisible by $n.$ Find all good numbers.
Problem
Source: Turkish TST 2012 Problem 5
Tags: number theory proposed, number theory
28.03.2012 21:57
I'll prove that for all positive integers $n$ except $1,2,4$ we can find such a sequence. $\sum_{i=1}^{n} {x_i} = X $ then it is easy to see that $y_i=2X-nx_i$ holds condition. If $n$ doesn't divide $2X$ it is done. If $n$ divides $2X$ : i) at least one of them not divisible by $n$ (w.l.o.g. $x_1$) then take $X$ as $-x_1+x_2+x_3 ... +x_n$ it is still holds the condition and $n$ does not divide anyone of $y_i$.(we now that $n$ does not divide 4) ii)if all of them divisible by $n$ then we can find positive $w_i$ such that $a=\sum_{i=1}^{n} n^{2k}{w_i}^2$ and at least one of them not divisible by $n$. Then from first case we can find such $z_i$'s that $a=\sum_{i=1}^{n} n^{2k-2}{z_i}^2$ applying it $k$ times we find $y_i$ s not divisible by $n$. for $n=1$ and $n=2 $ there's not $good$ positive integer. For $n=4$, $a=64$ is a counter-example.(it may be false but it's not hard to find a counter example)
09.04.2012 15:16
emregirgin35 wrote: i) at least one of them not divisible by $n$ (w.l.o.g. $x_1$) then take $X$ as $-x_1+x_2+x_3 ... +x_n$ it is still holds the condition and $n$ does not divide anyone of $y_i$.(we now that $n$ does not divide 4) if $x_1 = n/2$ then $X$ can divide by n