2022JJMO5番の解説

$a_i\equiv 3,5(\mathrm{mod}8)$と仮定して矛盾を導く. このとき,$p\equiv 3,5(\mathrm{mod}8)$を満たす$a_i$の素因数$p$が存在する. この時,$Y\equiv 2\cdot 4^{\lfloor \frac{k}{2}\rfloor }(\mathrm{mod}p)$なので,平方剰余の第2補充則に矛盾する.
$a_i\equiv 0(\mathrm{mod}3)$のときは上の議論で$p=3$とすればよい.

主張は$a_i\equiv 0,1,2,4(\mathrm{mod}8)$と同値である.
$a_i\equiv 0,1,2,4(\mathrm{mod}8)$を$i=k$から順に示す.
$i=k$のときは$a_i=1$より自明. $i$のとき正しいとすると,$\lfloor \frac{a_{i-1}}{2}\rfloor =a_i$より,$a_{i-1}\equiv 0,1,2,3,4,5(\mathrm{mod}8)$. これと補題1をあわせれば$i-1$でも正しいことがわかる.

$c_i$は$0=b_i=b_{i-1}=\cdots =b_{i-j+1}$を満たす最大の$j$であることに注意せよ.
主張の前半は補題2より,$b_i$と$b_{i+1}$のどちらかは$0$であることから従う.
後半は$b_i=b_{i+1}=0$もしくは$b_{i+1}=b_{i+2}=0$のときには正しく,補題2より残るパターンは$b_i=b_{i+2}=0,b_{i+1}=1$のみである. このとき再び補題2を$i-1$に適用すれば$b_{i-1}=0$となり,$c_i\ge 2,c_{i+2}=1$となる.

$a_k=1$より$a_{k-1}=2,3$だが,補題2より$a_{k-1}=2$.
よって$a_{k-2}=4,5$だが補題2より$a_{k-2}=4$.
よって$a_{k-3}=8,9$だが補題2より$a_{k-3}=8$.
ゆえに$c_k=0,c_{k-1}=1,c_{k-2}=2,c_{k-3}=3$.

補題3,4から従う.