12th European Girls' Mathematical Olympiad (EGMO 2023)

Problem 5.
We are given a positive integer $s \ge 2$ . For each positive integer $k$ , we define its twist $k’$ as follows: write $k$ as $as+b$ , where $a, b$ are non-negative integers and $b < s$ , then $k’ = bs+a$ . For the positive integer $n$ , consider the infinite sequence $d_1, d_2, \dots$ where $d_1=n$ and $d_{i+1}$ is the twist of $d_i$ for each positive integer $i$ .
Prove that this sequence contains $1$ if and only if the remainder when $n$ is divided by $s^2-1$ is either $1$ or $s$ .

Solution
For any nonnegative integers $a$ and $b$ , we have $s(bs+a)=bs^2+as \equiv as+b \pmod{s^2-1}.$ If the sequence starting with $n$ results in $1$ after $m$ twists, we have $n \equiv sn' \equiv s^2n'' \equiv \cdots \equiv s^m \pmod{s^2-1}$ . The powers of $s$ cycle between $1$ and $s \pmod{s^2-1}$ , so $n$ is congruent to $1$ or $s$ .

Now, we show that if $n$ is congruent to $1$ or $s \pmod{s^2-1}$ , then the sequence must contain $1$ . For any integer $k=as+b$ (with nonnegative integers $a$ and $b<s$ ) greater than $s^2-1$ , notice that $a \ge s>b$ , so $k'=bs+a<k$ . Thus, this sequence must eventually reach a positive integer less than or equal to $s^2-1$ . Since $n$ is congruent to $1$ or $s \pmod{s^2-1}$ , this number must be either $1$ or $s$ . If the number is $s$ , then its twist is $1$ , so our sequence contains $1$ as desired.