1. 同余符号：
≡
\equiv
≡
（1）含义
两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余，记作a≡b(mod m)。读作a同余于b模m，或读作a与b关于模m同余。
例：26≡14(mod 12)。
（2）定义
设m是大于1的正整数，a，b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)，读作a同余于b模m。
（3）性质
(1)若a≡0(mod m)，则m|a;
(2)a≡b(mod m)等价于a与b分别用m去除，余数相同。
2. 同余定理
（1）定义
给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称
整数a与b对模m同余
，记作a≡b(mod m)。
（2）性质
- 反身性：a≡a (mod m)；
- 对称性：若a≡b(mod m)，则b≡a (mod m)；
- 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
-
同余式相加减：若a≡b(mod m)，c≡d(mod m)，则a
±\pm
±
c≡b
±\pm
±
d(mod m)； -
同余式相乘：若a≡b(mod m)，c≡d(mod m)，则a
∗*
∗
c≡b
∗*
∗
d(mod m)。 - 同余式数乘：若a≡b(mod m)，则ak≡bk(mod m)，k为任意整数。
-
除法：若 a
∗*
∗
c≡b
∗*
∗
c(mod m) ，c
=\cancel{=}
=
0，则a≡b( mod m/(gcd(c,m)) ) ，其中gcd(c,m)表示c和m的最大公约数，
特殊地，gcd(c,m)=1，则 a≡b(mod m) ； -
幂运算：如果a≡b(mod m) ，那么
an
a^n
a
n
≡
bn
b^n
b
n
(mod m) ； - 若 a≡b(mod m) ，n=m，则 a≡b(mod n) ；
-
若 a≡b(mod
mi
m_i
m
i
) ，(i=1,2…n) 则 a≡b(mod [
m1
,
m
2
,
…
,
m
n
m_1,m_2,…,m_n
m
1
,
m
2
,
…
,
m
n
]) ，其中 [
m1
,
m
2
,
…
,
m
n
m_1,m_2,…,m_n
m
1
,
m
2
,
…
,
m
n
] 表示m1,m2,…mn的最小公倍数。 -
若 a≡b(mod m) ，k为正整数，则 ka≡kb(mod km) ；
d为a,b,m的任一公约数，则
ad
≡
b
d
(
m
o
d
m
d
)
\frac{a}{d}≡\frac{b}{d}(mod\space \frac{m}{d})
d
a
≡
d
b
(
m
o
d
d
m
)
； - 设d>=1，d|m，若 a≡b(mod m) ，则 a≡b(mod d) ；
- 若 a≡b(mod m)，则 (a,m)≡(b,m) ；
- 如果 a mod b = c ，则有(a+kb) mod b =c(k为非0整数)
- 如果 a mod b = c ，则有(ka) mod b =(kc) mod b (k为正整数)
- (a+b) mod c =((a mod c)+(b mod c )) mod c;
-
(a
b) mod c=((a mod c)
(b mod c)) mod c
3. 欧拉函数
（1）定义
φ(n)是
欧拉函数
（Euler’s totient function），设n是正整数，φ(n)表示{0,1,…,n-1}中与n互素的数的个数。例如φ(12)=4，因为与12互素的数有1，5，7，11。这里认为φ(1)=1。
（2）公式
φ
(
n
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
…
(
1
−
1
p
k
)
φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})
φ
(
n
)
=
n
(
1
−
p
1
1
)
(
1
−
p
2
1
)
…
(
1
−
p
k
1
)
其中p1, p2……pn为n的所有质因数，n是不为0的整数。
（3）性质
-
对于质数n，φ(n)=n-1
-
对于质数p，若
n=
p
k
n=p^k
n
=
p
k
，
φ(
n
)
=
p
k
−
p
k
−
1
=
(
p
−
1
)
p
k
−
1
φ(n)=p^k-p^{k-1}=(p-1)p^{k-1}
φ
(
n
)
=
p
k
−
p
k
−
1
=
(
p
−
1
)
p
k
−
1
-
【积性函数】:
若m,n互质，φ(mn)=φ(m)φ(n) -
【计算式】:
对于质数p，若
n=
∏
p
i
k
i
=
p
1
k
1
∗
p
2
k
2
∗
p
3
k
3
∗
…
∗
p
n
k
n
n=\prod p_i^{k_i}=p_1^{k_1}*p_2^{k_2}*p_3^{k_3}*…*p_n^{k_n}
n
=
∏
p
i
k
i
=
p
1
k
1
∗
p
2
k
2
∗
p
3
k
3
∗
…
∗
p
n
k
n
，
则
φ(
n
)
=
n
∗
∏
(
1
−
1
p
i
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
…
(
1
−
1
p
k
)
φ(n)=n*\prod(1-\frac{1}{p_i})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})
φ
(
n
)
=
n
∗
∏
(
1
−
p
i
1
)
=
n
(
1
−
p
1
1
)
(
1
−
p
2
1
)
…
(
1
−
p
k
1
)
-
【欧拉定理】：
对于互质的a,n，有
aφ
(
n
)
≡
1
(
m
o
d
n
)
a^{φ(n)} ≡ 1 (mod\space n)
a
φ
(
n
)
≡
1
(
m
o
d
n
)
-
小于n且与n互质的数的和：
S=
φ
(
n
)
∗
n
2
S=φ(n) * \frac{n}{2}
S
=
φ
(
n
)
∗
2
n
，(n>1) -
对于质数p，
若n mod p=0，则φ(n∗p)=φ(n)∗p
若n mod p≠0，则φ(n∗p)=φ(n)∗(p−1) -
n=
∑
d
∣
n
φ
(
d
)
n=\sum _{d∣n}φ(d)
n
=
∑
d
∣
n
φ
(
d
)
，即n的因数（包括1和它自己）的欧拉函数之和等于n
（5）计算单个欧拉函数
int oula(int n)
{
int rea=n;
for(int i=2; i*i<=n; i++)
if(n%i==0)//第一次找到的必为素因子
{
rea=rea-rea/i;
do
n/=i;//把该素因子全部约掉
while(n%i==0);
}
if(n>1)
rea=rea-rea/n;
return rea;
}
（6） 欧拉函数打表O(NlogN)
说明：
定义：欧拉函数phi(n)，表示小于或等于n的数中与n互质的数的数目。
欧拉函数求值的方法是：
（1）phi(1)=1
（2）若n是素数p的k次幂，
p
h
i
(
n
)
=
p
k
−
p
k
−
1
=
(
p
−
1
)
p
k
−
1
phi(n)=p^k-p^{k-1}=(p-1)p^{k-1}
p
h
i
(
n
)
=
p
k
−
p
k
−
1
=
(
p
−
1
)
p
k
−
1
（3）若m，n互质，phi(mn)=phi(m)phi(n)
根据欧拉函数的定义，可以推出欧拉函数的递推式：
令p为N的最小质因数，若
p
2
∣
N
,
p
h
i
(
N
)
=
p
h
i
(
N
p
)
×
p
p^2|N,phi(N)=phi(\frac{N}{p})\times p
p
2
∣
N
,
p
h
i
(
N
)
=
p
h
i
(
p
N
)
×
p
；否则
p
h
i
(
N
)
=
p
h
i
(
N
p
)
×
(
p
−
1
)
phi(N)=phi(\frac{N}{p})\times (p-1)
p
h
i
(
N
)
=
p
h
i
(
p
N
)
×
(
p
−
1
)
接口：
void genPhi();
复杂度：O(NlogN)
输出：phi全局变量，存储了1~max中每个数的欧拉函数。
代码：
const int max = 111111;
int minDiv[max],phi[max],sum[max];
void genPhi()
{
for(int i=1;i<max;++i)
minDiv[i] = i;
for(int i=2;i*i<max;++i)
{
if( minDiv[i]==i )
for(int j=i*i;j<max;j+=i)
minDiv[j] = i;
}
phi[1] = 1;
for(int i=2;i<max;++i)
{
phi[i] = phi[i/minDiv[i]];
if( (i/minDiv[i]%minDiv[i]==0 )
phi[i] *= minDiv[i];
else
phi[i] *= minDiv[i]-1;
}
}
4. 完全余数集合
定义小于 n 且和 n 互质的数构成的集合为 Z(n) ，称呼这个集合为 n 的
完全余数集合
。 显然 |Z(n)| ＝φ(n) 。
5. 算术基本定理
任何一个大于1的自然数 N ，如果N不为质数，那么N可以唯一分解成有限个质数的乘积
N
=
P
1
a
1
∗
P
2
a
2
∗
P
3
a
3
∗
…
∗
P
n
a
n
N=P_1^{a_1}*P_2^{a_2}*P_3^{a_3}*…*P_n^{a_n}
N
=
P
1
a
1
∗
P
2
a
2
∗
P
3
a
3
∗
…
∗
P
n
a
n
，这里
P
1
<
P
2
<
P
3
<
…
…
<
P
n
P_1<P_2<P_3<……<P_n
P
1
<
P
2
<
P
3
<
…
…
<
P
n
均为质数，其诸指数
a
i
a_i
a
i
是正整数。
这样的分解称为 N 的标准分解式。