数论基础阅读笔记与习题解答之三:同余运算

《数论基础》第三章首先介绍了同余、同余系、同余算术与逆元的概念,在此基础上介绍了费马小定理、威尔逊与拉格朗日的同余定理,本章也涉及了二次丢番图方程以及原根。各节习题解答如下:

3.1 模\(n\)同余

3.1.1 十进制数\(a_ka_{k-1}\cdots a_0\)可以表示成为\(10^ka^k+10^{k-1}a_{k-1}+\cdots+10a_1+a_0\),显然\(2\)可以整除\(10,10^2,\cdots,10^k\),则\(a_ka_{k-1}\cdots a_0\)除以\(2\)的余数由\(a_0\)决定,也就是由个位数决定。

3.1.2 同理\(5,10\)也可以整除\(10,10^2,\cdots,10^k\),则也可由个位数决定。

3.1.3 显然\(4\)不能整除\(10\),但可以整除\(10^2,10^3\cdots,10^k\),则余数由\(10a_1+a_0\)决定,也就是由后两位数除以四的余数决定。

3.1.4 同理我们有\(8\mid10^3,16\mid10^4\),则除八余数由后三位决定,除十六余数由后四位决定。

3.2 同余系与同余算术

3.2.1 因为\(10\equiv 1\pmod3\),所以同样有\(a_i10^i\equiv a_i\pmod 3\),因此只有当各位数之和整除三时,这个数字才能够整除三。

3.2.2 因为\(10\equiv-1\pmod{11}\),显然有\(10^2\equiv(-1)^2\pmod{11},10^3\equiv(-1)^3\pmod{11}\),则可以得到\(10^k\equiv(-1)^k\pmod{11}\)

3.2.3 根据上题结论有\(10^ka_i=(-1)^ka_i\pmod{11}\),则:

$$ 10^{k} a_{k} +\cdots +10^{2} a_{2} +10a_{1} +a_{0} \equiv ( -1)^{k} a_{k} +\cdots +a_{2} -a_{1} +a_{0}\pmod{11} $$

则某数除以十一的余数就等于其各位数字交替相加相减之和再除以十一的余数。

3.3 模\(p\)逆元

3.3.1 据题意\(a\)不是\(p\)的倍数,则设\(a\equiv r\pmod{p}\),则有\(ia\equiv ir\pmod{p}\),已知\(r\ne0\),则只有当\(i\equiv0\pmod{p}\)时,\(ia\equiv0\pmod{p}\)

3.3.2\(ia\equiv ja\pmod{p}\),则有\(p\mid{ia-ja=a(i-j)}\),因\(a\)不是\(p\)的倍数,则有\(p\mid(i-j)\),则显然有\(i\equiv j\pmod{p}\)

3.3.3 据题意对于\(i\in[1,p-1]\)\(i\)均与\(p\)互质,则有\(i\not\equiv0\pmod{p}\),同时我们有\(a\not\equiv0\pmod{p}\),则我们有\(ia\not\equiv0\pmod{p}\),即\(ia\)\(p\)剩余不可能等于零,即只能在\(1\)\((p-1)\)之间。同时,我们假设对于\(r,s\in[1,p-1]\)\(ra\equiv sa\pmod{p}\),根据性质3.3.2有\(r\equiv s\pmod{p}\),因为\(r,s\)均小于\(p\),则此种情况只能有\(r=s\),则对于不同的\(i\)\(ia\)\(p\)的结果必然不同,考虑这些结果处于\(1\)\(p-1\)之间,总共有\((p-1)\)个且各不相同,则只能是对\([1,p-1]\)的整数进行重新排序,这实际上就是题目需要证明的结论。

在此基础上,我们可以证明费马小定理,只需要在把题目结论的两边分别相乘,则有:

$$ a^{p-1}(p-1)!\equiv(p-1)!\pmod{p} $$

因为\([1,p-1]\)的整数均与\(p\)互质,则显然\((p-1)!\)也与\(p\)互质,因此根据3.3.2上述方程两边可以同时消去\((p-1)!\),则有\(a^{p-1}\equiv1\pmod{p}\),正是费马小定理。

3.3.4 容易验证如下:

微信图片_20210607165238

显然最后一列只是对\([1,6]\)间整数的重新排列。

3.4 费马小定理

3.4.1 见3.3.3的推导

3.4.2 同见3.3.3的推导

3.4.3 容易验证如下:

微信图片_20210607190218

显然当\(p=2,2^4\equiv1\pmod{5}\)\(4\)是满足这个条件的最小正整数,且因为\(4=5-1\)所以\(2\)\(5\)的原根。当\(p=7\)时,有\(2^3\equiv1\pmod{7}\),而\(3\ne7-1\),所以\(2\)不构成\(7\)的原根。

3.4.4 下表中行表示底数\(a\),列表示指数\(n\),行与列交叉处的值为\(\bmod(a^n,7)\),则从表格中可以看出当\(a=3,5\)时,\(a^6\equiv1\pmod{7}\),即\(7\)的原根应是\(3\)\(5\)

微信图片_20210607203555

3.4.5\((\mathbb{Z}/p\mathbb{Z})^\times\)包括\(1\)\((p-1)\)\((p-1)\)个元素,设其中一个元素为\(a\),则显然\(a\not\equiv0\pmod{p}\),则根据费马小定理有\(a^{p-1}\equiv1\pmod{p}\),设\(d\mid{p-1}\),则有:

$$ a^{p-1}\equiv a^{qd}\equiv (a^d)^q\equiv1\pmod{p}\Rightarrow a^d\equiv1\pmod{p} $$

则显然\(d\)构成\(a\)\(p\)的阶。

3.5 威尔逊与拉格朗日同余定理

3.5.1 据题意有\(n\)是一个合数,则可以分为两种情况:

因此,题目给出的条件是不准确的,只有当\(n>4\)时,原式才成立。

3.5.2 根据上题可知\(n\ is\ not\ prime \Rightarrow ( n-1) !\equiv 0 (\bmod n)\),其逆否命题为:

$$ ( n-1) !\not\equiv \ 0\ (\bmod \ n) \ \Rightarrow \ n\ is\ prime $$

显然当\((n-1)!\equiv-1\pmod{n}\)时,\(n\)是一个素数。这证明了原命题的充分性,而教材中已经证明了原命题的必要性,则有\(n\ is\ prime\Longleftrightarrow(n-1)!\equiv-1\pmod{n}\)

3.5.3\(n=7\)时,\((n-1)!=6!=720\equiv-1\pmod{7}\),所以有\(n\)是一个素数。

3.6 模\(k\)逆元

3.6.1 \(\varphi(n)\)表示小于\(n\)的数中与\(n\)互质的数的个数,当\(n\)是一个素数时,个数显然为\((n-1)\)

3.6.2\(1,2,3\cdots,p^i\)中的\(p\)的倍数分别是\(p,2p,3p,\cdots,p^{i-1}p\),显然有\(p^{i-1}\)个。

3.6.3 \(\varphi(p^i)\)表示小于\(p^i\)的自然数中与其互质的数的个数,它显然等于\(p^i\)减去小于\(p^i\)的自然数中和它不互质的数的个数,这些数即因子中包含有\(p\)的数,也即\(p\)的倍数,我们在上题中已经推导出\(p^i\)以内\(p\)的倍数总共有\(p^{i-1}\)个,所以有\(\varphi(p^i)=p^i-p^{i-1}=p^{i-1}(p-1)\)

3.6.4 显然有\(\varphi(5)=4,\varphi(3)=2\),而\(15\)以内与其互质的数有\(1,2,4,7,8,11,13,14\)共八个数,所以有\(\varphi(15)=8=\varphi(5)\varphi(3)\)

3.7 二次丢番图方程

3.7.1 容易验证如下:

微信图片_20210611123753

3.7.2 容易验证如下:

微信图片_20210611170043

可以发现,对于前十个\(4n+1\)型的素数,其表示成为平方和的方式是唯一的。

3.7.3 容易验证前十个\(8n+1\)或者\(8n+3\)型的素数及其分解方式如下:

$$ \begin{aligned} 3 & =1^{2} +2*1^{2}\\ 11 & =3^{2} +2*1^{2}\\ 17 & =3^{2} +2*2^{2}\\ 19 & =1^{2} +2*3^{2}\\ 41 & =3^{2} +2*4^{2}\\ 43 & =5^{2} +2*3^{2}\\ 59 & =3^{2} +2*5^{2}\\ 67 & =7^{2} +2*3^{2}\\ 73 & =1^{2} +2*6^{2}\\ 83 & =9^{2} +2*1^{2} \end{aligned} $$

可以发现他们的分解方式也是唯一的。

3.7.4 容易验证前十个\(3n+1\)型的素数及其分解方式如下:

$$ \begin{aligned} 7 & =2^{2} +3*1^{2}\\ 13 & =1^{2} +3*2^{2}\\ 19 & =4^{2} +3*1^{2}\\ 31 & =2^{2} +3*3^{2}\\ 37 & =5^{2} +3*2^{2}\\ 43 & =4^{2} +3*3^{2}\\ 61 & =7^{2} +3*2^{2}\\ 67 & =8^{2} +3*1^{2}\\ 73 & =5^{2} +3*4^{2}\\ 79 & =2^{2} +3*5^{2} \end{aligned} $$

可以发现他们的分解方式也是唯一的。

3.8 原根

3.8.1 显然有\(1/12=0.083333...\)从第三位小数开始循环;\(1/14=0.0714285\ 714285...\)从第二位小数开始循环,则符合题目的条件。

3.8.2 如果\(n\)的因子只包含\(2\)或者\(5\),即:

$$ \frac{1}{n}=\frac{1}{2^x5^y}=\frac{1}{2^x5^y}\cdot\frac{2^y5^x}{2^y5^x}=\frac{2^y5^x}{(2\cdot5)^{x+y}}=\frac{2^y5^x}{10^{x+y}} $$

因为其分母是\(10\)的倍数,所以\(1/n\)必然是一个有限小数。反之,如果\(n\)的因子中不包含\(2\)\(5\),则\(1/n\)是一个纯循环小数。最后,如果\(n\)的因子包含\(2\)\(5\)以及其它因子,设\(n=2^x5^yd\),则有:

$$ \frac{1}{n} =\frac{1}{2^{x} 5^{y} d} =\frac{1}{2^{x} 5^{y}} \cdot \frac{2^{y} 5^{x}}{2^{y} 5^{x}} \cdot \frac{1}{d} =\frac{2^{y} 5^{x}}{(2\cdot 5)^{x+y}} \cdot \frac{1}{d} =\frac{2^{y} 5^{x}}{10^{x+y}} \cdot \frac{1}{d} $$

显然此时\(1/n\)就是一个部分循环小数。

3.8.3 容易验证如下:

$$ \begin{aligned} 10^{1} & \equiv 10\ ( mod\ 13)\\ 10^{2} & \equiv \ 9\ ( mod\ 13)\\ 10^{3} & \equiv \ 12\ ( mod\ 13)\\ 10^{4} & \equiv \ 3\ ( mod\ 13)\\ 10^{5} & \equiv \ 4\ ( mod\ 13)\\ 10^{6} & \equiv \ 1\ ( mod\ 13) \end{aligned} $$

则显然\(10\)\(13\)的阶\(\delta_{13}(10)=6\)

3.8.4 容易验证\(p=17\)时,\(10^{p-1}\equiv10^{16}\equiv1\pmod{17}\),而\(1/17=0.\overline{0588235294117647}\),其循环节的数量正好为\(17-1=16\)

3.9 原根的存在性

3.9.1