Find the smallest positive integer which can be expressed as the sum of four positive squares, not necessarily different, and divides $2^n + 15$ for some positive integer $n$.

If you let $K$ be that integer you have, $K \equiv 1 \pmod 2$. And if $n \ge 4$ then $16$ divides $K + 1$ but I don't know what to next, hints and solutions would be appreciated.

Taken from the 2009 International World Youth Mathematics Intercity Competition (IWYMIC).


The smallest odd natural numbers that are sums of four positive squares are $7=4+1+1+1$ and $13=4+4+4+1$. It is easy to show that $2^n+15$ is never divisible by $7$. But $2^7+15=143$ is divisible by $13$.

  • $\begingroup$ Modulo $7$ the residue class of $2$ generates the subgroup of quadratic residues, and $-15$ is not in that subgroup. But $2$ is a primitive root modulo $13$. $\endgroup$ – Jyrki Lahtonen Oct 7 at 19:46
  • 2
    $\begingroup$ I was going to point out that $23 \equiv 7 \pmod 8$ could not be the sum of three squares, therefore must be the sum of four nonzero squares. Also $23 = 8 + 15$ says we could use 23 dividing itself. So, no larger $\endgroup$ – Will Jagy Oct 7 at 19:46

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.