\(h_1=w_1=1, h_2=w_2=N\) の場合に \(\gcd\) をどう求めれば良いかを導く過程の一例を示します。

高校数学の整数周りで扱われる定理として次のようなものがあります。

• 正整数 \(n\) に対し、\(n\) と \(n+1\) は互いに素

これを一般化すると、次のようになります。

• 正整数 \(n,k\) に対し、\(n\) と \(n+k\) の最大公約数は \(k\) の約数

このことを考えると、長方形範囲内の \(\gcd\) は少なくとも以下のすべてを満たすといえます。

• \(A_1+B_1\) の約数である。
• \(i=1,2,\ldots,N-1\) すべてに対し、\(A_{i+1}-A_i\) の約数である。( マス \((i,j)\) とマス \((i+1,j)\) の整数を考え、上の定理に対し \(k=A_{i+1}-A_i\) とすることでこの条件が導けます)
• \(i=1,2,\ldots,N-1\) すべてに対し、\(B_{i+1}-B_i\) の約数である。

逆に、これらの条件を満たす整数は長方形範囲内の整数すべての約数となることが確認できるため、\(A_1+B_1, A_{i+1}-A_i\, (1 \leq i \leq N-1),B_{i+1}-B_i \,(1 \leq i \leq N-1)\) の \(\gcd\) が長方形範囲内の整数全ての \(\gcd\) になると言えます。