今回は正方形を並べてできる長方形の対角線は何個の正方形を切るか?という問題について考えてみたいと思います。

まず、縦と横の最大公約数が1のときから考えてみます。このとき、対角線は格子点を通りません。
説明を簡単にするために、対角線で切られる正方形を左と下に移動させてL型を作ります。



着目すべきは、縦と横の最大公約数が1のとき、L型が1つできるということです。

結論

縦と横の最大公約数が1のとき

対角線で切られる正方形 = 縦 + 横 - 1


つぎに、縦と横の最大公約数が1ではないときを考えてみます。
このとき、対角線は格子点を通るので、そこで区切ってL型を作ります。



縦と横の最大公約数が1ではないとき、L型が最大公約数分できることになります。

結論

縦と横の最大公約数が1ではないとき

対角線で切られる正方形 = 縦 + 横 - 縦と横の最大公約数

[←戻る]