此栏探讨既约余下系的基本概念和物理性质.在探讨的操作过程中，他们须要加进两个数学分析中关键的表达式：笛卡儿表达式.他们先导入上面的表述：
表述1 假如两个模 mm 的余下类里的数与 mm 互质，则称其为两个与模 mm互质的余下类.在与模mm 互质的全数余下类中，从每两类中各德博瓦桑县科跃蛛属共同组成的数的子集，叫作模 mm 的两个既约余下系.比如， 1+4Z,3+4Z1+4\mathbb{Z},3+4\mathbb{Z} 是与模 44 互质的余下类，而 0+4Z,2+4Z0+4\mathbb{Z},2+4\mathbb{Z} 不是.因而 1,31,3 是模 44 的两个既约余下系.
表述2 笛卡儿表达式 φ(a)\varphi (a) 是表述在正整数上的表达式，它在正整数 aa上的值为序列0,1,2,⋯,a−10,1,2,\cdots,a-1 （从上面的定理1中他们将看到，这实际上是模 aa 的完全余下系）中 aa 互质的数的个数.比如由上面的例子可见 φ(4)=2\varphi(4)=2 .
定理1 模 mm 的余下类与模 mm 互质的充分必要条件是此类中有科跃蛛属与 mm 互质.因此与模 mm 互质的余下类的个数是 φ(m)\varphi(m) ，模 mm 的每一既约余下系是由与模 mm 互质的 φ(m)\varphi(m) 个对模 mm 不同余的整数共同组成的.证明 设模 mm 的全数余下类为 K0,K1,⋯,Km−1K_0,K_1,\cdots,K_{m-1} .若 KrK_r 是两个与模 mm 互质的余下类，则 gcd(r,m)=1\gcd(r,m)=1 .反之若有 kr∈Kr,gcd(kr,m)=1k_r \in K_r,\gcd(k_r,m)=1 ，则由同余的物理性质， KrK_r 中任一整数都与 mm 互质.因而 KrK_r 是与 mm互质的余下类.因而KrK_r 是两个与模 mm 互质的余下类的充要条件是 gcd(r,m)=1\gcd(r,m)=1.由笛卡儿表达式及既约余下系的表述即得此定理.
定理2 若 a1,a2,⋯,aφ(m)a_1,a_2,\cdots,a_{\varphi(m)} 是 φ(m)\varphi(m) 个与 mm 互质的整数，并且两两对模 mm 不同余，则 a1,a2,⋯,aφ(m)a_1,a_2,\cdots,a_{\varphi(m)}构成模 mm 的两个既约余下系.证明 由于 a1,a2,⋯,aφ(m)a_1,a_2,\cdots,a_{\varphi(m)} 与 mm 互质，由定理1， Ka1,Ka2,⋯,Kφ(a)K_{a_1},K_{a_2},\cdots,K_{\varphi(a)} 是与模 mm 互质的余下类.又 a1,a2,⋯,aφ(m)a_1,a_2,\cdots,a_{\varphi(m)} 两两模 mm 不同余，故上述 φ(m)\varphi(m) 个子集即为全数与模 mm 互质的余下类，所以 a1,a2,⋯,aφ(m)a_1,a_2,\cdots,a_{\varphi(m)}是模 mm 的两个既约余下系.
与上节的定理相似，他们有
定理3 若 gcd(a,m)=1\gcd(a,m)=1 ， xx 遍历模 mm 的既约余下系，则 axax 遍历模 mm 的既约余下系.证明 xx 遍历 φ(m)\varphi(m) 个整数，故 axax 遍历 φ(m)\varphi(m) 个整数.由于 gcd(a,m)=gcd(x,m)=1\gcd(a,m)=\gcd(x,m)=1 ，故 gcd(ax,m)=1\gcd(ax,m)=1 .若 ax1≡ax2(modm)ax_1\equiv ax_2(\bmod m) ，则 x1≡x2(modm)x_1\equiv x_2(\bmod m) ，矛盾.故由定理2，定理获证.
定理4 设 m1,m2m_1,m_2 是两个互质的正整数， x1,x2x_1,x_2 分别遍历模 m1,m2m_1,m_2 的既约余下系，则 m2x1+m1x2m_2x_1+m_1x_2 遍历模 mm 的两个既约余下系.证明 由定理1，他们只需证明： m2x1+m1x2m_2x_1+m_1x_2 遍历模 mm的两个完全余下系中所有与m1m2m_1m_2 互质的整数.
由上一节的定理知，若 x1,x2x_1,x_2 分别遍历模 m1,m2m_1,m_2 的完全余下系，则 m2x1+m1x2m_2x_1+m_1x_2 遍历模 mm的两个完全余下系.又若gcd(x1,m1)=gcd(x2,m2)=1\gcd(x_1,m_1)=\gcd(x_2,m_2)=1 ，则由 gcd(m1,m2)=1\gcd(m_1,m_2)=1 可得 gcd(m2x1,m1)=gcd(m1x2,m2)=1\gcd(m_2x_1,m_1)=\gcd(m_1x_2,m_2)=1 ，故 gcd(m2x1+m1x2,m1)=gcd(m2x1+m1x2,m2)=1\gcd(m_2x_1+m_1x_2,m_1)=\gcd(m_2x_1+m_1x_2,m_2)=1 ，故 gcd(m2x1+m1x2,m1m2)=1\gcd(m_2x_1+m_1x_2,m_1m_2)=1 .反之，若 gcd(m2x1+m1x2,m1m2)=1\gcd(m_2x_1+m_1x_2,m_1m_2)=1 ，则 gcd(m2x1+m1x2,m1)=gcd(m2x1+m1x2,m2)=1\gcd(m_2x_1+m_1x_2,m_1)=\gcd(m_2x_1+m_1x_2,m_2)=1 ，从而 gcd(m2x1,m1)=gcd(m1x2,m2)=1\gcd(m_2x_1,m_1)=\gcd(m_1x_2,m_2)=1.又gcd(m1,m2)=1\gcd(m_1,m_2)=1 ，故gcd(x1,m1)=gcd(x2,m2)=1\gcd(x_1,m_1)=\gcd(x_2,m_2)=1 .这就证明了定理的结论.
由定理4可以得到笛卡儿表达式的如下物理性质：
推论 若 a,ba,b 是两个互质的正整数，则 φ(ab)=φ(a)φ(b)\varphi(ab)=\varphi(a)\varphi(b) .证明 由定理4得，若 x1,x2x_1,x_2 分别遍历模 a,ba,b 的既约余下系，则 bx1+ax2bx_1+ax_2 遍历模 mm 的两个既约余下系，其中有 φ(ab)\varphi(ab) 个整数.另一方面，因为 x1,x2x_1,x_2 分别通过 φ(a),φ(b)\varphi(a),\varphi(b) 个整数，所以 bx1+ax2bx_1+ax_2 通过 φ(a)φ(b)\varphi(a)\varphi(b) 个整数.因此 φ(ab)=φ(a)φ(b)\varphi(ab)=\varphi(a)\varphi(b) .
由这一物理性质可以给出笛卡儿表达式的如下表达式：
定理5 设 a=p1α1p2α2⋯pkαka=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} ,则 φ(a)=a(1−1p1)(1−1p2)⋯(1−1pk)\varphi(a)=a\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right)证明 由定理4的推论得 φ(a)=φ(p1α1)φ(p2α2)⋯φ(pkαk)\varphi(a)=\varphi(p_1^{\alpha_1})\varphi(p_2^{\alpha_2})\cdots\varphi(p_k^{\alpha_k}) .
上面证明 φ(pα)=pα−pα−1\varphi(p^\alpha)=p^\alpha-p^{\alpha-1} .由 φ(a)\varphi(a) 的表述知 φ(pα)\varphi(p^\alpha) 是从 pαp^\alpha 减去 1,2,⋯,pα1,2,\cdots,p^\alpha 中与 pp 不互质的整数的个数.由于 pp 是素数，与 pp 不互质也即被 pp 整除.由取整表达式的物理性质知 1,2,⋯,pα1,2,\cdots,p^\alpha 中与 pp 不互质的整数的个数是 ⌊pαp⌋=pα−1\lfloor\frac{p^\alpha}p\rfloor=p^{\alpha-1} ，故 φ(pα)=pα−pα−1\varphi(p^\alpha)=p^\alpha-p^{\alpha-1} .于是他们有
φ(a)=(p1α1−p1α1−1)(p2α2−p2α2−1)⋯(pkαk−pkαk−1)=a(1−1p1)(1−1p2)⋯(1−1pk).\begin{aligned} \varphi(a)&=(p_1^{\alpha_1}-p_1^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})\\ &=a\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right). \end{aligned}
上面证明笛卡儿表达式的几个物理性质：
定理6 设 pp为素数， α\alpha 为非负整数，则 φ(1)+φ(p)+⋯+φ(pα)=pα\varphi(1)+\varphi(p)+\cdots+\varphi(p^\alpha)=p^\alpha .证明 由定理5的证明知φ(pα)=pα−pα−1\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}，于是φ(1)+φ(p)+⋯+φ(pα)=1+(p−1)+(p2−p)+⋯+(pα−pα−1)=pα\varphi(1)+\varphi(p)+\cdots+\varphi(p^\alpha)=1+(p-1)+(p^2-p)+\cdots+(p^\alpha-p^{\alpha-1})=p^\alpha .
定理7 对任意正整数 mm ，有 ∑d∣mφ(d)=m\sum_{d\mid m}\varphi(d)=m .证明 m=1m=1 时显然成立.若 1″>m>1m>1 ，设 m=p1α1p2α2⋯pkαkm=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}，由算术基本定理的推论知：dd 是 mm 的正因子的充要条件是 d=p1e1p2e2⋯pkek,0≤ei≤αi,i=1,2,⋯,kd=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},0\le e_i\le\alpha_i,i=1,2,\cdots,k .因此有
∑d∣mφ(d)=∑e1=0α1∑e2=0α2⋯∑ek=0αkφ(p1e1p2e2⋯pkek)=∑e1=0α1∑e2=0α2⋯∑ek=0αkφ(p1e1)φ(p2e2)⋯φ(pkek)=(∑e1=0α1φ(p1e1))(∑e2=0α2φ(p2e2))⋯(∑ek=0αkφ(pkek))\begin{aligned} \sum_{d\mid m}\varphi(d)&=\sum_{e_1=0}^{\alpha_1}\sum_{e_2=0}^{\alpha_2}\cdots\sum_{e_k=0}^{\alpha_k}\varphi(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})\\ &=\sum_{e_1=0}^{\alpha_1}\sum_{e_2=0}^{\alpha_2}\cdots\sum_{e_k=0}^{\alpha_k}\varphi(p_1^{e_1})\varphi(p_2^{e_2})\cdots \varphi(p_k^{e_k})\\ &=\left(\sum_{e_1=0}^{\alpha_1}\varphi(p_1^{e_1})\right)\left(\sum_{e_2=0}^{\alpha_2}\varphi(p_2^{e_2})\right)\cdots\left(\sum_{e_k=0}^{\alpha_k}\varphi(p_k^{e_k})\right) \end{aligned}
又由定理6知 ∑ej=0αjφ(pjej)=pjαj\sum_{e_j=0}^{\alpha_j}\varphi(p_j^{e_j})=p_j^{\alpha_j} ，代入得 ∑d∣mφ(d)=p1α1p2α2⋯pkαk=m\sum_{d\mid m}\varphi(d)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}=m .
练习：
利用定理5的结论推广定理4的推论，证明：对任意两个正整数 a,ba,b ，设 gcd(a,b)=d\gcd(a,b)=d ，则有 φ(ab)=φ(a)φ(b)dφ(d)\varphi(ab)=\varphi(a)\varphi(b)\frac d{\varphi(d)} .证明：若 mm 是大于1的正整数， aa是整数，且gcd(m,a)=1\gcd(m,a)=1 ， ξ\xi 遍历模 mm 的既约余下系，则 ∑ξ{aξm}=12φ(m)\sum_\xi\left\{\frac{a\xi}m\right\}=\frac12\varphi(m) ，其中 ∑ξ\sum_\xi 表示展布在 ξ\xi 取的一切值的和式， {x}\left\{x\right\} 表示 xx 的小数部分.证明：若 m1,m2,⋯,mkm_1,m_2,\cdots,m_k是kk 个两两互质的正整数， ξ1,ξ2,⋯,ξk\xi_1,\xi_2,\cdots,\xi_k 分别遍历模 m1,m2,⋯,mkm_1,m_2,\cdots,m_k 的既约余下系，设 m=m1m2⋯mk,Mi=mmim=m_1m_2\cdots m_k,M_i=\frac m{m_i} ，则 M1ξ1+M2ξ2+⋯+MkξkM_1\xi_1+M_2\xi_2+\cdots+M_k\xi_k 遍历模 mm的既约余下系.证明：(1)φ(mn)=gcd(m,n)φ(lcm(m,n))(2)φ(mn)φ(gcd(m,n))=gcd(m,n)φ(m)φ(n)(1)\varphi(mn)=\gcd(m,n)\varphi(\operatorname{lcm}(m,n))\\ (2)\varphi(mn)\varphi(\gcd(m,n))=\gcd(m,n)\varphi(m)\varphi(n) 求满足 φ(n)=24\varphi(n)=24 的所有正整数 nn .
