n を 3 以上の整数とする. 円周上の n+1 個の点を, 円周を n+1 等分するようにとる.
これらの点に 0 から n までの数字を 1 つずつ番号付けする方法を考える. 2 つの番
号付けは, 一方が他方を回転して得られるとき, 同じ番号付けとみなす. 番号付けが

美しい

とは, a < b < c < d かつ a + d = b + cをみたすすべての番号の組 (a, b, c, d) について,
番号 a が付いた点と番号 d が付いた点を結ぶ弦と, 番号 b が付いた点と番号 c が付
いた点を結ぶ弦が交わらないことをいう.美しい番号付けの個数を M とし, x + y ≦ n かつ
x と y の最大公約数が 1 であるような正の整数の組 (x, y) の個数を N とする. このとき,
M = N + 1を示せ.

数学的帰納法でやったのですが行き詰りました。よろしくお願いします