MATHEMATICAL OLYMPIAD ARCHIVE

EGMO 2023
問題 5

DIFFICULTY1

PROBLEM WORKSPACE

ヒント

PUBLIC

ヒント 1

$d_{i+1}$ を $d_i,s$ で表しましょう．

略解を表示

$d_i=as+b ~ (a\geq 0,0\leq b\lt s)$ であるとき， $a=\lfloor d_i/s\rfloor, b=d_i-s\lfloor d_i/s\rfloor$ が成り立つので

d_{i+1}=s\left(d_i-s\left\lfloor \dfrac{d_i}{s}\right\rfloor\right)-\left\lfloor \dfrac{d_i}{s}\right\rfloor\equiv sd_i\pmod{s^2-1}

が成り立つので， $d_1,d_2,\ldots$ のいずれかを $s^2-1$ で割ったあまりが $1$ であることは $n,sn$ のいずれかを $s^2-1$ で割ったあまりが $1$ であることと同値であり，これは $n\equiv 1,s\pmod{s^2-1}$ と言い換えられる．