1. 整除
设a , b ∈ Z a,b \in \rm Za,b∈Z，其中Z ZZ表示整数，a ≠ 0 a \neq 0a=0，如果存在q ∈ Z q \in \rm Zq∈Z使得b = a q b=aqb=aq，则称b bb可被a aa整除，记作a ∣ b a|ba∣b，并且称b bb是a aa的倍数，a aa是b bb的约数或除数、因数。
正整数n nn是素数，当且仅当它不能被任何整数d dd整除，其中1 < d ≤ n 1<d\leq \sqrt n1<d≤n.
设m , n ∈ Z m,n \in Zm,n∈Z，若能同时整除m mm和n nn的整数只有± 1 \pm 1±1，则称m mm和n nn互素。
2. 最大公约数
m mm和n nn均为不为零的整数，在m mm和n nn的所有公约数中存在唯一的公约数d > 0 d>0d>0，使得m mm和n nn的任一公约数e ee都整除d dd，则d dd称为最大公约数，记作d = g c d ( m , n ) d=gcd(m,n)d=gcd(m,n)。两个数m mm和n nn互素，记作g c d ( m , n ) = 1 gcd(m,n)=1gcd(m,n)=1
欧几里得算法是寻找两个整数a aa和b bb( a > b ) (a>b)(a>b)的最大公约数g c d ( a , b ) gcd(a,b)gcd(a,b)的常用方法，过程如下：g c d ( a , b ) = g c d ( b , a m o d b ) gcd(a,b)= gcd(b,a \bmod b)gcd(a,b)=gcd(b,amodb)eg： 求525 525525和778 778778的最大公约数
778 = 1 × 525 + 253 , g c d ( 728 , 525 ) = g c d ( 525 , 253 ) 778 =1 \times 525 +253 ,\;\; gcd(728,525) = gcd(525,253)778=1×525+253,gcd(728,525)=gcd(525,253)525 = 2 × 253 + 19 , g c d ( 525 , 253 ) = g c d ( 523 , 19 ) 525 =2 \times 253+19 ,\;\; gcd(525,253) = gcd(523,19)525=2×253+19,gcd(525,253)=gcd(523,19)253 = 13 × 19 + 6 , g c d ( 523 , 19 ) = g c d ( 19 , 6 ) 253 =13 \times 19+6 ,\;\; gcd(523,19) = gcd(19,6)253=13×19+6,gcd(523,19)=gcd(19,6)19 = 3 × 6 + 1 , g c d ( 19 , 6 ) = g c d ( 6 , 1 ) 19 =3 \times 6+1 ,\;\; gcd(19,6) = gcd(6,1)19=3×6+1,gcd(19,6)=gcd(6,1)最后得到余数1，则g c d ( 525 , 778 ) = 1 gcd(525,778)=1gcd(525,778)=1，即525 525525与778 778778互素。
3. 模运算
设m ≠ 0 m \neq 0m=0，若m ∣ a − b m|a-bm∣a−b，即a − b = k m a-b=kma−b=km，则称a aa同余于b bb模m mm，或b bb是a aa对模m mm的剩余，记作a ≡ b m o d m a \equiv b \bmod ma≡bmodm上式也称为模m mm的同余式，或简称同余式。由于m ∣ a − b m|a-bm∣a−b等价于− m ∣ ( a − b ) -m|(a-b)−m∣(a−b)，因此a ≡ b m o d m a \equiv b \bmod ma≡bmodm等价于a ≡ b m o d ( − m ) a \equiv b \bmod(-m)a≡bmod(−m)。
模运算的性质
- (1)自反性：对于任意的a aa，总有 a ≡ a m o d m a \equiv a \bmod ma≡amodm
- (2)对称性：如果a ≡ b m o d m a \equiv b \bmod ma≡bmodm，那么b ≡ a m o d m b \equiv a \bmod mb≡amodm
- (3)传递性：如果a ≡ b m o d m a \equiv b \bmod ma≡bmodm，且b ≡ c m o d m b \equiv c \bmod mb≡cmodm，那么a ≡ c m o d m a \equiv c \bmod ma≡cmodm
- (4)结合律：[ ( a m o d m ) ± ( b m o d m ) ] m o d m ≡ ( a ± b ) m o d m [(a \bmod m) ± (b \bmod m)]\bmod m \equiv (a±b)\bmod m[(amodm)±(bmodm)]modm≡(a±b)modm[ ( a m o d m ) × ( b m o d m ) ] m o d m ≡ ( a × b ) m o d m [(a \bmod m) \times (b \bmod m)]\bmod m \equiv (a \times b)\bmod m[(amodm)×(bmodm)]modm≡(a×b)modm
- (5)分配律：[ ( a × b ) m o d m + ( a × c ) m o d m ] m o d m ≡ [ a × ( b + c ) ] m o d m [(a \times b)\bmod m+(a \times c)\bmod m] \bmod m \equiv [a \times (b+c)]\bmod m[(a×b)modm+(a×c)modm]modm≡[a×(b+c)]modm
- (6)加法消除律：如果( a + b ) ≡ ( a + c ) m o d m (a+b) \equiv(a+c) \bmod m(a+b)≡(a+c)modm，则b = c m o d m b=c \bmod mb=cmodm
- (7)乘法消除律：如果( a × b ) ≡ ( a × c ) m o d m (a \times b)≡(a \times c) \bmod m(a×b)≡(a×c)modm，且g c d ( a , m ) = 1 gcd(a,m)=1gcd(a,m)=1，则b ≡ c m o d m b \equiv c \bmod mb≡cmodm。
4. 逆元
对于非0、非± 1 \pm 1±1的整数m mm，若g c d ( a , m ) = 1 gcd(a,m) =1gcd(a,m)=1，即a aa与m mm互素，则a aa模m mm的逆元存在。
且存在唯一整数x ( 0 < x < m ) x(0<x<m)x(0<x<m)，使a x ≡ 1 m o d m ax \equiv 1 \bmod max≡1modm记为a − 1 ≡ x m o d m a^{-1} \equiv x \bmod ma−1≡xmodm通常使用扩展的欧几里得算法：用欧几里得算法求出a aa和m mm的最大公约数，如果公约数是1，则逆元存在。通过反向迭代操作得到表达式x a + y m = 1 xa+ym =1xa+ym=1，从而得到a aa模m mm的逆元x xx和m mm模a aa的逆元y yy。
eg： 求25 2525模31 3131的逆元
∵ \because∵31 = 25 × 1 + 6 , 25 = 4 × 6 + 1 31=25 \times 1+6, 25=4 \times 6+131=25×1+6,25=4×6+1∴ \therefore∴1 = 25 − 4 × 6 = 25 − 4 × ( 31 − 25 ) = − 4 × 31 + 5 × 25 1=25-4 \times 6=25-4\times (31-25)=-4\times 31+5\times 251=25−4×6=25−4×(31−25)=−4×31+5×25因此，25 2525模31 3131的逆元为5 55，31 3131模25 2525的逆元为− 4 + 25 = 21 -4+25=21−4+25=21。
5. 欧拉函数
欧拉函数（Euler）φ ( n ) \varphi(n)φ(n)为对于一个正整数n nn，与其互素且小于等于n nn的正整数个数。
φ ( n ) \varphi(n)φ(n)具有如下性质：
- 如果p pp是素数，则φ ( p ) = p − 1 \varphi(p) = p-1φ(p)=p−1
- 设n = m 1 m 2 ，且 g c d ( m 1 , m 2 ) = 1 n=m_1m_2，且gcd(m_1,m_2)=1n=m1m2，且gcd(m1,m2)=1，则φ ( n ) = φ ( m 1 ) φ ( m 2 ) \varphi(n) = \varphi(m_1)\varphi(m_2)φ(n)=φ(m1)φ(m2)
- 对于整数n ≥ 2 n\ge 2n≥2，不计次序，n nn具有唯一分解式:n = p 1 α 1 p 2 α 2 . . . p m α m n=p_1^{\alpha_1}p_2^{\alpha_2}...p_m^{\alpha_m}n=p1α1p2α2...pmαm其中p 1 , p 2 , . . . . , p m p_1,p_2,....,p_mp1,p2,....,pm为两两不同的素数，α 1 ≥ 1 , 1 ≤ i ≤ m \alpha_1 \ge 1, 1 \le i \le mα1≥1,1≤i≤m，则φ ( n ) = ( p 1 α 1 − p 1 α 1 − 1 ) ( p 2 α 2 − p 2 α 2 − 1 ) . . . . ( p m α m − p m α m − m ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p m ) \varphi(n) = (p_1^{\alpha_1} - p_1^{\alpha_1-1})(p_2^{\alpha_2} - p_2^{\alpha_2-1})....(p_m^{\alpha_m} - p_m^{\alpha_m-m}) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})φ(n)=(p1α1−p1α1−1)(p2α2−p2α2−1)....(pmαm−pmαm−m)=n(1−p11)(1−p21)...(1−pm1)举例
对于n = 20 = 2 2 × 5 n=20=2^2 \times 5n=20=22×5，φ ( 20 ) = φ ( 2 2 × 5 ) = ( 2 2 − 2 2 − 1 ) × ( 5 1 − 5 1 − 1 ) = 2 × 4 = 8 \varphi(20) = \varphi(2^2 \times 5) =(2^2-2^{2-1}) \times (5^1-5^{1-1}) = 2 \times 4 = 8φ(20)=φ(22×5)=(22−22−1)×(51−51−1)=2×4=8
6. 欧拉定理
数论中的欧拉定理（Euler Theorem）又称费马-欧拉定理或欧拉函数定理。
对于任意整数a , n a,na,n，若g c d ( a , n ) = 1 gcd(a,n)=1gcd(a,n)=1，即a aa与n nn互素，则a φ ( n ) ≡ 1 m o d n a^{\varphi(n)}\equiv 1 \bmod naφ(n)≡1modneg： 利用欧拉定理简化大指数的幂运算：计算2 1000000 m o d 77 2^{1000000} \bmod 7721000000mod77
由于gcd ( 2 , 77 ) = 1 \gcd(2,77)=1gcd(2,77)=1，根据欧拉函数，φ ( 77 ) = φ ( 7 × 11 ) = φ ( 7 ) × φ ( 11 ) = 6 × 10 = 60 \varphi(77)=\varphi(7\times 11)=\varphi(7) \times \varphi(11) = 6 \times 10=60φ(77)=φ(7×11)=φ(7)×φ(11)=6×10=60
根据欧拉定理2 60 m o d 77 ≡ 1 m o d 77 2^{60}\bmod 77 \equiv 1 \bmod 77260mod77≡1mod77由于1 , 000 , 000 = 16666 × 60 + 40 1,000,000=16666\times 60+401,000,000=16666×60+40因此2 1000000 m o d 77 ≡ 2 16666 × 60 + 40 m o d 77 ≡ ( 2 16666 × 60 m o d 77 ) ( 2 40 m o d 77 ) ≡ ( ( 2 60 m o d 77 ) 16666 m o d 77 ) ( 2 40 m o d 77 ) ≡ 2 40 m o d 77 ≡ ( 2 10 m o d 77 ) 4 m o d 77 ≡ ( 2 3 2 m o d 77 ) 2 m o d 77 ≡ 6 7 2 m o d 77 ≡ 23 \begin{aligned} 2^{1 000 000} \bmod 77 \equiv \; & 2^{16666\times 60+40}\bmod 77 \\ \equiv \; & (2^{16666\times 60}\bmod 77)(2^{40} \bmod 77) \\ \equiv \; & ((2^{60} \bmod 77)^{16666} \bmod 77)(2^{40} \bmod 77) \\ \equiv \; & 2^{40} \bmod 77 \\ \equiv \; & (2^{10} \bmod 77)^{4} \bmod 77 \\ \equiv \; & (23^{2} \bmod 77)^{2} \bmod 77 \\ \equiv \; & 67^{2} \bmod 77 \equiv 23 \\ \end{aligned}21000000mod77≡≡≡≡≡≡≡216666×60+40mod77(216666×60mod77)(240mod77)((260mod77)16666mod77)(240mod77)240mod77(210mod77)4mod77(232mod77)2mod77672mod77≡23
7. 费马小定理
如果p pp是一个素数，且a aa是不能被p pp整除的正整数，那么a p − 1 ≡ 1 m o d p a^{p-1}\equiv 1 \bmod pap−1≡1modp或者a p ≡ a m o d p a^{p}\equiv a \bmod pap≡amodp费马小定理是欧拉定理中n nn为素数的情况。
8. 一次同余方程
如果a , b a,ba,b都是整数，n nn是一个正整数，当a m o d n ≠ 0 a \bmod n \neq 0amodn=0时，a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn称为模n nn的一次同余方程，或者线性同余方程。
一次同余方程a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn有解当且仅当方程a x + n y = b ax+ny=bax+ny=b有整数解，方程a x + n y = b ax+ny=bax+ny=b有整数解的充要条件是gcd ( a , n ) ∣ b \gcd(a,n)|bgcd(a,n)∣b。
如果x 0 x_0x0是满足a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn的一个整数，即a x 0 ≡ b m o d n ax_0 \equiv b \bmod nax0≡bmodn，则满足x ≡ x 0 m o d n x\equiv x_0 \bmod nx≡x0modn的所有整数x xx也能满足a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn，即包含x xx的模n nn同余类中的整数都满足a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn。包含x xx的模n nn同余类[ x 0 ] [x_0][x0]称为a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn的一个解，即同余方程的一个解包含一个类的所有整数。
同余方程a x ≡ b m o d n ax \equiv b \bmod nax≡bmodn有解当且仅当gcd ( a , n ) ∣ b \gcd(a,n)|bgcd(a,n)∣b，并且，如果这个同余方程有解，则有gcd ( a , n ) \gcd(a,n)gcd(a,n)个不同的解。
9. 中国剩余定理
我国古代的《孙子算经》中提出了这样的问题:“今有物不知数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”该问题可用一次同余方程组表示:{ x ≡ 2 m o d 3 x ≡ 3 m o d 5 x ≡ 2 m o d 7 \begin{cases} x \equiv 2 \bmod 3 \\ x \equiv 3 \bmod 5 \\ x \equiv 2 \bmod 7 \end{cases}⎩⎨⎧x≡2mod3x≡3mod5x≡2mod7中国剩余定理（孙子定理）：设m 1 ， m 2 ， … ， m r m_1，m_2，…，m_rm1，m2，…，mr，是r ≥ 2 r\ge 2r≥2个两两互素的大于1 11的整数，令M = m 1 m 2 . . . m r M=m_1m_2...m_rM=m1m2...mr，则同余方程组{ x ≡ a 1 m o d m 1 x ≡ a 2 m o d m 2 ⋮ x ≡ x r m o d m r \begin{cases} x \equiv a_1 \bmod m_1 \\ x \equiv a_2 \bmod m_2 \\ \;\;\;\;\;\;\;\;\; \vdots \\x \equiv x_r \bmod m_r \end{cases}⎩⎨⎧x≡a1modm1x≡a2modm2⋮x≡xrmodmreg: 我国古代数学家杨辉在1275年所写的《续古摘奇算法》有如下题目：二数余一，五数余二，七数余三，九数余四，问本数。
由题意得{ x ≡ 1 m o d 2 x ≡ 2 m o d 5 x ≡ 3 m o d 7 x ≡ 4 m o d 9 \begin{cases} x \equiv 1 \bmod 2 \\ x \equiv 2 \bmod 5 \\ x \equiv 3 \bmod 7 \\ x \equiv 4 \bmod 9 \end{cases}⎩⎨⎧x≡1mod2x≡2mod5x≡3mod7x≡4mod9根据中国剩余定理，m 1 = 2 ， m 2 = 5 ， m 3 = 7 ， m 4 = 9 ； a 1 ， a 2 = 2 ， a 3 = 3 ， a 4 = 4 ， M = 2 × 5 × 7 × 9 = 630 m_1=2，m_2=5，m_3=7，m_4=9；a_1，a_2=2，a_3=3，a_4=4，M=2 \times 5\times 7\times 9=630m1=2，m2=5，m3=7，m4=9；a1，a2=2，a3=3，a4=4，M=2×5×7×9=630
则M 1 = 630 / 2 = 315 , M 2 = 630 / 5 = 126 ， M 3 = 630 / 7 = 90 ， M 4 = 630 / 9 = 70 M_1=630/2=315,M_2=630/5=126，M_3=630/7=90，M_4=630/9=70M1=630/2=315,M2=630/5=126，M3=630/7=90，M4=630/9=70
根据315 b 1 ≡ 1 m o d 2 315b_1 \equiv 1\bmod 2315b1≡1mod2，解得b 1 ≡ 1 m o d 2 b_1\equiv 1\bmod 2b1≡1mod2，同理有b 2 ≡ 1 m o d 5 , b 3 ≡ 6 m o d 7 , b 4 ≡ 4 m o d 9 b_2\equiv 1\bmod 5,b_3\equiv 6\bmod 7,b_4\equiv 4\bmod 9b2≡1mod5,b3≡6mod7,b4≡4mod9
因此，x = 315 + 126 × 2 + 90 × 6 × 3 + 70 × 4 × 4 ≡ 157 m o d 630 x=315+126\times 2+90\times6\times3+70\times4\times4 \equiv157\bmod 630x=315+126×2+90×6×3+70×4×4≡157mod630
10. 二次剩余和Blum整数
如果p pp是素数，且a < p a<pa<p，如果x 2 ≡ a m o d p x^2 \equiv a \bmod px2≡amodp有解，则称a aa是对模p pp的二次剩余。
不是所有的a aa的值都满足这个特性。如果a是对模n的一个二次剩余,那么它必定是对模n nn所有素因子的二次剩余。
例如p = 7 p=7p=7，二次剩余是1 , 2 , 4 1,2,41,2,4{ 1 2 = 1 ≡ 1 m o d 7 2 2 = 4 ≡ 4 m o d 7 3 2 = 9 ≡ 2 m o d 7 4 2 = 16 ≡ 2 m o d 7 5 2 = 25 ≡ 4 m o d 7 6 2 = 36 ≡ 1 m o d 7 \begin{cases} 1^2 = 1 \equiv 1 \bmod 7 \\ 2^2 = 4 \equiv 4 \bmod 7 \\ 3^2 = 9 \equiv 2 \bmod 7 \\ 4^2 = 16 \equiv 2 \bmod 7 \\ 5^2 = 25 \equiv 4 \bmod 7 \\ 6^2 = 36 \equiv 1 \bmod 7 \\ \end{cases}⎩⎨⎧12=1≡1mod722=4≡4mod732=9≡2mod742=16≡2mod752=25≡4mod762=36≡1mod7
没有x xx值可满足下列方程:{ x 2 ≡ 3 m o d 7 x 2 ≡ 5 m o d 7 x 2 ≡ 6 m o d 7 \begin{cases} x^2 \equiv 3 \bmod 7 \\ x^2 \equiv 5 \bmod 7 \\x^2 \equiv 6 \bmod 7\end{cases}⎩⎨⎧x2≡3mod7x2≡5mod7x2≡6mod7所以,3 , 5 , 6 3,5,63,5,6称为模7 77的二次非剩余。
易证明，当p pp为奇数时，模p pp的二次剩余数目恰好是( p − 1 ) / 2 (p-1)/2(p−1)/2，且与其二次非剩余的数目相同。
如果a aa是模p pp的二次剩余，那么a aa恰好有两个平方根:
- 其中一个在1 ∼ ( p − 1 ) / 2 1 \sim(p-1)/21∼(p−1)/2 之间;
- 另一个在( p + 1 ) / 2 ∼ ( p − 1 ) (p+1)/2 \sim (p-1)(p+1)/2∼(p−1)之间。
此外,这两个平方根中的一个也是模的二次剩余,被称为主平方根。
如果n nn是两个素数p pp和q qq之积，那么模n nn恰好有( p − 1 ) ( q − 1 ) / 4 (p-1)(q-1)/4(p−1)(q−1)/4个二次剩余。如果a aa是对模n nn的一个二次剩余，那么它必定是对模n nn的所有素因子的二次剩余。这是因为要成为模n nn的平方，其余数必须有模p pp的平方和模q qq的平方。例如，模35 3535有11 1111个二次余:1 , 4 , 9 , 11 , 14 , 15 , 16 , 21 , 25 , 29 , 30 1,4,9,11,14,15,16,21,25,29,301,4,9,11,14,15,16,21,25,29,30。每一个二次剩余恰好有4 44个平方根。
如果p pp和q qq是两个素数,且都是模4 44余3 33的，那么n = p × q n=p \times qn=p×q称为Blum 整数。如果n nn是一个Blum整数，它的每一个二次剩余恰好有4 44个平方根，其中一个也是模n nn的二次剩余，称为主平方根。例如，139 139139 模$ 437$ 的主平方根是 24 2424，其他三个平方根分别为185 185185，252 252252 和 413 413413。
