This question is an exact duplicate of:
This is a number theory exercise I've been stuck on for a while. It was set during a lecture I attended once. It goes something like this . . .
Suppose there's a full circular prison with 100 cells and one prison guard who hates his job. He gets drunk one night and decides to play a game while the prisoners were asleep. He walks the circular prison and, the first time, he opens every cell; the second time, he closes every even numbered cell; the third time, he touches every third cell, and if that cell is open, he closes it, and he opens it otherwise; the fourth time, he touches every fourth cell, and if that cell is open, he closes it, and he opens it otherwise; and so on until his hundredth time around the prison. He then falls asleep.
By the morning, after the prison guard's hundredth lap, every prisoner in an open cell escapes.
Which prisoners escape?
I've thought of trying a modified use of the Sieve of Eratosthenes but there's got to be a more elegant, less brute-force solution.