从 ​p_1=2, p_2=3开始，进行这种构造，找出5个以上的素数。

  • ​p_3 = 2 * 3 + 1 = 7
  • ​p_4 = 2 * 3 * 7 + 1 = 43
  • ​p_5 = 2 * 3 * 7 * 43 + 1 = 1807
  • ​p_6 = 2 * 3 * 7 * 43 * 1807 + 1 = 3263443
  • ​p_7 = 2 * 3 * 7 * 43 * 1807 * 3263443 + 1 = 10650056950807

找出整数​z被​13整除的规则

对于模​13同余，我们有：
​10\equiv-3,10^2\equiv9,10^3\equiv12,10^4\equiv3,10^5\equiv4,10^6\equiv1,10^7\equiv-3
再接下去的余数则是上面的重复，因此 ​z 被13整除必须而且只须表达式
​z= a_0 - 3a_1 + 9a_2 + 12a_3 + 3a_4 + 4a_5 + a_6 - 3a_7 + \cdots
被​13整除。

说明下面的消去律对素数的模的同余式成立：

如果 ​ab\equiv ac ，且 ​a \not\equiv0 ，则 ​b \equiv c .

​ab - ac \equiv 0

​a(b - c) \equiv 0

因为 ​a \not\equiv0

所以 ​b - c \equiv 0

所以 ​b \equiv c

分配律证明：

\begin{aligned} ab &= ac + rd \\ ab - ac &= rd \\ a(b-c) &= rd \\ a(b-c) &\equiv 0 \\ \end{aligned}

习题

0和6之间哪一个数和乘积​11*18*2322*13*19模7同余？

​11 ≡ 4(mod 7)
​18 ≡ 4(mod 7)
​2322 ≡ 5(mod 7)
​13 ≡ 6(mod 7)
​13 ≡ 5(mod 7)
​111823221319 ≡ 4 * 4 * 5 * 6 * 5 (mod 7)
​4 * 4 * 5 * 6 * 5 ≡ 2400(mod 7) ≡ 6(mod 7)

0和12之间哪一个数和乘积​371117192329*113模13同余？

​3 ≡ 3(mod 13)
​7 ≡ 7(mod 13)
​11 ≡ 11(mod 13)
​17 ≡ 4(mod 13)
​19 ≡ 6mod 13)
​23 ≡ 10(mod 13)
​29 ≡ 3(mod 13)
​113 ≡ 9(mod 13)
​371117192329*113 ≡ 3 * 7 * 11 * 4 * 6 * 10 * 3 * 9 (mod 13)
​3 * 7 * 11 * 4 * 6 * 10 * 3 * 9 ≡ 1496880(mod 13)≡ 8(mod 13)

0和4之间哪一个数与​1 + 2 + 2^2 + \cdots + 2^{19}的和模5同余？

设2的指数为 ​k(k>=0) 。
​2^0 ≡ 1(mod 5)
​2^1 ≡ 2(mod 5)
​2^2 ≡ 4(mod 5)
​2^3 ≡ 3(mod 5)
​2^4 ≡ 1(mod 5)
接下来随着k的增长余数是重复，所以k模4观察。
若 ​k ≡ 0(mod 4) ，则 ​2^k = 2 ^{4n}=16^n,(n>=0) 。因为 ​16 ≡ 1(mod 5) ，所以 ​16^n ≡ 1(mod 5) ，所以 ​2^k ≡ 1(mod 5) 。
若 ​k ≡ 1(mod 4)，则 ​2^k = 2 ^{4n+1}=216^n,(n>=0) 。因为 ​16 ≡ 1(mod 5) ，所以 ​216^n ≡ 2(mod 5) ，所以 ​2^k ≡ 2(mod 5) 。
若 ​k ≡ 2(mod 4) ，则 ​2^k = 2 ^{4n+2}=416^n,(n>=0) 。因为 ​16 ≡ 1(mod 5) ，所以 ​416^n ≡ 4(mod 5) ，所以 ​2^k ≡ 4(mod 5) 。
若 ​k ≡ 3(mod 4) ，则 ​2^k = 2 ^{4n+3}=816^n,(n>=0) 。因为 ​16 ≡ 1(mod 5) ，所以 ​816^n ≡ 3(mod 5) ，所以 ​2^k ≡ 3(mod 5) 。
​1 + 2 + 2^2 + \cdots + 2^{19} = 1 + 2 + 4 + 3 + \cdots + 3(mod 5) = 5 * (1 + 2 + 4 + 3)(mod 5) = 0(mod 5)

费马定理

用类似的计算表明：​2^8≡1(mod17); 3^8≡-1(mod17); 3^{14}≡-1(mod29);2^{14}≡-1(mod29);4^{14}≡1(mod29);5^{14}≡1(mod29);

\begin{aligned} 2^1 ≡ 2(mod17) \\ 2^2 ≡ 4(mod17) \\ 2^5 ≡ 15(mod17) \\ 2^6 ≡ 13(mod17) \\ 2^8 ≡ 52(mod17) ≡1(mod17) \end{aligned}
\begin{aligned} 3^1 ≡ 3(mod17) \\ 3^2 ≡ 9(mod17) \\ 3^3 ≡ 10(mod17) \\ 3^4 ≡ 13(mod17) \\ 3^5 ≡ 5(mod17) \\ 3^8 ≡ 50(mod17) ≡-1(mod17) \end{aligned}
\begin{aligned} 3^2 ≡ 9(mod29) \\ 3^3 ≡ -2(mod29) \\ 3^4 ≡ -6(mod29) \\ 3^8 ≡ 7(mod29) \\ 3^{10} ≡ 5(mod29) \\ 3^{14} ≡ -6*5(mod29) ≡1(mod29) \end{aligned}
\begin{aligned} 2^2 ≡ 4(mod29) \\ 2^4 ≡ 16(mod29) \\ 2^5 ≡ -3(mod29) \\ 2^{10} ≡ 9(mod29) \\ 2^{12} ≡ 7(mod29) \\ 2^{14} ≡-1(mod29) \end{aligned}
\begin{aligned} 2^{14} ≡ -1(mod29) \\ 4^{14} = 2^{15} = 2^{14} * 2^{14} = 1(mod29) \end{aligned}
\begin{aligned} 5^2 ≡ -4(mod29) \\ 5^4 ≡ 16(mod29) \\ 5^5 ≡ -7(mod29) \\ 5^{10} ≡ -9(mod29) \\ 5^{12} ≡ 7(mod29) \\ 5^{14} ≡1(mod29) \end{aligned}

对​p=5,7,11,17,23，用不同的​a值来核对费马定理。

3^4 = 3^2*3^2 ≡ 4 * 4 (mod 5) ≡ 1(mod5)
\begin{aligned} 4^2 ≡ 2 (mod 7) \\ 4^4 ≡ 4 (mod 7) \\ 4^6 ≡ 1(mod7) \end{aligned}
\begin{aligned} 3^2 ≡ -2 (mod 11) \\ 3^4 ≡ 4 (mod 11) \\ 3^8 ≡ 5(mod11) \\ 3^{10} ≡ 1(mod11) \\ \end{aligned}
\begin{aligned} 5^2 ≡ 8 (mod 17) \\ 5^4 ≡ -4 (mod 17) \\ 5^8 ≡ -1(mod17) \\ 5^{16} ≡ 1(mod17) \end{aligned}
\begin{aligned} 7^2 ≡ -3 (mod 23) \\ 7^4 ≡ 9 (mod 23) \\ 7^6 ≡ -4(mod23) \\ 7^{12} ≡ 16(mod23) \\ 7^{14} ≡ -2(mod23) \\ 7^{16} ≡ -6(mod23) \\ 7^{22} ≡ 1(mod23) \end{aligned}

证明一个一般的定理：使​a^e≡1 \pmod p的最小正整数​e必须是​p-1的一个因子（提示：用​e除​p-1得到​p-1=ke+r，这里​0 \leqq r<e，并且用​a^{p-1}≡a^e≡1 \pmod a这一事实）

\begin{aligned} \because a^e≡1 \pmod p \\ \therefore a^{ke} ≡ 1 \pmod p \\ \because a^{p-1} ≡ 1 \pmod p \\ \therefore a^{ke+r} ≡ 1 \pmod p \\ \therefore a^{ke}*a^r ≡ 1 \pmod p \\ \therefore a^r ≡ 1 \pmod p \end{aligned}

根据条件，使 ​a^e≡1 \pmod p的最小正整数为​e ，且​0 \leqq r<e ，因此 ​r不可能为正整数。故能满足​a^r ≡ 1 \pmod p的 ​r 的唯一取值为0。因此 ​p-1 = ke，也即 ​e 为 ​p-1 的一个因子。

二次剩余

​6^2 = 36 ≡ 13 \pmod {23}，​23是不是二次剩余​\pmod {13}?

\begin{aligned} \because [\cfrac {23-1} 2]*[\cfrac {13-1} 2] 是偶数且13是二次剩余 \\ \therefore 23是二次剩余 \\ 6^2 = 36 ≡ 23 \pmod {13} \end{aligned}

我们已看到​x^2≡(p-x)\pmod p，说明这是数​1^2,2^2,3^2,\cdots,(p-1)^2中间仅有的同余关系。