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$.
Problem
Source: EGMO 2023/5
Tags: EGMO, EGMO 2023, number theory
17.04.2023 01:04
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.
17.04.2023 15:09
17.04.2023 15:15
Same solution here as well.
17.04.2023 23:03
First note that $$s(bs+a)\equiv bs^2+as \equiv as+b \pmod{s^2-1},$$so if the sequence contains $1$ then the starting term must be $1$ or $s$ modulo $s^2-1$, since $s^2 \equiv 1 \pmod{s^2-1}$. On the other hand, it is not hard to see that if $d_i \geq s^2$, then $d_{i+1}<d_i$, so eventually any sequence will become a $2$-digit base $s$ number $\overline{ab}_s$ (where $a$ and $b$ depend on $n$). Thus if $n$ is $1$ or $s$ $\pmod{s^2-1}$, so is $\overline{ab}_s$, which implies that it's either $1$ or $s$. In the former case, we're done, and in the latter case the next term in the sequence is $1$. $\blacksquare$
14.05.2023 21:40
Observe that \[s(bs+a)=bs^2+sa \equiv as+b \pmod{s^2-1},\]since $s^2 \equiv 1 \pmod{s^2-1}.$ Then, if the sequence terminates after $k$ moves, we know that $n \equiv sn' \equiv s^2n'' \equiv \dots \equiv s^k \pmod{s^2-1}.$ Thus all $d_i$ are powers of $s,$ which alternate between $1$ and $s$ modulo $s^2-1.$ Now we prove that if $n \equiv 1, s \pmod{s^2-1}$ than $1$ must be included in the sequence. Note that for any $k=as+b>s^2-1,$ we have $a \geq s>b.$ So $k'<k.$ Thus, $d_i$ eventually reaches a point where some number in this sequence is less than $s^2-1.$ From the restriction we imposed on $n,$ this forces this such number to be either $1$ or $s.$ But observe the twist of $s$ is $1,$ so the sequence eventually terminates at $1,$ as desired.
07.06.2023 17:29
We first prove the following key lemma: Lemma: If $d_1=n$, then the sequence $\pmod{s^2-1}$ is precisely $k, ks, ks^2, ks^3, \dots$ Proof: Unconditionally, $$as+b\equiv k \pmod{s^2-1}\implies ks\equiv s(as+b)\equiv bs+as^2\equiv bs+a \pmod{s^2-1}$$so the conclusion follows. $\square$ Now, we prove the two parts. Claim: If the sequence reaches $1$ starting from $n$, then $n$ must be $1$ or $s$ $\pmod{s^2-1}$. Proof: If the sequence reaches 1, then it must reach 1 $\pmod{s^2-1}$, which is strong enough: our lemma implies that $$ns^{k}\equiv 1 \pmod{s^2-1} \text{ for some } n\geq 1,$$but since $s^2\equiv 1 \pmod{s^2-1}$, the only possibilities for $n \pmod{s^2-1}$ are those claimed. $\blacksquare$ Claim: If $n$ is $1$ or $s$ $\pmod{s^2-1}$, then we reach 1. Proof: First, note that the sequence is strictly decreasing whenever $$bs+a<as+b\Longleftrightarrow b<a,$$and it is lower bounded by 1. Now let index $i$ be such that $d_{i+1}>d_i=as+b$, which must exist. We then have $$d_i=as+b\leq bs+b<(s-1)s+s=s^2.$$By our lemma, $d_i \equiv 1$ or $s$ $\pmod{s^2-1}$. However, this is possible only if $d_i=1$ or $d_i=s$. In both cases we have either reached 1, or will reach 1 in the next move. $\blacksquare$
21.01.2024 13:01
First direction: Claim 1: the sequence is equal to $d_i \equiv sd_{i+1} \pmod{s^2-1}$. $$as+b\equiv k \pmod{s^2-1}\implies ks\equiv s(as+b)\equiv bs+as^2\equiv bs+a \pmod{s^2-1}$$as desired. But this means that if the sequence $(d_i)$ contains a $1 $ after $m$ twist, then we have that $d_1 \equiv sd_{1} \equiv s^2d_{2} \equiv \cdots \equiv s^m \pmod{s^2-1}$, in other words all the terms of the sequence are powers of $s \pmod{s^2-1}$, Which implies $d_1 \equiv 1,s \pmod{s^2-1}$. Second direction: Claim 2: For $k>s^2-1$ then $k>k'$. Let $k=as+b$ then $k'=bs+a$, since $k>s^2-1$ then $a \geq s>b$ implying $k>k'$ as desired. Now for some $k=as+b$. We have that $k>s^2-1$, then by claim 2 we have that the sequence will reach a number less than $s^2-1$. Since $n \equiv 1,s \pmod s^2-1$ the it must either reach $1 $ or $s$ in both cases we are done as the twist of $s$ is $1$.