>>285
ユークリッドの互除法を使えばよい