A magician performs a trick with a deck of cards that are numbered from to . The magician prepares for the trick by putting the cards in an order of her choosing. Then she challenges a member of the audience to write an integer on a board. The magician turns over the cards one by one, in their pre-arranged order. Every time the magician turns over a card, the audience member multiplies the number on the board by , adds it to the number on the card, writes the result on the board, and erases the old number. The magician guarantees that, no matter which initial integer is chosen, the initial and final numbers will sum to .
Determine for which natural numbers the magician can perform the trick. You must both prove that the trick is possible for the numbers you claim, and prove that it is not possible for any other numbers.