互除法により2つの数の最大公約数が求められること，および互除法を逆にたどることにより1次不定方程式の解が得られることを確認しています．どちらも整数を扱うときの基本事項です．使えるだけでなく，なぜか？という姿勢で問題に取りくむことも大切です．

(1)で余りの周期性を確認して(2)へと進んでいきます．余りについては合同式による表記が明快でしょう．

2進法→10進法→5進法の書き換えを行います．