Problem 5.
We are given a positive integer . For each positive integer , we define its twist as follows: write as , where are non-negative integers and , then . For the positive integer , consider the infinite sequence where and is the twist of for each positive integer . Prove that this sequence contains if and only if the remainder when is divided by is either or . Solution
For any nonnegative integers and , we have If the sequence starting with results in after twists, we have . The powers of cycle between and , so is congruent to or . Now, we show that if is congruent to or , then the sequence must contain . For any integer (with nonnegative integers and ) greater than , notice that , so . Thus, this sequence must eventually reach a positive integer less than or equal to . Since is congruent to or , this number must be either or . If the number is , then its twist is , so our sequence contains as desired. |