全然余下系
内积是一类十分特定的形式语言，假如一类形式语言具备自反、对称、传达等特性，所以这是一类内积
子集依照内积可分成对角彼此之间平行的子集。 有理数的域论亲密关系是三个内积。
取值自然数 mm，全体人员有理数可依照模mm 与否域论分成若干个对角不平行的子集，使每三个子集中的任一三个自然数对模 mm 很大域论，而归属于相同子集的任一三个有理数对模 mm 不域论，每三个这种的子集称作模 mm 的域论类或余下类。
不等式 1
对取值的自然数 mm ，有且恰有 mm 个相同的模 mm 的余下类。
证明：依照带余除法，对任一有理数 aa ，都有 a=qm+r,0≤r<ma=qm+r,0\leq r<m ，也是说任何三个有理数模 mm 必然与 {0,1,2,…,m−1}\left\{ 0,1,2,…,m-1 \right\} 中的三个域论，而且这 mm 个有理数模 mm 彼此之间域论。所以模 mm 的余下类有且恰有 mm 个。
模 mm 的 mm 个余下类可分别记为 [i][i] ， ii 为该余下类中有理数除 mm 所得的余数，可分别如下表示：
[0]={…,−2m,−m,0,m,2m,…}[0]=\left\{ …,-2m,-m,0,m,2m,… \right\} [1]={…,−2m+1,−m+1,1,m+1,2m+1,…}[1]=\left\{ …,-2m+1,-m+1,1,m+1,2m+1,… \right\} [2]={…,−2m+2,−m+2,2,m+2,2m+2,…}[2]=\left\{ …,-2m+2,-m+2,2,m+2,2m+2,… \right\} ………… [m−1]={…,−2m+(m−1),−m+(m−1),m−1,m+(m−1),2m+(m−1),…}[m-1]=\left\{ …,-2m+(m-1),-m+(m-1),m-1,m+(m-1),2m+(m-1),… \right\}定义：在有理数模 mm 的所有余下类中各取三个代表元 a1,a2,…,am,(ai∈[i−1],i=1,2,…,m)a_1,a_2,…,a_m,(a_i\in [i-1],i=1,2,…,m) ，则称 a1,a2,…,ama_1,a_2,…,a_m 为模 mm 的全然余下系。全然余下系 0,1,2,…,m−10,1,2,…,m-1 称作最小非负全然余下系。
通常情况下，以 ZmZ_m 表示由 mm 的最小非负全然余下系子集 Zm={0,1,2,…,m−1}Z_m=\left\{ 0,1,2,…,m-1 \right\} 。 ZmZ_m 中的加法、减法、乘法都是模 mm 意义下的运算。
不等式 2
设 mm 是自然数，有理数 aa 满足 gcd(a,m)=1gcd(a,m)=1 ， bb 是任一有理数。 若 xx 遍历模 mm 的三个全然余下系，则 ax+bax+b 也遍历模 mm 的三个全然余下系。（ xx 为三个子集）
证明：设a1,a2,…,ama_1,a_2,…,a_m 为模 mm 的全然余下系。依照全然余下系的定义，这组有理数模 mm 对角不域论。要证明 aa1+b,aa2+b,…,aam+baa_1+b,aa_2+b,…,aa_m+b 也是模 mm 的一组全然余下系，只需要证明这 mm 个数模 mm 对角不域论即可。
若存在 aia_i 和 aja_j ， i≠ji\ne j ，使 aai+b≡aaj+b(modm)aa_i+b\equiv aa_j+b(modm) ，则有 m|a(ai−aj)m|a(a_i-a_j) 。由于gcd(a,m)=1gcd(a,m)=1，所以 m|(ai−aj)m|(a_i-a_j) ，即有 ai≡aj(modm)a_i\equiv a_j(modm) 。这与 a1,a2,…,ama_1,a_2,…,a_m 模 mm 对角不域论矛盾。因此 aa1+b,aa2+b,…,aam+baa_1+b,aa_2+b,…,aa_m+b 模 mm 对角不域论。不等式得证。
不等式 3
设 m1,m2m_1,m_2 是三个互素的自然数。假如 xx 遍历模 m1m_1 的三个全然余下系， yy 遍历模 m2m_2 的三个全然余下系，则 m1y+m2xm_1y+m_2x 遍历模 m1m2m_1m_2 的三个全然余下系。
证明：只需要证明所有的 m1y+m2xm_1y+m_2x 模 m1m2m_1m_2 对角彼此之间域论即可。 事实上，若有理数 x1,x2x_1,x_2 归属于模 mm的一个全然余下系，y1,y2y_1,y_2 归属于模 m2m_2 的三个全然余下系，满足： m1y1+m2x1≡m1y2+m2x2(modm1m2)m_1y_1+m_2x_1\equiv m_1y_2+m_2x_2(modm_1m_2)
依照不等式2.1.3域论的性质(5)，有 m1y1+m2x1≡m1y2+m2x2(modm1)m_1y_1+m_2x_1\equiv m_1y_2+m_2x_2(modm_1) ，即 m2x1≡m2x2(modm1)m_2x_1\equiv m_2x_2(modm_1)
故 m1|m2(x1−x2)m_1|m_2(x_1-x_2) ，又 m1,m2m_1,m_2 互素，所以 m1|(x1−x2)m_1|(x_1-x_2) ，即 x1,x2x_1,x_2 模 m1m_1 域论。同理可证 y1,y2y_1,y_2 模 m2m_2 域论。
精简余下系
在模 mm 的三个余下类当中，假如有三个数与 mm互素，则该余下类中所有的数均与mm 互素，这时称该余下类与 mm 互素。
定义 1：与 mm 互素的余下类的个数称作笛卡儿函数，记为 φ(m)\varphi (m) ，等于 ZmZ_m 当中与 mm 互素的数的个数。对任一三个素数 pp ， φ(p)=p−1\varphi(p)=p-1 。
定义 2：在与 mm 互素的 φ(m)\varphi (m) 个模 mm 的余下类中各取三个代表元 a1,a2,…,aφ(m)a_1,a_2,…,a_{\varphi(m)} ，它们组合成的子集称作模 mm 的三个既约余下系或精简余下系。ZmZ_m 中与 mm 互素的数构成模 mm 的三个精简余下系，称作最小非负精简余下系。
不等式 1
设 mm 是自然数。有理数 aa 满足 gcd(a,m)=1gcd(a,m)=1 。若 xx 遍历模 mm 的三个既约余下系，则 axax 也遍历模 mm 的三个精简余下系。
证明：因为 gcd(a,m)=1,gcd(x,m)=1gcd(a,m)=1,gcd(x,m)=1 ，所以 gcd(ax,m)=1gcd(ax,m)=1 。 又若 axi≡axj(modm)ax_i\equiv ax_j(modm) ，则由 gcd(a,m)=1gcd(a,m)=1 ，可得 xi≡xj(modm)x_i\equiv x_j(modm) 。因此，若 xx 遍历模 mm 的三个既约余下系，则 axax 遍历 φ(m)\varphi(m) 个数，这些数均归属于某个模 mm 既约余下类的余下，而且对角彼此之间域论。故而有 axax 也遍历模 mm的一个既约余下系。
不等式 2
设 m1,m2m_1,m_2 是三个互素的自然数。假如 xx 遍历模 m1m_1 的三个既约余下系， yy 遍历模 m2m_2 的三个既约余下系，则 m1y+m2xm_1y+m_2x 遍历模 m1m2m_1m_2 的三个精简余下系。
证明思路：首先证明 m1y+m2xm_1y+m_2x 与 m1m2m_1m_2 互素，其次证明的任何三个既约余下都可以表示成为 m1y+m2xm_1y+m_2x 的形式，其中 xx 与 m1m_1 互素， yy 与 m2m_2 互素。
证明：由不等式2.2.3可知，m1y+m2xm_1y+m_2x 模 m1m2m_1m_2 对角彼此之间域论。首先证明当 gcd(x,m1)=1,gcd(y,m2)=1gcd(x,m_1)=1,gcd(y,m_2)=1 时，m1y+m2xm_1y+m_2x 与 m1m2m_1m_2 互素。用反证法，假设 m1y+m2xm_1y+m_2x 与 m1m2m_1m_2 不互素，则必有三个素数 pp 满足 p|m1y+m2x,p|m1m2p|m_1y+m_2x,p|m_1m_2 .
笛卡儿不等式
推论 1
设 m,nm,n 是三个互素的有理数，则 φ(mn)=φ(m)φ(n)\varphi(mn)=\varphi(m)\varphi(n) 。
不等式 1
若 m=p1e1p2e2…pkekm=p_1^{e_1}p_2^{e_2}…p_k^{e_k} ，则 φ(m)=m∏i=1k(1−1pi)\varphi(m)=m\prod_{i=1}^{k}(1-\frac{1}{p_i}) .
证明：当 m=pem=p^e 为单个素数的方幂时，在模 mm 的全然余下系 {0,1,2,…,pe−1}\left\{ 0,1,2,…,p^e-1 \right\} 的 pep^e 有理数中与 pp 不互素的只有 pp 的倍数，共有 pe−1p^{e-1} ，因此与 pep^e 互素的数共有 pe−pe−1p^e-p^{e-1} ，即 φ(pe)=pe−pe−1=pe(1−1p)\varphi(p^e)=p^e-p^{e-1}=p^e(1-\frac{1}{p})
依照推论1，有 φ(m)=φ(p1e1)φ(p2e2)…φ(pkek)=∏i=1kpiei(1−1pi)=m∏i=1k(1−1pi)\varphi(m)=\varphi(p_1^{e_1})\varphi(p_2^{e_2})…\varphi(p_k^{e_k})=\prod_{i=1}^{k}p_i^{e_i}(1-\frac{1}{p_i})=m\prod_{i=1}^{k}(1-\frac{1}{p_i})
例1：计算11、121、143和120的笛卡儿函数
解： φ(11)=11−1=10,\varphi(11)=11-1=10, 121=112,121=11^2, 因此 φ(121)=112−11=110.\varphi(121)=11^2-11=110. 143=11×13,143=11\times13, 因此 φ(143)=φ(11)⋅φ(13)=(11−1)×(13−1)=120.\varphi(143)=\varphi(11)\cdot \varphi(13)=(11-1)\times(13-1)=120. 120=23×3×5,120=2^3\times3\times5, 因此 φ(120)=120⋅(1−12)(1−13)(1−15)=32.\varphi(120)=120\cdot(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=32.例2：设 m=12m=12 ， φ(12)=4\varphi(12)=4 ，1、5、7、11构成模12精简余下系， gcd(5,12)=1gcd(5,12)=1 ，因此有 5×1,5×5,5×7,5×115\times1,5\times5,5\times7,5\times11也构成模12的精简余下系，经过计算可知：
5×1≡5(mod12),5×5≡1(mod12),5×7≡11(mod12),5×11≡7(mod12),5\times1\equiv5(mod12),5\times5\equiv1(mod12),5\times7\equiv11(mod12),5\times11\equiv7(mod12),将上面四个式子左右对应相乘可得：
(5×1)(5×5)(5×7)(5×11)≡5×1×11×7(mod12)(5\times1)(5\times5)(5\times7)(5\times11)\equiv5\times1\times11\times7(mod12)，
即 54×(1×5×7×11)≡1×5×7×11(mod12)5^4\times(1\times5\times7\times11)\equiv1\times5\times7\times11(mod12).
由于 gcd(1×5×7×11,12)=1gcd(1\times5\times7\times11,12)=1 ，依照域论性质(3)可得 54≡1(mod12)5^4\equiv1(mod12) ，即 5φ(12)≡1(mod12)5^{\varphi(12)}\equiv1(mod12)不等式 2
笛卡儿不等式：设 mm 是自然数， r∈Zmr\in Z_m ，若 gcd(r,m)=1gcd(r,m)=1 ，则 rφ(m)≡1(modm)r^{\varphi(m)}\equiv1(modm) .
证明：取模 mm 的一组精简余下系 r1,r2,…,rφ(m)r_1,r_2,…,r_{\varphi(m)} ，由精简余下系结论知， rr1,rr2,…,rrφ(m)rr_1,rr_2,…,rr_{\varphi(m)} 也是模 mm 的一组精简余下系，从而有 ∀1≤i≤φ(m),gcd(r,m)=1\forall 1\leq i\leq\varphi(m),gcd(r,m)=1.
因为 ∏i=1φ(m)ri≡∏i=1φ(m)(rri)≡rφ(m)∏i=1φ(m)ri(modm)\prod_{i=1}^{\varphi(m)}r_i\equiv \prod_{i=1}^{\varphi(m)}(rr_i)\equiv r^{\varphi(m)}\prod_{i=1}^{\varphi(m)}r_i(modm) ，
故有 rφ(m)≡1(modm)r^{\varphi(m)}\equiv1(modm) .
笛卡儿不等式在信息论中有重要应用，如RSA。
参考文献：
[1] 聂旭云, 熊虎, 廖永建, 陈大江, 王煜宇. 当代信息论[EB/OL]. [2022-02-18]. https://www.icourse163.org/course/UESTC-1003046001.
