当時教科書の説明が分かりにくくて例題すら解けなかったので別の解法を。
互除法をプログラミングで組むときに使うやつです。
もちろん正規法ではないので これで解くときは先生に聞いてください。