格子点とGCD

問題

格子点2点を結ぶ線分上にある格子点は(端点を含めて)いくつありますか

答え

$gcd(|x_1-x_2|, |y_1-y_2|)+1$ 個です




原点(0, 0)と(a, b)を結ぶ線分を考えていいでしょう(a≧0, b≧0, a,bは整数)

もとの問題はむずかしすぎるので、解ける問題を解きます。a, bが互いに素だとします。a=a', b=b', a'⊥b'です。このとき、あきらかに求める格子点の数は原点と(a', b')の2つです。

a, bが互いに素ではないとします。g=gcd(a, b)としてa=ga', b=gb' (a'⊥b') とおきます。すると求める格子点は(0, 0), (a', b'), (2a', 2b'), ..., (ga', gb')のg+1個です。




これが解けなかったので書きました。