[數論] 網格點 (Lattice Point)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
LattE, A Short Lecture Series on Lattice Points https://www.math.ucdavis.edu/~latte/background.php
How to count lattice points on a line. http://math.stackexchange.com/questions/628117/how-to-count-lattice-points-on-a-line
Problem to Ponder: March 16, 2011 http://www.nctm.org/about/content.aspx?id=29768
#7: The Visible Grid Point Problem http://epicmath.org/2013/02/12/7-the-visible-grid-point-problem/

圖片來源 NCTM http://www.nctm.org

平面座標 $x,y$ 都是整數的點稱為網格點(Lattice point)或整點(Integral point)。若 $x$ 與 $y$ 互質，則稱該網格點為 reduced integral point。我們主要討論下面兩個問題：
一、一條線會通過多少網格點？
二、一個區域包含多少網格點？


一、一條線會通過多少網格點？

圖一

從圖一可以看出，綠色線段($(a,b)\rightarrow (c,d)$) 只有兩個端點是網格點；藍色線段($(a,b)\rightarrow (e,f)$)則有三個網格點。不失一般性，我們以 $(a,b)\rightarrow (c,d)$ 線段做說明。

證明：給定兩點 $(a,b)$、$(c,d)$ 連成直線，此直線上會有 gcd$(c-a,d-b)+1$ 個網格點。

<pf>

先寫出直線方程式為 $y-b=\left ( \frac{d-b}{c-a} \right )(x-a)$。因為等號左邊 $y-b$ 是整數，所以等號右邊的 $\left ( \frac{d-b}{c-a} \right )(x-a)$ 也須為整數。

我們令 $k=$gcd$(c-a,d-b)$，則 $c-a=k\cdot \alpha $，$d-b=k\cdot \beta $。則 $\left ( \frac{d-b}{c-a} \right )(x-a)$ 可改寫成 $\frac{\beta }{\alpha }(x-a)$，$\frac{\beta }{\alpha }(x-a)\in \mathbb{Z}$， $\alpha \mid (x-a)$。而 $a\leq x\leq c$，亦即 $0\leq (x-a)\leq (c-a)=k\cdot \alpha $，滿足此不等式的整數有 $k+1$ 個(解集合為 $\left \{ 0,1,2,\cdots ,k \right \}$)，因此證明了直線上會有 gcd$(c-a,d-b)+1$ 個網格點。

二、一個區域包含多少網格點？
這裡的「區域」有很多種類型：三角形、方形、多邊形、圓形等等。有興趣者可自行上網搜尋相關資料。