We identify the children with the residues $\mod n$. It starts with turn $0$ when child $0 \mod n$ gets a candy. In turn $k$ the teacher gives a candy to the child $1+2+...+k =\frac{k(k+1)}{2} \mod n$. We are thus asked for what $n$ the map $\sigma :k \mapsto \frac{k(k+1)}{2} \mod n$ is surjective. If $p$ is an odd prime dividing $n$, we would need that $\sigma$ is surjective $\mod p$. But $\sigma \mod p$ only depends on the residue classes $\mod p$. By $\sigma(-1) \equiv \sigma(0) \mod p$ we get that it's not injective, thus not surjective. Thus $n$ is a power of $2$, $n=2^k$. We show that it works for all those $n$: We want $k$ with $\frac{k(k+1)}{2} \equiv a \mod 2^k \iff (2k+1)^2 \equiv 8a+1 \mod 2^{k+3}$ for all $a$. But it's well known that $\mod$ any power of two, exactly the residues $\equiv 1 \mod 8$ are those that are quadratic residues, thus we are done.

ZetaX wrote: We identify the children with the residues $\mod n$. But it's well known that $\mod$ any power of two, exactly the residues $\equiv 1 \mod 8$ are those that are quadratic residues, thus we are done. is there a better way to see this fact? (better than using an induction-like argument like the following sketch: Let $k = 2^n.$ For the roots of the quadratic residues, it suffices to check the squares of the odd integers up to $k/4-1$ (denote this set $L$), since $i^2 \equiv (k/2-i)^2$ and obviously $i^2 \equiv (-i)^2 \equiv (k/2+i)^2$, both of which follow from binomial expansion and using $k=2^n$. In fact, these must be exactly the set of residues $\equiv 1 \pmod 8)$ since there are $k/8$ of them. We just need to show that $L$ maps injectively and surjectively to the residues $\equiv 1 \pmod 8$. Now we induct by noting the symmetry of (2k)/2-i and i It's easy to check the base case. Suppose this is true for $k=2^n$. Then we need to check it's true for the odd integers up to $2k/4-1 = k/2-1$. But $(k/2-i)^2 \equiv i^2 +(2k)/2 \pmod {2k}$ since $k=2^n$ by definition. Thus we can extend this bijective map and the inductive step is done.

Induction is one way, another goes as follows: - Check that $x^2 \equiv 1 \mod 2^n$ has at most $4$ solutions. - Conclude that $x^2 \equiv a \mod 2^n$ has at most $4$ solutions. - Check that only the residues $\equiv 1 \mod 8$ can be quadratic residues. - Compare the last two using that there are $2^{n-1}$ possible residues to square.

Ahh that is much better. THanks!. I will write this for future reference: $x^2\equiv 1 \pmod{2^n}$ has at most 4 solutions: $x^2-1=(x+1)(x-1) \equiv 0 \pmod{2^n}$. so either one of the factors evenly divides 2^n or one exactly divides 2^(n-1) and the other is 2 mod 4. (I think this is easiest way to think about this?). So $x$ is $\pm 1, 2^{n-1} \pm 1$ $x^2 \equiv a$. If $a$ is a q.r., then $a=k^2$ and the solutions should be $\pm k , 2^{n-1} \pm k$, which is multiplying above by k (mod 2^(n-1)). Basically same reasoning. The resides mod 8 are 0,1, 4 There are $2^{n-1}$ odd numbers, and the first two points check that for every four odd numbers, there is at least one quadratic residue, while the third says exactly one/eight of the residues can be quadratic residue, so the odd quadratic residues are exactly those 1 mod 8