同余与欧拉函数

2019-04-13 15:55发布生成海报

站内文章 / 模拟电子

16945 0

1.同余定理
定义1 ：一般地，两个整数a和b，除以大于1的自然数m所得的余数相同，就称a、b对于模m同余，m在数学上被称谓为模（module）。记作： a≡b(mod m) 读作：a、b对于模m同余。即：如果a与b除以m的余数相同，那么a与b的关系就是模m同余关系。 同余的其它定义形式 定义1：若m|(a-b)，则称a与b对模m同余。 定义2：若a=mq+b，q∈Z，则称a与b对模m同余。显然，a≡0(mod m)等价于m|a 以上三种定义形式均为余数的定义，虽然表现形式不同，但实质是一致的。例如：当a=8，b=5，m=3时，8和5除以3得到的余数相等（均为2），就可写为 8≡5(mod3) 或 3|（8-5）或 8=3q+5 根据同余定理，可得到同余的基本性质。

1.整除性

aequiv b{pmod {m}}Rightarrow ccdot m=a-b,cin mathbb {Z}

（即是说a和b之差是m的倍数）
换句话说，

aequiv b{pmod {m}}Rightarrow mmid (a-b)

同余可以用来检验一个数是否可以整除另外一个数。

2.传递性

left.{egin{matrix}aequiv b{pmod {m}}\bequiv c{pmod {m}}end{matrix}} ight}Rightarrow aequiv c{pmod {m}}

3.保持基本运算

left.{egin{matrix}aequiv b{pmod {m}}\cequiv d{pmod {m}}end{matrix}} ight}Rightarrow left{{egin{matrix}apm cequiv bpm d{pmod {m}}\acequiv bd{pmod {m}}end{matrix}} ight.

这性质更可进一步引申成为：

aequiv b{pmod {m}}Rightarrow {egin{cases}anequiv bn{pmod {m}},forall nin mathbb {Z} \a^{n}equiv b^{n}{pmod {m}},forall nin mathbb {N} ^{0}end{cases}}

4.放大缩小模数

k

为正整数，

aequiv b{pmod {m}}

，当且仅当

{displaystyle kaequiv kb{pmod {km}}}

除法原理一

若

{displaystyle kaequiv kb{pmod {m}}}

且

{displaystyle k,m}

互质，则

aequiv b{pmod {m}}

2.欧拉函数

varphi (n)

varphi (8)=4

完全余数集合： 定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。 显然 |Zn| ＝φ(n) 。

性质：

1.对于质数 p ，φ(p) = p -1 。

2.对于两个不同质数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。

这是因为 Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ， 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝ φ(p) * φ(q) 。

欧拉定理 ： 对于互质的正整数 a 和 n ，有 a φ(n) \equiv 1 mod n

欧拉公式：

( 1 ) pk 的欧拉函数

对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = pk ， φ(n) = pk - pk -1 证明：小于 pk 的正整数个数为 pk - 1个，其中和 pk 不互质的正整数有{p * 1,p * 2,...,p * (pk - 1-1)} 共计 pk - 1 - 1 个所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

( 2 ) p * q 的欧拉函数

假设 p, q是两个互质的正整数，则 p * q 的欧拉函数为 φ(p * q) = φ(p) * φ(q)， gcd(p, q) = 1 。证明：令 n = p * q ， gcd(p,q) = 1 根据中国余数定理，有 Zn 和 Zp × Zq 之间存在一一映射（我的想法是： a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。）所以 n 的完全余数集合的元素个数等于集合 Zp × Zq 的元素个数。而后者的元素个数为 φ(p) * φ(q) ，所以有 φ(p * q) = φ(p) * φ(q) 。
3. 任意一个整数 n 都可以表示为其素因子的乘积为：

I n = ∏ p_{i^{ki (I 为 n 的素因子的个数)
i=1

根据前面两个结论，很容易得出它的欧拉函数为：

I I
Φ(n) = ∏ piki -1(p_i-1) = n ∏ (1 - 1 / pi)
i=1 i=1

对于任意 n > 2，2 | Φ(n) ,因为必存在 p_i-1 是偶数

$欧拉函数模板：$

$模板题：HDU 1286 找新朋友$

#include
#include
int Eular(int n)
{
int ans=1;
for (int i=2;i<=sqrt((double)n);i++)
{
if (n%i==0)
{
n/=i;
ans*=(i-1);
//若n有个因子是i的k次，根据欧拉公式有下面的代码
while (n%i==0)
{
n/=i;
ans*=i;
}
}
}
if (n>1) //若最后剩的数为大于1的素数，根据欧拉公式再算进去
ans*=(n-1);
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
printf("%d
",Eular(n));
}
return 0;
}

$参考：$

$欧拉函数&&欧拉公式$}}