# Find the smallest positive integer which can be expressed as the sum of four positive squares and divides $2^n +15$

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$$.
• 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$. Commented Oct 7, 2019 at 19:46
• 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 Commented Oct 7, 2019 at 19:46