Problem 4
During a break, n children sit in a circle. A teacher chooses one child and gives a candy, skips the next child and gives one to the following child, then skips 2 children, then 3, and so on. For which n will every child eventually receive at least one candy?
Step 2 of 4: Exclude an odd factor
Detailed analysis
If n has an odd factor m, then m divides x(x+1) exactly when x is 0 or m-1 modulo m. Hence f has two equal values modulo m. The Chinese remainder theorem lifts this failure of injectivity to modulo n, so not every child can be visited.