[數論] 網格點 (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$ 個網格點。

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

[數論] 形數(Figurate Number) 與級數

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
Wikipedia http://en.wikipedia.org/wiki/Figurate_number
Wolfram MathWorld http://mathworld.wolfram.com/FigurateNumber.html

這是一篇與圖形息息相關的文章。

三角形數
參考：昌爸工作坊 http://www.mathland.idv.tw/fun/triangle.htm

第一層$1$個點、第二層$2$個點、第三層$3$個點，$\cdots$，可知第$n$層會有$n$個點。
數列 $t_1=1$，$t_2=1+2$，$t_3=1+2+3$，$\cdots$，$t_n=1+2+3+\cdots +n=\frac{n(n+1)}{2}$。

正方形數
第一層$1$個點、第二層$3$個點、第三層$5$個點，$\cdots$，可知第$n$層會有$2n-1$個點。
數列 $s_1=1$，$s_2=2^2=4$，$s_3=3^2=9$，$\cdots$，$s_n=n^2$。

推廣至正多邊形數
對於正 $k$ 邊形而言，每多一層，會增加 $k$ 邊的範圍。扣除最旁邊的兩個邊，每多一層增加的點會坐落在其他 $k-2$ 的邊上。

如果只看這 $k-2$ 個邊的其中一邊，第 $n$ 層時，這條邊上會有 $n$ 個點。如果直接算第 $n$ 層有 $(k-2)n$ 個點的話，那麼就會多算，因為邊上的端點(也就是頂點)會被重複計算。扣掉重複計算的部分才是真正的數目，重複計算的端點有 $(k-2)-1=k-3$ 個，也就是有效邊數($k-2$)減$1$，因此第 $n$ 層有 $(k-2)n-(k-3)$ 個點。

計算形數的和
對於正 $k$ 邊形，如何計算 $t_1+t_2+\cdots +t_n$ 的和？
根據上面的結論，相當於計算 $p_n(k)=\sum_{i=1}^{n}\left [ (k-2)i+(k-3) \right ]=\frac{n[n(k-2)-k+4]}{2}=\binom{k+n-1}{n}$。

77. 試證：兩個相鄰的三角形數之和是一個平方數。

<sol> 設兩三角形數為 $t_n=\frac{n(n+1)}{2}$ 和 $t_{n+1}=\frac{n+1(n+2)}{2}$。則

$t_n+t_{n+1}=\frac{n(n+1)}{2}+\frac{(n+1)(n+2)}{2}=\frac{1}{2}\left [ (n^2+n)+(n^2+3n+2) \right ]=\frac{1}{2}\left [ 2n^2+4n+2 \right ]=(n+1)^2$.

78. 試求前 $n$ 個四邊形數(即平方數)的和。
<sol> 可參考此網頁：https://proofwiki.org/wiki/Sum_of_Sequence_of_Squares，裡面提供了五種證明。個人比較喜歡 Proof 4，下面稍微介紹一下，欲見完整證明請點網頁連結。

上圖是 $1^2+2^2+3^2+4^2$ 的圖示。如果以行的角度來看，可看作 $\sum_{k=1}^{4}k^2=\sum_{k=1}^{4}k+\sum_{k=2}^{4}k+\sum_{k=3}^{4}k+\sum_{k=4}^{4}k$.

若推廣至 $n$ 層，亦即 $1^2+2^2+3^2+\cdots +n^2$，仿照上式，我們可以寫出

$\sum_{k=1}^{n}k^2=\sum_{k=1}^{n}k+\sum_{k=2}^{n}k+\sum_{k=3}^{n}k+\cdots +\sum_{k=n}^{n}k=\sum_{k=1}^{n}\left ( \sum_{j=k}^{n}j \right )$.

78-1. 試求$S_n=1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n(n+1)$。
<sol> $S_n=\frac{1}{2}\left ( 1\cdot 2+2\cdot 3+\cdots +(n-1)n \right )$
              $=1\cdot (1+1)+2\cdot (2+1)+3\cdot (3+1)+\cdots +n\cdot (n+1)$
              $=(1^2+1)+(2^2+2)+(3^2+3)+\cdots +(n^2+n)$
              $=(1^2+2^2+3^2+\cdots +n^2)+(1+2+3+\cdots +n)$
              $=\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}$
              $=\frac{n(n+1)(n+2)}{3}$.

79. 試求前 $n$ 個三角形數的和。 圖解：http://www.mathland.idv.tw/fun/seriesadd.htm
81. 設 $p_n(k)$ 為第 $n$ 個 $k$ 邊形數，試證：$p_n(k)=p_n(k-1)+p_{n-1}(3)$。
<sol> $p_n(k-1)+p_{n-1}(3)=[(k-3)n-(k-4)]+[(3-2)(n-1)-(3-3)]$
                                          $=(k-3)n-k+4+n-1=(k-2)n-(k-3)$
                                          $=p_n(k)$.

82. 試證：任何三角形數的個位數字不會是 $2,4,7,9$。
<sol> 第 $n$ 個三角形數 $=\frac{n(n+1)}{2}$。依序取 $n=0,1,2,\cdots ,9$ 代入觀察後即得所求。

83. 試證：(1) 任何四邊形數的個位數不會是 $2,3,7,8$。 (2) 任何平方數的最後兩位數字之積必為偶數。
85. 試求如下平方數的和：(1) $1^2-2^2+3^2-4^2+\cdots +(-1)^{n+1}n^2$；(2)$1^2+3^2+5^2+\cdots +(2m+1)^2$。
<sol>
(1) 當 $n$ 是偶數時，令 $n=2m$。
    $1^2-2^2+\cdots +(n-1)^2-n^2=[1^2+3^3+\cdots +(n-1)^2]-[2^2+4^2+\cdots +n^2]$
                                                     $=\sum_{i=1}^{m}(2m-1)^2-\sum_{i=1}^{m}(2m)^2$
                                                     $=\sum_{i=1}^{m}[(2m-1)^2-(2m)^2]$
                                                     $=\sum_{i=1}^{m}(-4m+1)$
                                                     $=-4\cdot \frac{m(m+1)}{2}+m$
                                                     $=-4\cdot \frac{n(n+1)}{2}$  (since $m=\frac{n}{2}$)

     當 $n$ 是奇數時，令 $n=2m+1$，所求之和為 $-4\cdot \frac{n(n+1)}{2}+(2m+1)^2=\frac{n(n+1)}{2}$。

     故 $1^2-2^2+3^2-4^2+\cdots +(-1)^{n+1}n^2=(-1)^{n+1}\cdot \frac{n(n+1)}{2}$。

86. 試證：$1^2+4^2+7^2+\cdots +(3m+1)^2=\frac{(m+1)(6m^2+9m+2)}{2}$。

[書籍] 104 Number Theory Problems: From the Training of the USA IMO Team

Titu Andreescu, Dorin Andrica, Zuming Feng(2007), 104 Number Theory Problems: From the Training of the USA IMO Team
http://www.amazon.com/104-Number-Theory-Problems-Training/dp/0817645276


Example 1.10. [HMMT 2002]
Find $n$ such that $2\parallel 3^{1024}-1$.

Theorem 1.3b.
For any given integer $m$, there is no polynomial $p(x)$ with integer coefficients such that $p(n)$ is prime for all integers $n$ with $n>m$.

Example 1.12.
Compute gcd$(2002+2,2002^{2}+2,2002^{3}+2,\cdots )$.

Corollary 1.10.
Let $p$ be a prime, and let $k$ be an integer with $1\leq k<p$. Then $p\mid \binom{p}{k}$.

Example 1.15. [Russia 2001]
Let $a$ and $b$ be distinct positive integers such that $ab(a+b)$ is divisible by $a^{2}+ab+b^2$. Prove that $\left | a-b \right |>\sqrt[3]{ab}$.

Example 1.16. [AIME 1988]
Compute the probability that a randomly chosen positive divisor of $10^{99}$ is an integer multiple of $10^{88}$.

Example 1.17.
Determine the number of ordered pairs of positive integers $(a, b)$ such that the least common multiple of $a$ and $b$ is $2^{3}5^{7}11^{13}$.

Example 1.18.
Determine the product of distinct positive integer divisors of $n = 420^4$.

Corollary 1.15.
For any positive integer $n$, $\prod_{d\mid n}^{\; }d=n^{\frac{\tau (n)}{2}}$.

The Number of Divisors $\tau (n)=\sum_{d\mid n}^{\; }1$, The Sum of Divisors $\sigma (n)=\sum_{d\mid n}^{\; }d$.

Corollary 1.16.
For any positive integer $n$, $\tau (n)\leq 2\sqrt{n}$.

Example 1.19.
Find the sum of even positive divisors of $10000$.

Example 1.21. [Russia 2001]
Find all primes $p$ and $q$ such that $p + q =(p − q)^{3}$.

Example 1.22. [Baltic 2001]
Let $a$ be an odd integer. Prove that $a^{2^n} + 2^{2^n}$ and $a^{2^m} + 2^{2^m}$ are relatively prime for all positive integers $n$ and $m$ with $n\neq m$.

Example 1.23.
Determine whether there exist infinitely many even positive integers $k$ such that for every prime $p$ the number $p^2 + k$ is composite.

Residue Classes

Example 1.25. [Romania 2003]
Consider the prime numbers $n_1 < n_2 < \cdots <n_{31}$. Prove that if $30$ divides $n_{1}^{4}+n_{2}^{4}+\cdots +n_{31}^{4}$, then among these numbers one can find three consecutive primes.

Example 1.26.
Let $m$ be an even positive integer. Assume that $\left \{ a_{1},a_{2},\cdots ,a_{m} \right \}$ and $\left \{ b_{1},b_{2},\cdots ,b_{m} \right \}$ are two complete sets of residue classes modulo $m$. Prove that $\left \{ a_{1}+b_{1},a_{2}+b_{2},\cdots ,a_{m}+b_{m} \right \}$ is not a complete set of residue classes.

Theorem 1.26. [Wilson’s Theorem]
For any prime $p$, $(p-1)!\equiv -1\; (\mathbf{mod}\; p)$.

Fermat’s Little Theorem and Euler’s Theorem

Example 1.30.
Let $p\geq 7$ be a prime. Prove that the number  $\underset{p-1\; \mathbf{1's}}{\underbrace{11\cdots 1}}$ is divisible by $p$.

Example 1.31.
Let $p$ be a prime with $p > 5$. Prove that $p^{8}\equiv 1\; (\mathbf{mod}\; 240)$.

Example 1.32.
Prove that for any even positive integer $n$, $n^2−1$ divides $2^{n!}−1$.

Example 1.33. [IMO 2005]
Consider the sequence $a_1, a_2,\cdots$ defined by $a_{n}=2^{n}+3^{n}+6^{n}-1$ for all positive integers $n$. Determine all positive integers that are relatively prime to every term of the sequence.

Example 1.35. [IMO 2003 shortlist]
Determine the smallest positive integer $k$ such that there exist integers $x_1, x_2,\cdots , x_k$ with $x_{1}^{3}+x_{2}^{3}+\cdots +x_{k}^{3}=2002^{2002}$.

Example 1.36. [AIME 2001]
How many positive integer multiples of $1001$ can be expressed in the form $10^j −10^i$ , where $i$ and $j$ are integers and $0\leq i\leq j\leq 99$?

Euler’s Totient Function

Theorem 1.34. [Gauss]
For any positive integer $n$, $\sum_{d\mid n}^{\; }\phi (d)=n$.

Example 1.37.
Let $n$ be a positive integer.
(1) Find the sum of all positive integers less than $n$ and relatively prime to $n$.
(2) Find the sum of all positive integers less than $2n$ and relatively prime to $n$.

Linear Diophantine Equations

Example 1.39.
Let $n$ be a positive integer. Suppose that there are $666$ ordered triples $(x, y, z)$ of positive integers satisfying the equation $x+8y+8z=n$. Find the maximum value of $n$.

Numerical Systems

Example 1.41. [AHSME 1973]
In the following equation, each of the letters represents uniquely a different digit in base ten: $(YM)\cdot (ME)=TTT$. Determine the sum $E + M + T + Y$.

Example 1.42. [AIME 2001]
Find the sum of all positive two-digit integers that are divisible by each of their digits.

Example 1.43. [AMC12A 2002]
Some sets of prime numbers, such as ${7, 83, 421, 659}$, use each of the nine nonzero digits exactly once. What is the smallest possible sum such a set of primes can have?

Example 1.48.
Determine all positive integers $n$ such that $11111_{(n)}$ is a perfect square.

Divisibility Criteria in the Decimal System

Example 1.50. Perfect squares or not?
(1) Determine all positive integers $k$ such that the $k$-digit number $11\cdots 1$ is not a perfect square.
(2) Can a $5$-digit number consisting only of distinct even digits be a perfect square?
(3) Determine whether $\underset{2004}{\underbrace{20\cdots 04}}$ is a perfect square.

Example 1.52.
Determine the number of five-digit positive integers $\overline{abcde}$$(a, b, c, d,$ and $e$ not necessarily distinct) such that the sum of the three-digit
number $\overline{abc}$ and the two-digit number $\overline{de}$ is divisible by 11.

Example 1.53. [USAMO 2003]
$S(n)$ denote the sum of its digits. Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

Example 1.54. [Russia 1999]
In the decimal expansion of $n$, each digit (except the first digit) is greater than the digit to its left. What is $S(9n)$?

Example 1.55. [Ireland 1996]
Find a positive integer $n$ such that $S(n) =1996S(3n)$.

Example 1.56. 
Determine whether there is any perfect square that ends in $10$ distinct digits.

Example 1.57. [IMO 1976]
When $4444^{4444}$ is written in decimal notation, the sum of its digits is $A$. Let $B$ be the sum of the digits of $A$. Find the sum of the digits of $B$.

Floor Function

Example 1.60. [ARML 2003]
Find the positive integer $n$ such that $\frac{1}{n}$ is closest to $\left \{ \sqrt{123456789} \right \}$.

Example 1.61 [AIME 1997]
Suppose that $a$ is positive, ${a^{−1}} = {a^2}$, and $2 < a^2 < 3$. Find the value of $a^{12} − 144a^{−1}$.

Example 1.62. 
Find all real solutions to the equation $4x^2-40\left \lfloor x \right \rfloor+51=0$.

以上節錄了一些題目，有興趣的可以自行練習。