Content

Euler’s phi function

先引入记号 $\phi(m)$,

$\phi(m)=\Big\lvert\{a\mid 1\le a\le m \text{ and }\gcd{(a,m)}=1\}\Big\rvert$

$\phi(m)$ 表示在 $[1,m]$ 之间和 $m$ 互质的整数的数量，即模 $m$ 缩系的大小。

Parity

除了 $\phi(2)=1$ 是奇数以外，$\phi(m)$ 总是偶数。这是因为当 $m\gt2\text{, }\gcd{(a,m)}=1\implies \gcd{(m-a,m)}=1$。而且 $a\not\equiv m-a$，否则 $m=2a$ 和 $\gcd{(a,m)}=1$ 矛盾。这表示和 $m$ 互质的整数总是成对存在。

Lemma

假如 $\gcd{(a,m)}=1$，而且

$\begin{array}{} 1\le b_1 \lt b_2 \lt\ldots\lt b_{\phi(m)} \lt m & \gcd{(b_i, m)}=1 \end{array}$

那么由整数

$b_1a,b_2a,\ldots, b_{\phi(m)}a \pmod m$

所构成的集合和

$b_1,b_2,\ldots, b_{\phi(m)} \pmod m$

所构成的集合相等。换一种说法就是给定模 $m$ 缩系 $B$，对于满足 $p\nmid a$ 的整数 $a$，$C={ ab \mid b\in B}$ 也是一个模 $m$ 缩系。证明过程和上一篇大同小异。

Euler’s Theorem

假如 $\gcd{(a,m)}=1$，那么 $a^{\phi(m)}\equiv 1\pmod m$

证明过程和上一篇大同小异。

Chinese remainder theorem

已知整数 $m,n$ 满足 $\gcd{(m,n)}=1$。对于任意整数 $b,c$ 以下线性同余(simultaneous congruences) $\begin{array}{} x\equiv b\pmod m & \text{ and }&x\equiv c\pmod n \end{array}$

在 $0\le x\lt mn$ 之间有且只有一个解。

线性同余方程组的解法同样也是中国剩余定理的证明。稍作换元，令 $x=mt+b$ 代入第二个同余式

$mt+b\equiv c\pmod n\implies mt\equiv c-b\pmod n$

这个时候可以用解线性同余的方法得到 $mt\equiv c-b\pmod n$ 的解，而且模 $n$ 互不同余的解只有一个；换句话说就是在 $0\le t\le n-1$ 之间只有一个解。由于

$\begin{array}{} 0\le b\le m-1 & 0\le c\le n-1 \end{array}$

所以

$b\le mt+b \le mn-m + m-1\lt mn\implies b\le x\lt mn$

因此线性同余方程组在 $0\le x\lt mn$ 之间有且只有一个解，这个解式为 $x\equiv mt+b\pmod {mn}$。

Phi function formulas

Value of prime power arguments

已知 $p$ 是素数，证明 $\phi(p^k)=p^k-p^{k-1}$.

考虑不大于 $p^k$ 而且能够被 $p$ 整除的整数

$p, 2p, 3p,\ldots,(p^{k-1}-1)p,p^{k-1}p$

一共有 $p^{k-1}$ 个。因此排除能被 $p$ 整除的整数，剩下的整数和 $p^k$ 互质，即$\phi(p^k)=p^k-p^{k-1}$。

The function is multiplicative

假如 $\gcd{(m,n)}=1$, 那么 $\phi(mn)=\phi(m)\phi(n)$。

首先令

$\begin{array}{} A=\{a\mid0\le a\lt m\text{ and }\gcd{(a,m)}=1\} & |A|=\phi(m) \end{array}$ $\begin{array}{} B=\{b\mid0\le b\lt n\text{ and }\gcd{(b,n)}=1\} & |B|=\phi(n) \end{array}$ $\begin{array}{} C=\{c\mid0\le c\lt mn\text{ and }\gcd{(c,mn)}=1\} & |C|=\phi(mn) \end{array}$

在 $m,n$ 互质的条件下，利用中国剩余定理构造映射 $f:A\times B\to C$。接下来的目标是证明 $f$ 是一个双射；双射的充分必要条件是单射(injective)+满射(surjective)。

单射指函数将定义域(domain)内不同的元素映射到陪域(codomain)的不同元素。首先设 $(a_1,b_1),(a_2,b_2)\in A\times B$。假如 $f(a_1,b_1)=f(a_2,b_2)$，可知线性同余方程组满足

$\begin{cases} x\equiv a_1\pmod m\\ x\equiv b_1\pmod n\\ \end{cases} \text{ and } \begin{cases} x\equiv a_2\pmod m\\ x\equiv b_2\pmod n\\ \end{cases}$ $\begin{array}{} a_1\equiv a_2\pmod m & b_1\equiv b_2\pmod n \end{array}$

因为 $0\le a_1,a_2\lt m, 0\le b_1,b_2\lt n$，所以 $a_1=a_2,b_1=b_2$，$f$ 是一个单射。

满射指对于陪域的每一个元素 $y$，在定义域中至少有一个元素 $x$ 满足 $f(x)=y$。取任意 $c_1\in C$，存在整数 $a’,b’$ 使得

$\begin{array}{} a'\equiv c_1\pmod m & b'\equiv c_1\pmod n\\ \end{array}$ $\begin{array}{} 0\le a'\lt m & 0\le b'\lt n \end{array}$

所以 $(a’,b’)\in A\times B$，$f$ 是一个满射。结合前面的证明，$f$ 是一个双射，因此双射 $f$ 的定义域 $A\times B$ 和陪域 $C$ 的势(cardinality)相等

$|A\times B|=|C|$

因此 $\phi(mn)=\phi(m)\phi(n)$。

Euler’s product formula

已知整数 $m=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}$

$\begin{aligned} \phi(m)&=\prod_{i=1}^n(p_i^{k_i}-p_i^{k_i-1})=\prod_{i=1}^np_i^{k_i}(1-\dfrac{1}{p_i})\\ &=m\prod_{i=1}^n(1-\dfrac{1}{p_i})\\ \end{aligned}$

Exercise

10.1

(a) & (b)

令 $B=b_1b_2\ldots b_{\phi(m)}$，证明 $B\equiv1\pmod m\text{ or }B\equiv-1\pmod m$

考虑 $x^2\equiv 1\pmod m$。假如 $x\equiv a\pmod m$ 是方程的解，因为

$(m-a)^2\equiv m^2-2am+a^2\equiv a^2\equiv 1\pmod m$

那么 $x\equiv m-a\pmod m$ 也是方程的解。而且

$a(m-a)\equiv am-a^2\equiv -1 \pmod m$

所以 $x^2\equiv 1\pmod m$ 至少有两个解为 $x\equiv 1\pmod m\text{ and }x\equiv m-1\pmod m$。

前面已经知道了，$b_i$ 有且只有一个模 $m$ 乘法逆元 $x\in{b_1,b_2,\ldots,b_{\phi(m)}}$；如果 $x=b_i$ 本身，那么 $b_j=m-b_i$ 的模 $m$ 乘法逆元也是 $b_j$，而且 $b_ib_j\equiv -1\pmod m$。

综上所述，$B=b_1b_2\ldots b_{\phi(m)}$ 的值取决于 $x^2\equiv 1\pmod m$ 的解的数量：如果有 奇数对 解，那么 $B\equiv-1\pmod m$；否则 $B\equiv1\pmod m$。前面提到的多项式的模 $p$ 同余根定理在 $n=2$ 时的情况，以及威尔逊定理，都是这个结论在 $m$ 是素数的特例。

10.3

卡迈克尔数(Carmichael Number)是一个合数 $m$, 满足 $\forall a \text{ with }\gcd{(a,m)}=1\text{ s.t. } a^{m-1}\equiv 1\pmod m$

对于所有能够整除 $m$ 的素数 $p$，用费马小定理验证 $a^{m-1}\equiv 1\pmod p$ 并解释为什么这是判断 $m$ 是卡迈克尔数的充分条件。

首先，$\gcd{(a,b)}=1, a\mid c\text{ and }b\mid c\implies ab\mid c$，因为

$\begin{aligned} \gcd{(a,b)}=1&\implies ax+by=1\\ &\implies cax+cby = c\\ &\implies kb\cdot ax+ ia\cdot by=c\\ &\implies ab(kx+iy)=c\implies ab\mid c \end{aligned}$

所以若 $m=p_1p_2\ldots p_n\text{ and }p_i\not=p_j$，假如 $\forall a\text{ with }\gcd{(a,m)}=1\rightarrow a^{m-1}\equiv 1\pmod {p_i}$，那么 $p_i\mid {(a^{m-1}-1)}$，即 $p_1p_2\ldots p_n\mid {(a^{m-1}-1)}$，换言之 $a^{m-1}\equiv 1\pmod m$。

你认为有无穷多个卡迈克尔数吗？

判断卡迈克尔数的充分条件：假如 $m=p_1p_2\ldots p_n\text{ and }p_i\not=p_j$，$(p_i-1)\mid {(m-1)}$。

11.2

(a)

解释为何当 $m\ge3$ 时 $\phi(m)$ 的值总是偶数。

$\phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$

假如 $m\ge3,p=2$，那么 $k\ge2$，$\phi(2^k)=2\cdot2^{k-2}$.

假如 $p\not=2$，那么 $p$ 是奇数，$p-1$ 是偶数，$\phi(m)$ 的值是偶数。

(b)

描述满足 $\phi(m)$ 不能被 $4$ 整除时的 $m$。

先考虑 $m=p^k$。

显然 $p\not=2$。因为 $p-1\equiv 0\pmod 4\to 4\mid {p^{k-1}(p-1)}$为真，所以其逆否命题 $4\nmid {p^{k-1}(p-1)}\to p-1\not\equiv 0\pmod 4$ 也为真。

所以当 $m=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}$，要使得$\phi(m)$ 不能被 $4$ 整除，就要满足 $\forall p_i, p_i-1\not\equiv 0\pmod 4$。

11.11

(a)

找出至少 $5$ 个满足 $\phi(n)=160$ 的整数 $n$

$160=2^5\times5$ $\begin{aligned} 2^4\times10&\to32\times11=352\\ 16\times10&\to17\times11=187\\ 2^3\times2\times10&\to2^4\times3\times11=528\\ 2^2\times40&\to8\times41=328\\ 4\times40&\to5\times41=205\\ \end{aligned}$

(b)

已知 $\phi(n)=1000$，列出所有可能整除 $n$ 的素数。

$1000=2^3\times5^3$

枚举 $4\times4=16$ 种组合，判断 $2^i5^j+1$ 的值是否是一个素数

$p=2,3,5,11,\cancel{41},101,251$

(c)

找出所有满足 $\phi(n)=160$ 的整数 $n$

$\begin{aligned} 2^1\times4\cdot5^3&\to2^2\times5^4=2500\\ 2\times4\cdot5^3&\to3\times5^4=1875\\ 100\times10&\to101\times11=1111\\ 4\cdot5^2\times10&\to125\times11=1375\\ 4\times250&\to5\times251=1255\\ 2^2\times250&\to8\times251=2008\\ \end{aligned}$

主观上可以把这类问题看作是搜索：为求问题的答案 $f(m)$，对 $m$ 进行因式分解，根据结果构造出素数 $p$，递归地求 $f(\dfrac{m}{p})$，之后再回溯得到问题的答案。

11.12

分别找出满足以下条件的整数 $n$

$\begin{array}{} \text{(a) }\phi(n)=\dfrac{n}{2} & \text{(b) }\phi(n)=\dfrac{n}{3} & \text{(c) }\phi(n)=\dfrac{n}{6} \end{array}$

令 $\phi(n)=n\displaystyle\prod_{i=1}^k(1-\dfrac{1}{p_i})=\dfrac{n}{2}$，得到 $\displaystyle\prod_{i=1}^k\dfrac{p_i-1}{p_i}=\dfrac{1}{2}$。可以断言只有 $p=2$ 满足条件，否则设整除 $n$ 的最大的素数 $p’>2$，在分母引入的素数 $p’$ 不能整除分子 $\displaystyle\prod(p_i-1)$，因此不存在这样的 $p’$。所以满足条件 (a) 的整数为 $n=2^k$。满足条件 (b) 的整数为 $n=2^i3^j$。可能不存在满足条件 (c) 的整数。

11.13

求 $a^{1000}$ 的最后四位数字。

换句话说就是求 $a^{1000}\pmod {10000}$。这个问题的特殊性在于

$10000=2^4\cdot5^4$

$\phi(2^4)=8$ 以及 $\phi(5^4)=500$ 能够整除 $1000$。由算术基本定理可知，任意整数属于以下的一种情况

能够同时被 $2,5$ 整除
能够被 $2$ 整除，但不能被 $5$ 整除
能够被 $5$ 整除，但不能被 $2$ 整除
不能被 $2$ 或 $5$ 整除

对应地，由欧拉定理

$\begin{aligned} a^{1000}\equiv a^8 &\equiv 1\pmod {2^4}\text{, if }\gcd{(a,2^4)}=1\\ a^{1000}\equiv a^{500} &\equiv 1\pmod {5^4}\text{, if }\gcd{(a, 5^4)}=1\\ \end{aligned}$

令 $x=a^{1000}$ 可知 $a^{1000}\pmod {2^4}$ 和 $a^{1000}\pmod {2^5}$ 的值对应地属于以下的一种情况

$\begin{cases} x\equiv 0\pmod{2^4}\\ x\equiv 0\pmod{5^4}\\ \end{cases} \begin{cases} x\equiv 0\pmod{2^4}\\ x\equiv 1\pmod{5^4}\\ \end{cases} \begin{cases} x\equiv 1\pmod{2^4}\\ x\equiv 0\pmod{5^4}\\ \end{cases} \begin{cases} x\equiv 1\pmod{2^4}\\ x\equiv 1\pmod{5^4}\\ \end{cases}$

用中国剩余定理分别解得

$\begin{array}{} x\equiv0\pmod {2^4\cdot5^4} &x\equiv9376\pmod {2^4\cdot5^4} & x\equiv625\pmod {2^4\cdot5^4} & x\equiv1\pmod {2^4\cdot5^4} & \end{array}$

所以

$a^{1000}\pmod{10000}= \begin{cases} 0&\text{, if }2\mid a\text{ and }5\mid a\\ 9376&\text{, if }2\mid a\text{ and }5\nmid a\\ 625&\text{, if }2\nmid a\text{ and }5\mid a\\ 1&\text{, if }2\nmid a\text{ and }5\nmid a\\ \end{cases}$

A Friendly Introduction to Number Theory Chapter 10~11

欧拉函数(Euler's phi function)