第零章 集合与整数

欧拉函数和欧拉-费马定理

首先介绍数论中一个重要的函数即欧拉函数.

设$n$为一正整数，在$0,1,2,\cdots ,n-1$中与$n$互素的整数的个数记作$\varphi (n)$，叫做欧拉函数.由同余性质$6$知道，$\varphi (n)$也就是那些模$n$的剩余类的个数，这些剩余类是由与$n$互素的整数组成的.从这些剩余类取出的代表所组成的集合叫做模$n$的既约剩余代表系.一个既约剩余代表系$T$也可以这样来刻画：$1)$任一个与$n$互素的整数必与$T$中一个数模$n$同余，而且$2)T$中整数与$n$互素而且模$n$两两不同余.

设$r_1 ,r_2 ,\cdots ,r_N ,N=\varphi (n)$，为模$n$的一个既约剩余代表系，$(a,n)=1$，则$ar_1 ,ar_2 ,\cdots ,ar_N $仍是模$n$的一个既约剩余代表系.这是因为，首先根据互素性质$4)$和同余性质$4$，$ar_1 ,ar_2 ,\cdots ,ar_N $与$n$互素而且两两互不同余$\pmod{n} $.其次，每个$ar_i $和某一个$r_{a_i } (1\leq a_i \leq N)$同余，而且当$i\neq j$有$a_i \neq a_j $，于是$ar_i \mapsto r_{a_i }$是一个单射，因而是一个满射.$\alpha _1 ,\alpha _2 ,\cdots ,\alpha _N $是$1,2,\cdots ,N$的一个排列.由于每个与$n$互素的整数$b$必与某个$r_{a_i } $同余，由上可知$b$必与$ar_i $同余.所以$ar_1 ,ar_2 ,\cdots ,ar_N $是模$n$的既约剩余代表系.

定理$6$(欧拉-费马($Fermat$)) 设$(a,n)=1,N=\varphi (n)$，则

$$a^N \equiv 1\pmod{n} .$$

证明 取模$n$的一个既约剩余代表系$r_1 ,r_2 ,\cdots ,r_N $.由于$(a,n)=1$，$ar_1 ,ar_2 ,\cdots ,ar_N $也是一个既约剩余代表系，而且$ar_i \equiv r_{a_i } \pmod{n} $，$a_1 ,a_2 ,\cdots ,a_N $是$1,2,\cdots ,N$的一个排列.这$N$个同余式连乘得

$$\prod \limits_{i=1}^N ar_i \equiv \prod \limits_{i=1}^N r_{a_i } =\prod \limits_{i=1}^N r_i \pmod{n} ,$$

$$a^N\prod \limits r_i \equiv \prod \limits r_i \pmod{n},$$

根据互素性质$4)$，$\prod \limits r_i $与$n$互素，根据同余式性质$4$，消去$\prod \limits r_i $得$a^N \equiv 1\pmod{n} $.$\blacksquare $

定理$6$的特殊情况是，$n=p$为一素数，$\varphi (p)=p-1$.$(a,p)=1$即$p\nmid a$，于是

$$a^{p-1}\equiv 1\pmod{p} .$$

这就是费马定理.费马定理也可写成：对任意素数$p$和任意整数$a$，恒有

$$a^p \equiv a\pmod{p} .$$

在这里顺便介绍一下指数的概念.设$a,n$为互素的一对整数，$n\geq 1$，则存在一个最小正整数$m$使得

$$a^m \equiv 1\pmod{n} ,$$

$m$叫做$a$模$n$的指数.指数的存在由欧拉-费马定理得到保证.因为使$a^k\equiv 1\pmod{n} $的正整数$k$存在，$\varphi (n)$就是一个.$k$的存在也可直接看出.因为$a,a^2,a^3,\cdots $中必有两个同余的，设$a^j \equiv a^i \pmod{n} $，$j > i$，消去$a^i$使$a^{j-i}\equiv 1\pmod{n} $.应用除法算式可以证明指数的一个基本性质：

$a^k \equiv 1\pmod{n} \Leftrightarrow m\mid k$，$m$为$a~mod~n$的指数.特别地，指数$m\mid \varphi (n)$.

例 $~2~mod~17$的指数为$8$，$3~mod~17$的指数为$16=\varphi (17)$.计算$3^{157}~mod~17$，可应用指数.

首先，$157\equiv 13\pmod{16} $，$3^{157}\equiv 3^{13}\pmod{17} $，而$3^{13}\equiv 3^8\cdot 3^5\equiv -3^5\equiv -5\pmod{17} $.

个人思路：首先先分解$157=9\times 16+13$.根据欧拉-费马定理，令$a=3^k$，$n=17$，则$(a,n)=(3^k,17)=1$，对任意的整数$k$来说.$N=\varphi (n)=\varphi (17)=17-1=16$，因此有$a^N=(3^k)^{16} \equiv 1\pmod{17} $成立，也即是说$a^{N}\cdot 3^{13}=(3^k)^{16}\cdot 3^{13} \equiv 3^{13}\pmod{17} $成立.这时，可令$k=9$，则有$3^{157}=(3^9)^{16}\cdot 3^{13} \equiv 3^{13}\pmod{17} $成立.因为$17\times 386=6562=6561+1=3^8+1$，所以$3^8\equiv -1\pmod{17} $.因为$3^5=243=17\times 16+5$，所以$3^5\equiv 5\pmod{17} $.因此有$3^{13}\equiv 3^8\cdot 3^5\equiv -3^5\equiv -5\pmod{17} $.

下面我们来计算欧拉函数.

引理$1$$~p$为素数，$\varphi (p^m)=p^m (1-\dfrac{1}{p} )$，$m\geq 1$.

证明 因为在$S=\lbrace 0,1,2,\cdots ,p^m-1 \rbrace$中除去$p$的倍数，剩下的都与$p$互素，而$S$中$p$的倍数恰好有$\dfrac{p^m}{p} $个，因此$S$中与$p$互素的整数的个数为$p^m-p^{m-1}$.

引理$2$设$n=n_1 \times n_2 $，$(n_1 ,n_2 )=1$，$n_i \geq 1$，则

$$\varphi (n)=\varphi (n_1 )\times \varphi (n_2 ).$$

证明$\varphi (n_i )$简记作$N_i $，$i=1,2$.设$r_1 ,\cdots$,$ r_{N_1}$和$s_1,\cdots $,$s_{N_2}$分别为模$n_1$和模$n_2$的既约剩余代表系.根据孙子定理，存在整数$t_{ij}$，$i=1,\cdots ,N_1$，$j=1,\cdots ,N_2$使得

$$t_{ij}\equiv r_i\pmod{n_1},$$

$$t_{ij}\equiv s_j\pmod{n_2}.$$

证明$t_{ij}$为模$n_1n_2$的一个既约剩余代表系.首先，由于$(r_i,n_1)=1$，有$(t_{ij},n_1)=1$.由于$(s_j,n_2)=1$，有$(t_{ij},n_2)=1$.因而$(t_{ij},n_1n_2)=1$.其次$t_{ij}$互不同余.假设若$t_{ij}\equiv t_{kl}\pmod{n_1n_2}$，一方面有$t_{ij}\equiv t_{kl}\pmod{n_1}$，它化为$r_i\equiv r_k\pmod{n_1}$，从而$i=k$，另一方面有$t_{ij}\equiv t_{kl}\pmod{n_2}$，它化为$s_j\equiv s_l\pmod{n_2}$，从而$j=l$.所以$t_{ij}$互不同余$\pmod{n_1n_2}$.最后设$a$为任一与$n$互素的整数，根据$r_i$和$s_j$的定义，存在$r_i$和$s_j$使得$a\equiv r_i\pmod{n_1}$，$a\equiv s_j\pmod{n_2}$，于是根据孙子定理有$a\equiv t_{ij}\pmod{n}$(不懂).所以$t_{ij}$是模$n$的一个既约代表系.这就证明了$\varphi (n)=\varphi (n_1)\times \varphi (n_2)$.$\blacksquare$

定理$7$设$n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$，$p_1,p_2,\cdots ,p_r$为不同素数，$e_i \geq 1$，则

$$\varphi (n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots (1-\dfrac{1}{p_r}).$$

应用引理$1$和引理$2$对$r$作归纳法即得.

最后证明欧拉函数的一个性质

$$\underset{d\mid n}{\sum}\varphi (d)=n.$$

设$S=\lbrace 0,1,\cdots ,n-1\rbrace$，对每个$d\mid n$，令$S_d =\lbrace x\in S\mid (x,n)=d\rbrace$.显然$S=\underset{d\mid n}{\bigcup}S_d$是$S$的一个划分.其次，映射

$$\eta :x\mapsto \dfrac{x}{d},x\in S_d$$

是$S_d$到$S(\dfrac{n}{d})=\lbrace 0,1,2,\cdots ,\dfrac{n}{d}-1\rbrace$的一个单射.而且象集$\eta (S_d)$恰好是$S(\dfrac{n}{d})$中与$\dfrac{n}{d}$互素的整数全体.所以$\mid S_d\mid =\varphi (\dfrac{n}{d})$，由此得

$$n=\underset{d\mid n}{\sum}\mid S_d\mid =\underset{d\mid n}{\sum} \varphi (\dfrac{n}{d}),$$

当$d$走遍$n$的因子时，$\dfrac{n}{d}$刚好走遍$n$的因子，所以

$$\underset{d\mid n}{\sum} \varphi (d)=\underset{d\mid n}{\sum} \varphi (\dfrac{n}{d}).$$