[數論] 整值多項式 (Integer-valued Polynomial)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
數學研發論壇 http://bbs.emath.ac.cn/thread-2912-1-1.html
NEWTON FORWARD INTERPOLATION ON EQUISPACED POINTS
https://www3.nd.edu/~jjwteach/441/PdfNotes/lecture7.pdf
呂冠緯，高一上數學(第二章：多項式函數)
http://www.youtube.com/playlist?list=PLZruNYXiv2mC6Prcx7cWl064sU_0vA8Di

當變數 $x$ 取整數時，若多項式 $f(x)$ 的值恆為整數，則稱 $f(x)$ 為整值多項式。

整係數的多項式一定是整值多項式，但有沒有可能當係數非整數、$f(x)$ 的值卻都為整數呢？有的，例如當多項式是組合數(combination number)形式時，也就是說，

$\forall x\in \mathbb{Z},\; f(x)=\binom{x}{n}=\frac{x\cdot (x-1)\cdots (x-n+1)}{n!}\in \mathbb{Z},\; 0\leq n\leq x$.

定理12 一個 $n$ 次多項式 $f(x)$ 是整值多項式的充分必要條件是 $f(x)$ 可以寫成

$f(x)=C_{n}\binom{x}{n}+C_{n-1}\binom{x}{n-1}+\cdots +C_1\binom{x}{1}+C_0$，其中 $C_i,\; 0\leq i\leq k$ 皆為整數。

<pf>
必要性$(\Leftarrow )$
因為 $\binom{x}{n},\binom{x}{n-1},\cdots ,\binom{x}{1},1$ 皆為整值多項式。整值多項式分別乘上整數 $C_n,C_{n-1},\cdots ,C_0$ 後相加仍為整值多項式。

充分性$(\Rightarrow )$
任何一個 $n$ 次多項式必可寫成 $f(x)=C_{n}\binom{x}{n}+C_{n-1}\binom{x}{n-1}+\cdots +C_1\binom{x}{1}+C_0$ 的形式。現在要證明當 $f(x)$ 是整值多項式時，$C_i,\; 0\leq i\leq k$ 皆為整數。

我們記 $\Delta f(x)=f(x+1)-f(x)$(First order forward difference)。一般地有 $\Delta ^{r}f(x)=\Delta (\Delta ^{r-1}f(x))$。

則 $\Delta f(x)=f(x+1)-f(x)$
                $=C_n\left [ \binom{x+1}{n}-\binom{x}{n} \right ]+C_{n-1}\left [ \binom{x+1}{n-1}-\binom{x}{n-1} \right ]+\cdots +C_1\left [ \binom{x+1}{1}-\binom{x}{1} \right ]$
                $=C_n\binom{x}{n-1}+C_{n-1}\binom{x}{n-2}+\cdots +C_1$.

得到 $f(0)=C_0$
        $\Delta f(x)\mid_{x=0}=C_1$
        $\Delta ^2f(x)\mid_{x=0}=C_2$
           $\vdots$
        $\Delta ^nf(x)\mid_{x=0}=C_n$.

因為 $f(x)$ 是整值多項式，所以 $\Delta f(x),\; \Delta ^2f(x),\; \cdots ,\; \Delta ^nf(x)$ 也都是整值多項式。所以 $C_0$, $C1$, $\cdots$, $C_n$ 也都是整數。

定理14 設 $n$ 次多項式為 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,\: (a_k\neq 0)$。若 $x$ 取 $n+1$ 個連續整數 $a,\; a+1,\cdots ,\; a+n$ 時，$f(x)$ 的值皆為整數，則 $f(x)$ 為整值多項式。

定理14' 設 $n$ 次多項式為 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,\: (a_k\neq 0)$。若 $x$ 取 $n+1$ 個連續整數 $a,\; a+1,\cdots ,\; a+n$ 時，$f(x)$ 的值皆能被 $m$ 整除，則對任意 $x$，$m\mid f(x)$。

上面兩個定理可用牛頓插值公式或 Lagrange's interpolation formula 證明。牛頓插值公式也叫做牛頓級數，由「牛頓前向差分方程」的項組成。

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

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

[數論] 原根 (Primitive Roots)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
李華介，基礎數論 http://math.ntnu.edu.tw/~li/ent-html/node34.html
Integers with Primitive Roots https://proofwiki.org/wiki/Integers_with_Primitive_Roots
Primitive Roots Modulo the First 1000 Numbers
http://dbfin.com/2012/04/primitive-roots-modulo-the-first-1000-numbers/

在前兩篇 (二次剩餘，Legendre Symbol) 我們只有討論二次剩餘的存在性，並沒有給出一個完整地求解方法，當然列舉法也算一種求解方法，但這不在本篇的討論範圍內。為了要求解，我們會用到「原根(Primitive roots)」的概念。

原根定義
設整數 $a$ 和 $m$ 互質。 使 $a^{\delta }\equiv 1\; (\mathbf{mod\; }m)$ 成立的最小正整數 $\delta$ 稱為 $a$ 對模 $m$ 的次數(degree)或階(order)。根據 Euler's theorem，若 整數 $a$ 和 $m$ 互質，則 $a^{\phi (m)}\equiv 1\; (\mathbf{mod\; }m)$。當 $\delta =\phi (m)$，稱 $a$ 是模 $m$ 的一個原根。

定理1：若 $a$ 對模 $m$ 的次數是 $\delta$。若 $\delta \mid n$，則 $a^{n}\equiv 1\; (\mathbf{mod}\; m),\; n>0$ 。
<pf>
這是一個充分必要條件的證明。
先證明充分性。假設 $\delta \mid n$，即 $n=k\cdot \delta ,k\in \mathbb{Z}$。因此 $a^{n}\equiv a^{k\cdot \delta }\equiv \left (a^{\delta }  \right )^{k}\equiv 1^{k}\equiv 1\; (\mathbf{mod}\; m)$。

證明必要性。若 $n$ 不是 $\delta$ 的倍數，表示存在兩整數 $q$、$r$，使得 $n=q\delta +r,\; 0<r<\delta$，則

$1\equiv a^{n}\equiv a^{q\delta +r}\equiv \left (a^{\delta}  \right )^{q}\cdot a^{r}\equiv 1\cdot a^{r}\equiv a^{r}\; (\mathbf{mod}\; m)$，

這與 $\delta$ 為最小的定義矛盾，故 $\delta \mid n$。證畢。

定理2：若 $a$ 對模 $m$ 的次數為 $\delta$，則 $1,a,a^2,\cdots ,a^{\delta -1}$ 對模 $m$ 皆不同餘。
<pf>
假設有兩整數 $k$，$l$，滿足 $a^{k}\equiv a^{l}\; (\mathbf{mod}\; m),\; 0\leq k< l<\delta$。因為 gcd$(a,m)=1$，故有 $\frac{a^{l}}{a^{k}}\equiv a^{l-k}\equiv 1\; (\mathbf{mod}\; m)$。因為 $l-k<\delta$，這與 $\delta$ 是最小的定義矛盾，故原命題成立。

在 二次剩餘 這篇，證明 Euler's Criterion 時，就用到了原根的性質。利用原根的概念，$m$ 的簡化剩餘系可以用一套規律的方式寫下。假設 $a$ 是模 $m$ 的一個原根，根據上述定理2，$\left \{ a^{0},a^{1},\cdots ,a^{\phi (m)-1} \right \}$ 其實就是模 $m$ 的簡化剩餘系。我們之後習慣用這種簡化剩餘系說明之。

$\left \{ a^{0},a^{1},\cdots ,a^{\phi (m)-1} \right \}$ 是模 $m$ 的簡化剩餘系。

定理3：若 $a$ 對模 $m$ 的次數是$r$。設有一數 $\lambda >0$，$a^{\lambda }$ 對模 $m$ 的次數是 $t$，則 $t=\frac{r}{(\lambda ,r)}$。
<pf>
根據上述定理1，我們有 $r\mid \lambda t$，即得 $\frac{r}{(\lambda ,r)}\mid \frac{\lambda }{(\lambda ,r)}\cdot t$。因為 $\left ( \frac{r}{(\lambda ,r)} ,\frac{\lambda }{(\lambda ,r)}\right )=1$，所以 $\frac{r}{(\lambda ,r)}\mid t$。

另一方面，$(a^{\lambda })^{\frac{r}{(\lambda ,r)}}\equiv a^{r\cdot \frac{\lambda }{(\lambda ,r)}}\equiv 1\; (\mathbf{mod}\; m)$，根據定理1，有 $t\mid \frac{r}{(\lambda ,r)}$。所以 $t=\frac{r}{(\lambda ,r)}$。

這個定理告訴我們，如果 $g$ 是模 $m$ 的原根，則 $g^{k}$ 是模 $m$ 原根的充分必要條件是 gcd$(k,\phi (m))=1$。這是一個非常重要的結論！例如我們找到了模 $m$ 的一個原根 $g$，只要 $g$ 的次方數 $k$ 與 $\phi (m)$ 互質，那麼 $g^k$ 也會是模 $m$ 的一個原根。換句話說，

只要找到了模 $m$ 的一個原根，我們就可以找出其他的原根。

定理4：設 $a$ 對模 $m$ 的次數是 $\delta$。若 gcd$(\lambda ,\delta )=1$，$0<\lambda \leq \delta$，則 $a^{\lambda }$ 對模 $m$ 的次數均為 $\delta$，符合條件的 $\lambda$ 有 $\phi (\delta )$ 個。

<pf>
在 $1,2,\cdots ,\delta$ 中，與 $\delta$ 互質的數有 $\phi (\delta )$ 個。當 gcd$(\lambda ,\delta )=1$，根據定理3，我們知道 $a^{\lambda }$ 對模 $m$ 的次數均為 $\delta$。證畢。

根據定理3，只要 $g$ 的次方數 $k$ 與 $\phi (m)$ 互質，那麼 $g^k$ 也會是模 $m$ 的一個原根。與 $\phi (m)$ 互質的數的個數有 $\phi (\phi (m))$。換句話說，

設模 $m$ 有原根，則它共有 $\phi (\phi (m))$ 個對於模 $m$ 不相同的原根。

定理5：若 $a$ 對模 $m$ 的次數為 $s$，$b$ 對模 $m$ 的次數為 $t$。若 gcd$(s,t)=1$，則 $ab$ 對模 $m$ 的次數為 $st$。
<pf>
設 $ab$ 對模 $m$ 的次數為 $\delta$。$(ab)^{st}=a^{st}\cdot b^{st}=[a^{s}]^{t}\cdot [b^{t}]^{s}\equiv 1\; (\mathbf{mod}\; m)$。我們得到 $\delta \mid st$。

另一方面，$1\equiv [(ab)^{\delta }]^{s}\equiv (ab)^{s\delta }\equiv a^{s\delta }\cdot b^{s\delta }\equiv a^{s\delta }\cdot (b^{s})^\delta \equiv b^{s\delta }\; (\mathbf{mod}\; m)$，我們得到 $t\mid s\delta$。因為 gcd$(s,t)=1$，所以 $t\mid s\delta$ 可改寫成 $t\mid \delta$。

同理，$1\equiv [(ab)^{t}]^{\delta }\equiv a^{t\delta }\cdot b^{t\delta }\equiv (a^{t})^\delta \cdot b^{t\delta }\equiv b^{t\delta }\; (\mathbf{mod}\; m)$，可以得到 $s\mid \delta$。因為 gcd$(s,t)=1$，所以有 $st\mid \delta$，而一開始已證明 $\delta \mid st$，故 $st=\delta$，證畢。

實際解二次同餘方程之前，其實有很多東西要講。首先，原根是否一定存在？答案是否，原根必須要符合某些條件才會存在。例如對於模 $8$，$\phi (8)=\phi \left ( 2^{3} \right )=2^{3}-2^{2}=4$，由於任何與 $8$ 互質的整數都是奇數，奇數的平方除以 $8$ 都是餘 $1$，這表示對於奇數 $x$，$x^{2}\equiv 1\; (\mathbf{mod}\; 8)$，$2< \phi (8)$，故模 $8$ 沒有原根。

討論完原根的存在性之後，接著再討論如何求出原根，最後利用原根的特性，求出二次同餘式、甚至是高次同餘式的解。

原根的存在性

若 $m$ 為 $2$, $4$, $p^{k}$, $2p^{k}$ ($p$ 為奇質數) 四者之一時，原根才存在。

證明可在各數論書籍找到，故略。我們把重點放在原根的計算上。

原根的計算

[數論] Legengre symbol 和 二次互反律

參考資料
李華介 基礎數論 http://math.ntnu.edu.tw/~li/ent-html/node30.html
Squares Modulo p http://www.math.brown.edu/~jhs/MA0042/FRINTNewCh2324.pdf
Proofs of quadratic reciprocity http://en.wikipedia.org/wiki/Proofs_of_quadratic_reciprocity
Gauß, Eisenstein, and the "third'' proof of the Quadratic Reciprocity Theorem: Ein kleines Schauspiel
http://math.nmsu.edu/~history/schauspiel/schauspiel.html

在上一篇，我們在文章最後提到了利用 Legendre symbol 去判別二次剩餘的存在性。

二次剩餘定義
For $x,m\neq 0$, $a$ is a quadratic residue mod $m$ if $x^{2}=a$ (mod $m$). Otherwise, $a$ is a quadratic nonresidue.

Legendre symbol定義
令 $p$ 是奇質數，$a$ 是整數，$(a,p)=1$。 Legendre Symbol $\left ( \frac{a}{p} \right )\overset{def}{=} a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$.

我們利用 Legendre symbol 是完全積性函數的特性，「把 $a$ 拆解成較小的數字相乘，再去計算其 Legendre Symbol 的值」。下面將說明完整的拆解及計算流程。

首先，對 $a$ 做質因數分解。為了不失一般性，我們寫成 $a=(-1)2^{k_{0}}\cdot q_{1}^{k_2}q_{2}^{k_2}...q_{n}^{k_n}$，其中 $q_1$ 到 $q_n$ 都是質數。

其次，將 $a$ 代入 Legendre symbol，得到 $\left ( \frac{a}{p} \right )=\left ( \frac{-1}{p} \right )\left ( \frac{2}{p} \right )\left ( \frac{q_{1}^{k_1}}{p} \right ) \left ( \frac{q_{2}^{k_2}}{p} \right )...\left ( \frac{q_{n}^{k_n}}{p} \right )$

對於 $\left ( \frac{q_{i}^{k_i}}{p} \right )$，利用 Legendre symbol 完全積性函數的特性，我們只需計算 $\left ( \frac{q_{i}}{p} \right )$ 的值，將此值乘上 $k_i$ 次，就是 $\left ( \frac{q_{i}^{k_i}}{p} \right )$ 了。 因此對於 $a$ 的計算，底下我們分成三種情況討論，$\left ( \frac{-1}{p} \right )$、$\left ( \frac{2}{p} \right )$、$\left ( \frac{q}{p} \right )$，其中 gcd$(q,p)=1$。

情況一、計算 $\left ( \frac{-1}{p} \right )$
判別 $\left ( \frac{-1}{p} \right )$ 的值是不是 $1$，相當於尋找哪些質數 $p$，能使  $x^{2}\equiv -1\; (\mathbf{mod}\; p)$ 有解。

根據 Euler's Criterion，$a$ 是模 $p$ 的平方剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv 1\: (\mathbf{mod}\; p)$。

這裡我們的 $a=-1$。代入 Euler's Criterion 後，得到 $(-1)^{\frac{p-1}{2}}\equiv 1\: (\mathbf{mod}\; p)$。顯然 $\frac{p-1}{2}$ 必須是偶數，故 $\frac{p-1}{2}=2k$，$k\in \mathbb{Z}$。整理後得到 $p=4k+1$，這就是我們要的結果！

情況二、計算 $\left ( \frac{2}{p} \right )$
這回我們無法用 Euler's Criterion 去證明。為了要製造出 $(-1)$ 的次方，我們會利用之前這篇、證明 Euler's theorem 的技巧。

考慮下面 $\frac{p-1}{2}$ 個同餘式。

$p-1\equiv 1\cdot (-1)\; (\mathbf{mod}\; p)$

       $2\equiv 2\cdot (-1)^{2}\; (\mathbf{mod}\; p)$

 $p-3\equiv 3\cdot (-1)^{3}\; (\mathbf{mod}\; p)$

       $4\equiv 4\cdot (-1)^{4}\; (\mathbf{mod}\; p)$

...

                      $r\equiv \left ( \frac{p-1}{2} \right )\cdot (-1)^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

對於第 $r$ 個，也就是第 $\frac{p-1}{2}$ 個，$\frac{p-1}{2}$ 可能是奇數或偶數。若 $\frac{p-1}{2}$ 是偶數，表示 $\frac{p-1}{2}=2k$，$k\in \mathbb{Z}$，此時 $p=4k+1$；同理，若 $\frac{p-1}{2}$ 是奇數，則 $p=4k+3$。換句話說，

將上面 $\frac{p-1}{2}$ 個同餘式兩端相乘。得到 $2\cdot 4\cdots (p-3)\cdot (p-1)\equiv \left ( \frac{p-1}{2} \right )!\left ( -1 \right )^{1+2+\cdots +\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

左端重新整理，得到 $2\cdot 4\cdots (p-3)\cdot (p-1)=2^{\frac{p-1}{2}}\cdot \left ( \frac{p-1}{2} \right )!$。

右端 $(-1)$ 的次方數 $1+2+\cdots +\frac{p-1}{2}=\frac{\left ( 1+\frac{p-1}{2} \right )\cdot \left ( \frac{p-1}{2} \right )}{2}=\frac{p^{2}-1}{8}$。

把整理後的項目代入上面相乘後的同餘式，得到 $2^{\frac{p-1}{2}}\cdot \left ( \frac{p-1}{2} \right )!\equiv \left ( \frac{p-1}{2} \right )!\cdot (-1)^{\frac{p^{2}-1}{8}}\; (\mathbf{mod}\; p)$。

因為 $\left ( \frac{p-1}{2} \right )!$ 是偶數，gcd$(\left ( \frac{p-1}{2} \right )!,p)=1$，所以兩端可以消去 $\left ( \frac{p-1}{2} \right )!$，得到 $2^{\frac{p-1}{2}}\equiv (-1)^{\frac{p^{2}-1}{8}}\; (\mathbf{mod}\; p)$。根據 Euler's Criterion，$\left ( \frac{2}{p} \right )\equiv 2^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$。因為兩端的絕對值等於 $1$，且 $p$ 是奇質數，故同餘的符號可改為等號，也就是說，$\left ( \frac{2}{p} \right )= (-1)^{\frac{p^{2}-1}{8}}$。

當 $p$ 等於多少時，$\frac{p^{2}-1}{8}$ 會是偶數呢？答案有兩個：$p=8k+1$ 及 $p=8k-1$，解 $p$ 過程可用奇偶數性質去判斷，建議一定要自己練習去解出 $p=8k\pm 1$。

情況三、計算 $\left ( \frac{q}{p} \right )$，其中 gcd$(q,p)=1$
根據 Gauss's Lemma(文末會證明)，我們可以有 $\left ( \frac{q}{p} \right )=(-1)^n$，其中 $n$ 是數列 $q,2q,\cdots ,\left ( \frac{p-1}{2} \right )q$ 中、對模 $p$ 的最小正剩餘裡大於 $\frac{p}{2}$ 的個數。當 $n$ 是奇數時，$(-1)^{n}=-1$；當 $n$ 是偶數時，$(-1)^{n}=1$。Gauss's Lemma 的重要性在於我們不用去算 $a^{\frac{p-1}{2}}$，而是改算最小正剩餘裡大於 $\frac{p}{2}$ 的個數，降低了計算的工作量。

要如何找出 $n$？或者說，如何判別 $n$ 是奇數或偶數？目前看過最多人用的是 Eisenstein 的方法，又稱 Eisenstein's Lemma，因為較為直覺且可用幾何圖形表示。

Eisenstein's Lemma：假設 $q$ 是奇數，$p$ 是奇質數，$gcd(q,p)=1$，對於 $\left ( \frac{q}{p} \right )=(-1)^n$ 中的 $n$，有 $n=\sum_{k=1}^{\frac{p-1}{2}}\left \lfloor \frac{qk}{p} \right \rfloor$。這裡 $\left \lfloor \;  \right \rfloor$ 是 floor function 符號，例如 $\left \lfloor 4.7 \right \rfloor=4$，$\left \lfloor -3.7 \right \rfloor=-4$。

這裡不證明 Eisenstein's Lemma，我們直接用例子了解。例如我們要計算 $\left ( \frac{7}{11} \right )$，先求出 $n=\sum_{k=1}^{\frac{11-1}{2}}\left \lfloor \frac{7k}{11} \right \rfloor=\sum_{1}^{5}\left \lfloor \frac{7k}{11} \right \rfloor$。

計算五個 floor function 的值，分別得到 $0,1,1,2,3$，於是 $n=0+1+1+2+3=7$。最後得到 $\left ( \frac{7}{11} \right )=(-1)^7=-1$。

但如果 $n$ 很大，計算 $n$ 個 floor function 的值就很頭痛了。此時有一個很重要的定律就派上用場了，叫做「二次互反律(Quadratic Reciprocity Law)」。

 二次互反律(Quadratic Reciprocity Law)
定義：若 $p,q$ 都是奇質數，$p\neq q$，則 $\left ( \frac{q}{p} \right )\left ( \frac{p}{q} \right )=(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$。或者說，

在網路和書籍可以找到很多證明二次互反律的說明，礙於篇幅就不在這裡贅述，有興趣的可以看這篇最底下的補充。透過二次互反律，可以把較大的分母($p$)替換成較小的($q$)，計算時更為快速。

分析完上述三種情況：計算 $\left ( \frac{-1}{p} \right )$、計算 $\left ( \frac{2}{p} \right )$、計算 $\left ( \frac{q}{p} \right )$，計算 $\left ( \frac{a}{p} \right )$ 就簡單多了。

Gauss's Lemma(高斯引理)
Gauss's Lemma 定義：
設 $a\in \mathbb{Z}$，$p$ 是奇質數，$gcd(a,p)=1$。則 $\left ( \frac{a}{p} \right )=(-1)^n$，其中 $n$ 是數列 $a,2a,\cdots ,\left ( \frac{p-1}{2} \right )a$ 中、對模 $p$ 的最小正剩餘裡大於 $\frac{p}{2}$ 的個數。

從 $(-1)^{n}$ 來看，當 $n$ 是奇數時，$(-1)^{n}=-1$；當 $n$ 是偶數時，$(-1)^{n}=1$。

例如我們要判別 $\left ( \frac{3}{17} \right )$ 的值，也就是 $x^{2}\equiv 3\; (\mathbf{mod }17)$ 是否有解。這裡的 $a=3$，$p=17$，而 $\frac{p-1}{2}=\frac{17-1}{2}=8$。數列 $3,6,9,12,15,18,21,24$ ，對模 $17$ 的最小正剩餘依序為 $3,6,9,12,15,1,4,7$，大於 $\frac{p}{2}$，也就是大於 $\frac{17}{2}$ 的個數有三個：$9,12,15$，因此 $n=3$。$\left ( \frac{3}{17} \right )=(-1)^3=-1$，$3$ 是模 $17$ 的二次非剩餘，所以同餘式 $x^{2}\equiv 3\; (\mathbf{mod }17)$ 無解。

Gauss's Lemma 證明
已知 $(a,p)=1$，令 $k\in \left \{ 1,2,\cdots ,\frac{p-1}{2} \right \}$，有 $(ka,p)=1$。

設 $a,2a,3a,\cdots ,\frac{p-1}{2}a$ 對模 $p$ 的最小正剩餘為 $r_{1},r_{2},\cdots ,r_{\frac{p-1}{2}}$，且 $0<r_{1}<r_{2}<\cdots <r_{\frac{p-1}{2}}<p$。假設大於 $\frac{p}{2}$ 的最小正剩餘有 $n$ 個，小於 $\frac{p}{2}$ 的有 $m$ 個，其中 $m+n=\frac{p-1}{2}$，於是我們把原本的  $r_{1},r_{2},\cdots ,r_{\frac{p-1}{2}}$ 改寫為

 $\underset{<\frac{p}{2}}{\underbrace{r_{1},r_{2},\cdots ,r_{m}}},\underset{>\frac{p}{2}}{\underbrace{r_{m+1},\cdots ,r_{\frac{p-1}{2}}}}$。

對於 $\underset{>\frac{p}{2}}{\underbrace{r_{m+1},\cdots ,r_{\frac{p-1}{2}}}}$，為了使每一項都小於 $\frac{p}{2}$，我們對每一項都減去 $p$，變成  $p-r_{m+1},p-r_{m+2},\cdots ,p-r_{m+n}$。

對於下面的數列

$r_{1},r_{2},\cdots ,r_{m},p-r_{m+1},p-r_{m+2},\cdots ,p-r_{m+n}$，

我們接著要證明，這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。這樣他們相乘時剛好會是 $\left ( \frac{p-1}{2} \right )!$。

前面已經說明這 $\frac{p-1}{2}$ 個數都小於 $\frac{p}{2}$。只要證明這 $\frac{p-1}{2}$ 個數皆不相同，就相當於證明了這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。

我們用反證法。假設有 $r_{s}=p-r_{t}$，移項得到 $r_{s}+r_{t}=p$，也就是 $x_{s}a+y_{t}a=(x_{s}+y_{t})a\equiv 0\; (\mathbf{mod}\; p)$。因為 $(a,p)=1$，所以得到 $x_{s}+y_{t}\equiv 0\; (\mathbf{mod}\; p)$。但是 $1\leq x_{s}\leq \frac{p-1}{2}$，$1\leq y_{t}\leq \frac{p-1}{2}$，相加後的範圍是 $2\leq x_{s}+y_{t}\leq p-1$，而 $\left \{ 2,3,\cdots ,p-1 \right \}$ 中的每個元素都無法被 $p$ 整除，故原本的假設是錯誤的。因此這 $\frac{p-1}{2}$ 個數恰好是 $1,2,\cdots ,\frac{p-1}{2}$。

所以 $\left ( \frac{p-1}{2} \right )!=r_{1}r_{2}\cdots r_{m}(p-r_{m+1})\cdots (p-r_{m+n})$

                     $\equiv (-1)^{n}r_{1}r_{2}\cdots r_{\frac{p-1}{2}}$

                     $\equiv (-1)^{n}a\cdot 2a\cdot \cdots \frac{p-1}{2}a$

                     $\equiv (-1)^{n}\left ( \frac{p-1}{2} \right )!a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$

因為 $\left ( \left ( \frac{p-1}{2} \right )!,p \right )=1$，故同餘式兩端除以 $\left ( \frac{p-1}{2} \right )!$，得到 $1\equiv (-1)^{n}a^{\frac{p-1}{2}}\; (\mathbf{mod}\; p)$。於是有

$a^{\frac{p-1}{2}}\equiv (-1)^n\; (\mathbf{mod}\; p)$。

根據 Legengre symbol 定義，$\left ( \frac{a}{p} \right )\equiv a^{\frac{p-1}{2}}\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )$，也就是 $\left ( \frac{a}{p} \right )\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )$。

對於 $\left ( \frac{a}{p} \right )\equiv (-1)^n\; \left ( \mathbf{mod}\; p \right )，$因為 $p$ 是奇質數，所以 $\left ( \frac{a}{p} \right )=(-1)^n$，證明完畢。

[數論] 二次剩餘 (Quadratic Residues)

參考資料
Chapter 4: Quadratic residues http://www.math.uiuc.edu/~hildebr/453.spring11/nt-notes4.pdf
中文數學百科Wiki http://zh.math.wikia.com/wiki/二次剩餘?variant=zh-tw
Number of Quadratic Residues of a Prime
http://www.proofwiki.org/wiki/Number_of_Quadratic_Residues_of_a_Prime
Euler's Criterion http://www.proofwiki.org/wiki/Euler's_Criterion
第五講 二次剩餘 http://wenku.baidu.com/view/0c908d0dba1aa8114431d942

如果對同餘的的概念不熟悉，可以先看這一段影片：

「二次剩餘」定義
任意非零平方整數除以某個數後可能的餘數，我們稱之為「二次剩餘」。用數學式表達如下：

For $x,m\neq 0$, $a$ is a quadratic residue mod $m$ if $x^{2}=a$ (mod $m$). Otherwise, $a$ is a quadratic nonresidue(二次非剩餘).

例如對模$10$而言，可能的餘數集合為$\left \{ 0,1,4,5,6,9 \right \}$：

$\left\{\begin{matrix}0^{2}\equiv 0 & \\1^{2}\equiv 1 & \\2^{2}\equiv 4 & \\3^{2}\equiv 9 & \\4^{2}\equiv 6 & \\5^{2}\equiv 5 & \mathbf{(mod\; 10)}\\6^{2}\equiv 6 & \\7^{2}\equiv 9 & \\8^{2}\equiv 4 & \\9^{2}\equiv 1 &\end{matrix}\right.$

一般來說，因為 $x^{2}=0$ (mod $m$)總是有解，所以通常不會把 $0$ 考慮進去。這也是一開始定義 $x$ 時會強調是「非零整數」的原因。在此例中，模 $10$ 的二次剩餘是 $\left \{1,4,5,6,9 \right \}$。

若 $p$ 是一個奇質數(odd prime，除了 $2$ 以外的質數)，則在 $\{1, 2, \ldots, p - 1\}$ 中，模 $p$ 的二次剩餘與二次非剩餘的數量會是相等的。 換句話說，對一奇質數 $p$ 而言，模 $p$ 的二次剩餘數量 = 二次非剩餘數量 = $\frac{p-1}{2}$。

欲看證明可看參考資料第三個連結：Proof Wiki。簡單來說，就是要證明 $(p-i)^{2}\equiv i^{2}\; (\mathbf{mod}\; p)$。把 $(p-i)^{2}$ 展開，得到 $(p-i)^{2}=p^2-2pi+i^2\equiv i^2\; (\mathbf{mod}\; p)$，證明完畢。

例如以模 $11$ 為例，在 $1,2,...,10$ 中有一半為平方剩餘，他們分別與 $1^{2},2^{2},3^{2},4^{2},5^{2}$ 同餘。由於

$\left\{\begin{matrix}1^{2}\equiv 1 &\mathbf{mod}\: 11 \\2^{2}\equiv 4 &\mathbf{mod}\: 11 \\3^{2}\equiv 9 &\mathbf{mod}\: 11 \\4^{2}\equiv 5 &\mathbf{mod}\: 11 \\5^{2}\equiv 3 &\mathbf{mod}\: 11\end{matrix}\right.$

所以 $1,4,9,5,3$ 是模 $11$ 的平方剩餘。

現在我們知道對於某奇質數 $p$，求出模 $p$ 之二次剩餘的方法。反過來看，現在我給你一個數 $a$，有沒有辦法判別 $a$ 是不是模 $p$ 的二次剩餘呢？當然，我們可以照著上面的步驟，先將模 $p$ 的二次剩餘全部找出來，再看 $a$ 是不是在剩餘集合裡面。但對於數字較大的 $p$，這樣顯得很沒效率。因此我們要介紹一種判別法，可以幫助我們快速判別一個數是否為模 $p$ 之二次剩餘。

Euler's Criterion(歐拉準則)：判定給定的整數是否是一個質數的二次剩餘
定義：若 $(a,p)=1$，$p$ 是奇質數，則
(1) $a$ 是模 $p$ 的平方剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$
(1) $a$ 是模 $p$ 的平方非剩餘的充分必要條件是 $a^{\frac{p-1}{2}}\equiv -1\; (\mathbf{mod}\; p)$

注意上式給的是"充分必要"條件，因此有必要去證明。證明可參考 Euler's Criterion 網頁，過程中會用到 Euler's Totient Theorem。

充分性：若 $a$ 是模 $p$ 的平方剩餘，則  $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$。
<pf> Assume $a$ is a quadratic residue modulo $p$. $\exists \; k\in \mathbb{Z}$ s.t. $k^{2}\equiv a\; (\mathbf{mod\; }p)$. $(k^{2})^{\frac{p-1}{2}}\equiv k^{p-1}\equiv a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod\; }p)$ by Congruence of Powers and Fermat's Little Theorem.

必要性：若 $a^{\frac{p-1}{2}}\equiv 1\; (\mathbf{mod}\; p)$，則 $a$ 是模 $p$ 的平方剩餘。
<pf> $(a^{\frac{p-1}{2}})^{2}\equiv a^{p-1}\equiv 1^{2}\equiv 1\; (\mathbf{mod}\; p)$. Let $b$ is a *primitive root for $p$. $\exists k\in \mathbb{Z}$ s.t. $a=b^{k}$.

$a^{\frac{p-1}{2}}=(b^{k})^{\frac{p-1}{2}}=b^{\frac{k(p-1)}{2}}\equiv 1\; (\mathbf{mod}\; p)$. $\frac{k(p-1)}{2}$must be a multiple of $(p-1)$, so $\frac{k}{2}$ is an integer, which means $k$ is even. $a=b^{k}$ is the square of $b^{\frac{k}{2}}.$

*何謂原根？Let $p$ be a prime. Then $b$ is a primitive root for $p$ if the powers of $b$, $1$, $b$, $b^2$, $b^3$, ...
include all of the residue classes mod $p$ (except $0$).

歐拉準則給了我們另一種判別 $a$ 是否為 $p$ 的二次剩餘的方法，這顯然比列出剩餘系、然後一個一個慢慢檢驗來的方便。但是，一旦 $p$ 很大的時候，計算 $a^{\frac{p-1}{2}}$ 絕非易事！因此數學家又想到另一種方式去檢驗二次剩餘。這種方式其實和歐拉準則有點像，但表達的方式略有差異。

Legendre Symbol(勒讓得符號，二次特徵)
定義：令 $p$ 是奇質數，$a$ 是整數，$(a,p)=1$。 Legendre Symbol $\left ( \frac{a}{p} \right )\overset{def}{=} a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$

在歐拉準則中我們已經看過 $a^{(\frac{p-1}{2})}\; (\mathbf{mod}\; p)$ 了。Legendre Symbol 則是改用另一種符號來表示：$\left ( \frac{a}{p} \right )$。我們可以進一步改寫上面的定義，使其看起來更簡潔。

Legendre Symbol 其實是 Jacobi Symbol 的特例(當分母是質數 $p$ 的特例)。使用 Legendre Symbol 時別忘了分子與分母的限制(分母是質數，分子與分母互質)。有些書會寫 $\left ( \frac{a}{p} \right )=0$ if $p\mid a$，也就是說當 $a$ 是 $p$ 的倍數，$(a,p)=p$，則 $\left ( \frac{a}{p} \right )=0$。因為我們一般只討論當 $a$ 與 $p$ 互質的情形，所以沒有把 $0$ 寫在定義裡。

Legendre Symbol 有下列性質。想看證明的可以參考這個網頁，或是看 YouTube 這段影片。
1. $\left ( \frac{a^2}{p} \right )=1$。
2. 若 $a_{1}\equiv a_{2}\; (\mathbf{mod}\; p)$，有 $\left ( \frac{a_{1}}{p} \right )=\left ( \frac{a_{2}}{p} \right )$。
3. $\left ( \frac{a}{p} \right )$ 是完全積性函數，即 $a=a_{1}a_{2}...a_{n}$ 時，有 $\left ( \frac{a}{p} \right )=\left ( \frac{a_{1}}{p} \right )\left ( \frac{a_{2}}{p} \right )...\left ( \frac{a_{n}}{p} \right )$。

透過第三個性質，把 $a$ 拆解成較小的數字相乘，再去計算其 Legendre Symbol 的值，會比直接用 $a$ 去計算來的方便多了。最後總結一下這篇文章介紹的三種判別二次剩餘的方法。
1. 逐項代入法，亦即逐項檢驗 $p$ 的剩餘系。
2. 歐拉準則
3. 利用 Legendre Symbol

RSA加密演算法

參考資料
Proof of the RSA Algorithm https://sites.google.com/site/danzcosmos/proof-of-the-rsa-algorithm
RSA算法原理 http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

資料加密(Data encryption)，如同替家門或金庫上鎖一樣，都是為了防止外人輕易窺知裡頭的東西。加密可分為「對稱式」與「非對稱式」。「對稱式」是指用同一把鑰匙進行加密和解密動作，「非對稱式」則是指加解密時採用不同的鑰匙。

對稱式的加解密方法比較直觀，也比較方便，但這也是它的致命傷。因為對稱式加密系統，加解密都是用同一把鑰匙，萬一鑰匙在某個環節被破解，等於宣告整個系統瓦解，因此有必要改進這種加密系統模式。

非對稱式加密系統是利用公開鑰匙(Public Key)和私密鑰匙(Private Key)進行加密解密動作。公開鑰匙是公開資訊，用於加密資料時使用；私密鑰匙是隱藏資訊，只有解密者擁有，用於解密時使用。

關鍵：加密用公鑰，解密用私鑰。

RSA加密演算法於1973年，由Ron Rivest、Adi Shamir 和 Leonard Adleman 三人提出，1977年正式對外發表。

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。

RSA演算法會用的數論工具主要有二：Euler's theorem(歐拉定理)及Modular inverse(模反元素)。

Euler's theorem 會在製作公鑰時用到，modular inverse 用於製作私鑰。公私鑰製作流程如下圖。

有了公鑰和私鑰元素，接著我們來看如何進行加解密的操作，並針對RSA的安全性做討論。

加解密的流程如下圖，我們限制$m<n$：

我們必須證明 $c^{d}\equiv m$ (mod $\varphi (n)$) 這條同餘式的正確性。

<pf> $c^{d}\equiv (m^{e})^d \equiv m^{ed}\equiv m^{k \cdot \varphi (n)+1}$ (mod $\varphi (n)$), where $k$ is an integer.

CASE 1. If $(m,n)=1$, according to Euler's theorem, we have $m^{\varphi (n)}\equiv 1$ (mod $n$), so $m^{k\cdot \varphi (n)}\equiv 1$ (mod $n$). Therefore, $m^{k\cdot \varphi (n)+1}\equiv m$ (mod $\varphi (n)$)

CASE 2. If $m$ and $n$ are not coprime, you can try to prove it yourself. The answer is written in the 2nd reference.

透過上式證明，我們可以確定加解密的算法是正確的，但它的安全性呢？我能否光憑 $n$, $e$ 兩數，就可以算到 $d$ 呢？

$d$ 從何而來？$d$ 是在上述的步驟5出現，由 $e$ 而來；而 $e$ 是步驟4中由 $\varphi (n)$，也可以說由 $n$ 而來；而 $n$ 是兩個質數的乘積。因此$d$ 的破解與否，$n$ 的質因數分解扮演莫大的角色。如同我們在一開始提到到這段話：

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。

[數論] 歐拉定理 (Euler's theorem)、Wilson's theorem

參考資料
http://www.math.cornell.edu/~putnam/modular.pdf
http://www.millersville.edu/~bikenaga/number-theory/euler/euler.html (推薦)

Euler's theorem

定義 $a^{\varphi (n)}\equiv 1\; ($mod$\; n)$, 其中 $\varphi (n)$ 是 Euler's phi function, $(a,n)=1$.

證明：內容擷自下面兩段 YouTube 影片, 雖然影片是證明費馬小定理, 但仍不失一般性(費馬小定理是歐拉定理的特例.). 簡單來說, a mod n, 2a mod n, ..., (n-1)a mod n 的餘數的集合是 {1, 2, ..., n-1}. 例如a=3, n=5, (a, n)=1, 則 3 mod 5, 6 mod 5, ..., 12 mod 5 的餘數依序是 3, 1, 4, 2, 寫成集合是 {1, 2, 3, 4}.

我們得到式子 $a\cdot 2a\cdot ...\cdot (n-1)a\equiv 1\cdot 2\cdot ...\cdot (n-1)\equiv (n-1)!$ mod $n$

上式可改寫成 $(n-1)!\cdot a^{n-1}\equiv (n-1)!$ mod $n$.
將上式左右兩邊消去 $(n-1)!$, 即得 $a^{n-1}\equiv 1$ mod $n$. 證明完畢

Euler's theorem 可以簡化我們在計算某個數的高次方的餘數. 假設今天我們想知道 $7^{222}$ 除以 $10$ 的餘數, 亦即 $7^{222}$ 的個位數字.

方法1. 算出 $7^{222}$, 看個位數字. 這個方法很直觀, 若次方數字很小, 這個方法也許比較快, 但對於高次方, 例如這裡的 $222$, 顯然毫無效率可言.

方法2. 試圖看 $7$ 的次方數中, 個位數字有無規律. 依序列出後會發現 $7$ 的次方的個位數字會以 $1,9,3,7$ 的順序出現, 每四個數循環一次. 所以我們把 $222$ 除以循環週期 $4$, 得到餘數 $2$, 最後得到 $7^{222}$ 個位數字是 $9$. 這個方法很好用, 但遇到週期很長的題目, 甚至是看出不週期的時候, 這個方法就派不上用場.

如果知道 Euler's theorem, 我們就可以用第三種方法來解決這類問題.

方法3. 因為 $(7,10)=1$, 所以我們可以用 Euler's theorem. 因為 $\varphi (10)=4$, 所以我們知道 $7^{4}\equiv 1\; ($mod$\; 10)$. 接著再用方法2中, 看 $222$ 除以 $4$ 的餘數. 最後得到答案是 $9$

萬一....要是 $a$ 和 $n$ 不互質呢? 例如我把 $7^{222}$ 改成 $8^{222}$, 那不就不能直接套用 Euler's theorem 嗎? 此時我們要對 $n$ 做適當地分解.

因為 $10=2\times 5$, 所以我們分開求 $8^{222}$ 除以 $2$ 及 $8^{222}$ 除以 $5$ 的餘數. $8^{222}\equiv 0\; ($mod$\; 2)$; 另一方面, 因為 $(8,5)=1$, $\phi (5)=4$, 由 Euler's theorem 得知 $8^{\varphi (5)}\equiv 8^{4}\equiv 1\; ($mod$\; 5)$, 而 $222$ 除以 $4$ 的餘數是 $2$, 所以 $8^{222}\equiv 8^{55\times 4+2}\equiv 1\times 8^{2}\equiv 4\; ($mod$\; 5)$. 最後得到答案是 $4$(why?).

Beacuse $8^{222}=2a=5b+4$, we know that $b$ must be even. Let $b=2c$, then $5b+4=5(2c)+4=10c+4$. Therefore, $8^{222}\equiv 4\: ($mod$\: 10)$.

練習題
試求 $16^{198}$ 的末兩位數字. (答案：$96$)


有一個跟 Euler's theorem 的類似的定理, 叫做 Wilson's theorem. 下面的證明擷自影片內容.

Wilson's theorem: $p$ is prime iff $(p-1)!\equiv -1$ mod $p$.

<pf> If $p$ is prime, and $k\in \left \{ 1,2,...,p-1 \right \}$, then there exists two integers $a$ and $b$ such that $ak+bp=1$(according to the Euclidean algorithm). We have $ak+bp\equiv ak\equiv 1$ (mod $p$). It says that the modular multiplicative inverse of $k$ modulo $p$ exists.

The point is to to pair each number with its modular inverse. There are two exceptions: $k=1$ and $k=p-1$. The modular inverses of 1 and p-1 modulo p are equal to themselves (check: $1\times 1\equiv 1$ mod $p$, $(p-1)(p-1)\equiv 1$ mod $p$).

$(p-1)!\equiv 1\cdot (2\cdot 2^{-1})\cdot (3\cdot 3^{-1})...\cdot (p-1)\equiv p-1\equiv -1$ mod $p$. Q.E.D.

Note: $2^{-1}$ 是指 $2$ 的模反元素, 它會是 $\left \{ 2,3,...,p-2 \right \}$ 的某個元素. 同理, $3^{-1}$ 也會是 $\left \{ 2,3,...,p-2 \right \}$ 的某個元素, 且 $2^{-1}$ 和 $3^{-1}$ 不會相同, 不會有重複的問題. 下面是證明.

For two integers $a,b\in \left \{ 2,3,...,p-2 \right \}$. Assume $a$ and $b$ have the same modular multiplicative inverse modulo $p$, called $k$. $ak\equiv bk\equiv 1$ mod $p$.
$\Leftrightarrow ak-bk\equiv 0$ mod $p$
$\Leftrightarrow (a-b)k\equiv 0$ mod $p$

Since $k\in \left \{ 2,3,...,p-1 \right \}$, $(k,p)=1$, $(a-b)$ must be a multiple of $p$. We know that $a,b\in \left \{ 2,3,...,p-2 \right \}$, $0\leq (a-b)< p$. Therefore, $a=b$. Q.E.D.

[數論] 歐拉函數(Euler's Phi Function)

參考資料
EulerTheorem-Silverman http://palmer.wellesley.edu/~ivolic/pdf/Classes/USEM/EulerTheorem-Silverman.pdf

定義2 一個數論函數 $f(n)$, 若 $(m,n)=1$, 具有性質 $f(mn)=f(m)f(n)$, 則稱 $f(n)$ 為「積性函數(multiplicative function)」. 若不論有無 $(m,n)=1$, 上式都成立, 則稱 $f(n)$ 為「完全積性函數(complete multiplicative function)」.

例2 試證: $h_{\lambda }(n)=n^{\lambda }$($\lambda$為常數)是完全積性函數.
<pf> 設 $n=n_{1}n_{2}$, 無論 $n_{1}$ 與 $n_{2}$ 是否互質, 都有 $h_{\lambda }(n)=h_{\lambda }(n_{1}n_{2})=(n_{1}n_{2})^{\lambda }=(n_{1})^{\lambda }(n_{2})^{\lambda }=h_{\lambda }(n_{1})h_{\lambda }(n_{2})$. 由定義得知, $h(n)$ 是完全積性函數.

性質2 若積性函數 $f(n)$ 不恆等於 $0$, 則必有 $f(1)=1$.
<pf> 設 $f(n)\neq 0$. 因為 $f(n)$ 為積性函數, 所以有 $f(n)=f(n\cdot 1)=f(n)f(1)$, 從而 $f(1)=1$.

定義3 小於或等於正整數 $n$ 且與 $n$ 互質的正整數個數稱為 $n$ 的歐拉函數(Euler's function), 記為 $\varphi (n)$.

1. $\phi (1)=1$
2. 若 $n=p$ 是質數, 因為凡是小於 $p$ 的正整數均與 $p$ 互質, 故 $\varphi (p)=p-1$.
3. 若 $n=p^{k}$,$k\in \mathbb{N}$, 亦即 $n$ 是某個質數的次方. 凡是 $p$ 的倍數都不列入. 這些 $p$ 的倍數中, 最大的是 $p^{k}=p^{k-1}p$, 故總共有 $k-1$ 個 $p$ 的倍數.(例如要知道 $\varphi(27)$, 因為 $27=3^{3}$, 故有 $3$, $2\cdot 3$, $3\cdot 3...,$ $3^{2}\cdot 3$, 總共 $3^{2}$個 $3$ 的倍數.). 因此 $\phi (p^{k})=p^{k}-p^{k-1}=p^{k}(1-\frac{1}{p})$.
4. 對於一般正整數 $N$, 對 $n$ 做質因數分解, 得到 $N=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}$. 則 $\phi (N)=\phi (p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}})=\phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})...\phi (p_{n}^{k_{n}})$ (這裡用到了 Euler's function 是積性函數的性質, 證明在文末).

公式：$\phi (N)=N\cdot \left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )...\left ( 1-\frac{1}{p_{n}} \right )$

證明：Euler's function 是積性函數
<pf> If p and q are prime, then $\varphi (pq)=(pq-1)-(q-1)-(p-1)=pq-(p+q)+1=(p-1)(q-1)=\varphi (p)\phi (q)$.
$(q-1)$ 是 $p$ 的倍數的個數, $(p-1)$ 是 $q$ 的倍數的個數.

底下介紹一些歐拉函數的推廣.

Euler's theorem(當要對一個高次方的數取餘數)  http://en.wikipedia.org/wiki/Euler's_theorem
RSA加密演算法 http://en.wikipedia.org/wiki/Euler's_totient_function

[數論] 不定方程

參考資料：
不定方程，凡異出版社，1996年1月初版，ISBN：9576942225

二元一次不定方程
二元一次不定方程式 $ax+by=c$, 其中 $a,b,c$ 都是已知整數, 且 $a,b$ 不全為 $0$.

 $ax+by=c$ 有整數解 $\Leftrightarrow \left ( a,b \right )\mid c$

實際求解的方法，有「誤試法(Trial and Error)」、「歐基里德算法(輾轉相除法)」，有時候解題方法不只一種。

誤試法(Trial and Error)：當 $\left | a \right |,\left | b \right |$ 不大時可以試試看, e.g. $7x+15y=1989$.
歐基里德算法：e.g. $5767x+4453y=-1679$.

設 $(a,b)=1$, $x=x_{0}$, $y=y_{0}$ 是方程式 $ax+by=c$ 的一組解(特解), 則全部的整數解(通解)為 $\left\{\begin{matrix}x=x_{0}+bt\\ y=y_{0}-at\end{matrix}\right.$, $t$ 是任何整數.

<pf> 設 $(x',y')$ 是方程式的一組解, 則 $ax'+by'=c$. 再由 $ax_{0}+by_{0}=c$, 兩式相減得到 $a(x_{0}-x')+b(y_{0}-y')=0$, 由此知 $a\mid b(y_{0}-y')$. 但 $(a,b)=1$, 所以 $a\mid (y_{0}-y')$. 可寫成 $y_{0}-y'=at$, 其中 $t$ 為整數, 即 $y'=y_{0}-at$. 把 $y'=y_{0}-at$ 代回 $a(x_{0}-x')+b(y_{0}-y')=0$, 得到 $x'=x_{0}+bt$.


例10 設 $a,b,n$ 都是正整數, $(a,b)=1$. 當 $n>ab-a-b$ 時, 方程 $ax+by=n$ 有非負整數解; 當 $n=ab-a-b$ 時, 則無非負整數解. 換句話說, 凡大於 $ab-a-b$ 的整數必可表示為 $ax+by$ $(x\geq 0, y\geq 0)$ 的形式, 但 $ab-a-b$ 不能表示為此種形式.

<pf1> 因為 $(a,b)=1$, 所以必有整數 $x,y$ 使得 $ax+by=n$ 成立. 我們總可以選擇 $0\leq x< b$(思考一下,why?).
當 $n>ab-a-b$ 時, $by=n-ax>(ab-a-b)-ax\geq ab-a-b-a(b-1)=-b$. 因此 $y>-1$, 證明了 $y$ 也是非負整數.

當 $n=ab-a-b$ 時, 則 $ax+by=n=ab-a-b$, $x=\frac{ab-a-b-by}{a}=b-1-\frac{b}{a}(y+1)$. 若要使 $x\geq 0$, 因為$(a,b)=1$, 所以 $(y+1)$ 須為 $a$ 的倍數, 且 $\frac{b}{a}(y+1)<b$, 得到 $(y+1)<a$.
且假設 $y$ 也為非負整數, 所以 $(y+1)>0$. 整理得到 $0<(y+1)<a$, 亦即 $a\cdot 0<(y+1)<a\cdot 1$, 顯然 $(y+1)$ 不是 $a$ 的倍數, 與假設矛盾. 故 $x,y$ 無非負整數解.

<pf2>
首先證明方程 $ax+by=n$ 當 $n>ab-a-b$ 時有非負整數解.
方程式的一般解為 $\left\{\begin{matrix}x=x_0+bt\\ y=y_0-at\end{matrix}\right.$, $t\in \mathbb{Z}$. 取 適當的 $t$ 使得 $0\leq y=y_0-at\leq a-1$. 對於此 $t$, 有 $ax=a(x_0+bt)=n-b(y_0-at)>ab-a-b-b(a-1)=-a$. 而 $a>0$, 故 $x=x_0+bt>-1$, 亦即 $x\geq 0$.

其次證明 $n=ab-a-b$ 時, $ax+by=n$ 無非負整數解.
假設方程有解, $x\geq 0, y\geq 0$. 由 $ax+by=n=ab-a-b$ 得 $a(x+1)+b(y+1)=ab$. 因為 $(a,b)=1$, 所以 $a\mid (y+1), b\mid (x+1)$. 於是有 $y+1\geq a, x+1\geq b$. 所以 $ab=a(x+1)+b(y+1)\geq ab+ab=2ab$, 但 $a>0, b>0$, 所以上式矛盾.

例4 若 $a>0$, $b>0$, 且 $(a,b)=1$, 試證：
1. 方程 $ax+by=n$ 的非負整數解之個數為 $\left [ \frac{n}{ab} \right ]$ 或 $\left [ \frac{n}{ab} \right ]+1$.
2. 在 $0\leq n\leq ab-a-b$ 中, 恰有 $\frac{(a+1)(b+1)}{2}$ 個整數 $n$ 能(或不能)表示成 $ax+by$ 的形式, 這裡的 $x,y$ 都是非負整數.


三元一次不定方程
例13 求不定方程 $6x+20y-15z=23$ 的全部整數解.(hint: 從係數小的著手)


一次不定方程組
消元法
例2 《張丘建算經》的百雞問題. 公雞5元一隻, 母雞3元一隻, 小雞1元一隻. 現在用100元買100隻雞, 問公雞, 母雞, 小雞應各買多少隻?
解 設公雞, 母雞, 小雞的隻數分別為 $x,y,z$. 由題意, 得 $\left\{\begin{matrix}x+y+z=100\\ 5z+3y+\frac{z}{3}=100\end{matrix}\right.$. 相應的 $(x,y,z)$ 有 $(0,25,75)$, $(4,18,78)$, $(8,11,81)$ 和 $(12,4,84)$.

[數論] Pell's equation(佩爾方程，二元二次不定方程)

參考資料：
HW Lenstra Jr(2002), Solving the Pell Equation, Volume 49, Number 2

D Djukic(2007), Notes on Pell's equation - Usc
單樽, 余紅兵(1996), 不定方程, 凡異出版社

$\sqrt{2}=[1,\dot{2}]$, $1+\sqrt{5}=[3,\dot{4}]$, 週期都是 $1$; $\frac{3}{\sqrt{7}}=[1,\dot{7},\dot{2}]$, 週期是 $2$.

定理1 拉格朗日(1770)證明一個數字能表示成循環連分數，若且唯若此數為二次無理數(即整數係數的二次方程的實數解)

形如 $x^2-dy^2=1$ 的方程, 其中 $d$ 是整數, 這種方程稱為 Pell's equation. 當 $d$ 是完全平方數時, 方程式只有 $(\pm 1,0)$ 解. 以下僅探討當 $d$ 不是完全平方數的情況.

$x^2-dy^2=1$ 總是有解, 但 $x^2-dy^2=-1$ 就不一定有解.

定理6 若 $x_{0}$, $y_{0}$ 是不定方程 $x^{2}-dy^{2}=1$ 的一組正整數解, 且 $x_{0}+\sqrt{d}y_{0}$ 是形如 $x+\sqrt{d}y$ 的最小數, 則該不定方程的全部正整數解 $x$, $y$ 可由下式表示：$x+\sqrt{d}y=(x_{0}+\sqrt{d}y_{0})^{n}$, $n=1,2,...$.

一個線上解 Pell's equation 的網頁：http://www.had2know.com/academics/pell-equation-calculator.html

定理7 設 $d$ 是非平方的正整數, 且 $\sqrt{d}=[a_{1},\dot{a_{2}},...,\dot{a_{t+1}}]$, $\frac{p_{t}}{q_{t}}=[a_{1},a_{2},...,a_{t}]$ 是它的第 $t$ 個漸近分數,
(1) 當 $t$ 是偶數,
$x^2-dy^2=-1$ 無解;
$x^2-dy^2=1$ 的全部正整數解 $x_{n}$, $y_{n}$ 可由下式確定：$x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=1,2,3,...$

(2) 當 $t$ 是奇數,
$x^2-dy^2=-1$ 的全部正整數解 $x_{n}$, $y_{n}$ 是 $x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=1,3,5,...$.
$x^2-dy^2=1$ 的全部正整數解 $x_{n}$, $y_{n}$ 是 $x_{n}+\sqrt{d}y_{n}=(p_{t}+\sqrt{d}q_{t})^{n}$, $n=2,4,6,...$.

例3 試求兩個不定方程的全部正整數解: $x^{2}-8y^{2}=-1$, $x^{2}-8y^{2}=1$.
[方法一] 利用同餘的概念
$\because x^{2}\equiv 0,1(mod\; 4)$, $\therefore x^{2}-8y^{2}\equiv x^{2}\equiv 0,1\not\equiv -1(mod\; 4)$.
所以 $x^{2}-8y^{2}=-1$ 無整數解.

由觀察法, 得到 $x_{0}=3$, $y_{0}=1$ 是方程 $x^{2}-8y^{2}=1$ 中, 使 $x+\sqrt{8}y$ 最小的一組正整數解, 故按照公式, 全解可由下式確定：$x_{n}+\sqrt{8}y_{n}=(3+\sqrt{8})^{n}$, $n=1,2,3,...$
依次取 $n=1,2,3,...$, 可得 $(x,y)$ 為 $(3,1),(17,6),(99,35)$.

[方法二] 利用循環連分數的概念
將 $\sqrt{8}$ 表示成循環連分數, 得到 $\sqrt{8}=[2,\dot{1},\dot{4}]$, 週期 $t=2$ 為偶數, 故對於 $x^{2}-8y^{2}=-1$ 而言無解; 對於 $x^{2}-8y^{2}=1$, 此時第 $t$ 個, 亦即第 $2$ 個漸近分數為 $[2,1]=2+\frac{1}{1}=\frac{3}{1}$, 取 $(x_{0},y_{0})=(3,1)$, 全解可寫為 $x_{n}+\sqrt{8}y_{n}=(3+\sqrt{8})^{n}$, $n=1,2,3,...$

解答題
2. 試證: $\sqrt{d}$ 能表示成週期 $1$ 的循環連分數的充分必要條件式 $d=m^{2}+1$, $m$ 是正整數.
6. 試求 $\sqrt{8}$ 的分母最小的漸近分數, 使其誤差小於等於 $10^{-6}$.
10. 試按 $a^{2}$, $b$ 的大小情況, 分別討論方程 $x^{2}+2axy+by^{2}=1$ 的整數解.
11. 設直角三角形的三邊長為整數 $a=2mn$, $b=m^{2}-n^{2}$, $c=m^{2}+n^{2}$, 且 $b=a+1$, 試求出所有這樣的三角形, 並寫出其中邊長為最小的兩個.
12. 試證: 不定方程 $x^{2}+(x+1)^{2}=y^{2}$ 的全部正整數解可表示為 $x=\frac{1}{4}\left ( (1+\sqrt{2})^{2k+1}+(1-\sqrt{2})^{2k+1}-2 \right )$, $y=\frac{1}{2\sqrt{2}}\left ( (1+\sqrt{2})^{2k+1}+(1-\sqrt{2})^{2k+1} \right )$, $k=1,2,...$
13. 試證: 若且為若 $3(a^{2}-1)$ 是平方數時, 以 $2a-1$, $2a$, $2a+1$ 為三邊之三角形的面積是整數, 並找出三個這樣的三角形.
14. 若 $a,b$ 是方程 $x^{2}-dy^{2}=1$ 的一組正整數解, 試證: $0<a-\sqrt{d}b$<1.
16. 若 $x_{1},y_{1}$ 是方程 $x^{2}-dy^{2}=-1$ 的一組最小正整數解, 則方程 $x^{2}-dy^{2}=1$ 的所有正整數解 $u_{k},v_{k}$ 可由 $u_{k}+\sqrt{d}v_{k}=(x_{1}+\sqrt{d}y_{1})^{2k}$, $k=1,2,3,...$ 表示.
17. 設 $d$ 是非平方的正整數, 試證: 若方程 $x^{2}-dy^{2}=k$ 有一組整數解, 它就有無窮多組整數解.
19. 設 $d$ 是非平方的正整數, $a$ 是任意的正整數, 試證: 方程 $x^{2}-a^{2}dy^{2}=1$ 有無窮多組正整數解滿足 $a\mid y$.
20. 有無窮多個三角形數也是平方數.
21. 試求下列不定方程的正整數解: (1) $x^{2}-11y^{2}=1$; (2) $x^{2}-11y^{2}=-1$.
22. 試利用連分數求出下列不定方程的正整數解, 並分別算出最小的一組正整數解: (1) $x^{2}-41y^{2}=-1$; (2) $x^{2}-41y^{2}=1$.
23. 設 $x_{1}, y_{1}$ 和 $x_{2},y_{2}$ 是如下方程的兩組整數解: $x^{2}-dy^{2}=4$, 試證: 由下式確定的 $u,v$ 也是這個方程的整數解: $\frac{u+\sqrt{d}v}{2}=\frac{x_{1}+\sqrt{d}y_{1}}{2}\cdot \frac{x_{2}+\sqrt{d}y_{2}}{2}$.
24. 試求不定方程 $x^{2}-3y^{2}=4$ 的全部正整數解.
25. 設整係數不定方程 $ax^{2}+bxy+cy^{2}=k$ 的判別式 $D=b^{2}-4ac$ 是非平方的正整數, $k\neq 0$, 試證: 如果該方程有整數解, 則必有無窮多個整數解.
27. 試求方程 $x^{2}+xy-y^{2}=19$ 的整數解.
29. 試求方程 $x^{2}-229y^{2}=4$ 的 $y$ 值最小的一組正整數解.
30. 試求方程 $3x^{2}-2xy+3y^{2}=72$ 的整數解.
31. 若 $m$ 為正整數, 試證: 有無窮多個正整數 $n$, 使 $mn+1$ 與 $(m+1)n+1$ 都是完全平方數.
33. 試證: 有無窮多個正整數 $n$, 使平均數 $\frac{1^{2}+2^{2}+...+n^{2}}{n}$ 是完全平方數.