数论部分知识积累::代数

# 数论部分知识积累::代数 ### 重要信息：本文中的定义基本上都是我自己编的，差不多就行。如果您是那种迂腐麻木只知道背定义的人，这篇文章可能不太适合您，出门左转百度百科，谢谢。 ___ ___ ## 欧拉函数 ### 性质 以下默认$\ {\color{Blue}{p\ is\ a\ prime}}$ $\varphi(p)=p-1$ $\varphi(mn)=\varphi(m) \times \varphi(n)\qquad gcd(m,n)=1$ 如果$\ i \mod p = 0\ $，那么$\ \varphi(i \times p)=p \times \varphi(i)$ 如果$\ i \mod p \ne 0\ $，那么$\ \varphi(i \times p)=(p-1) \times \varphi(i)$ ### 板子 ```cpp int n; int phi[MAXN]; void Getphi(){ For(i,n) phi[i] = i; Forx(i,2,n){ if( phi[i] == i ){ // i is a prime now Forstep(j,i,n,i) phi[j] = phi[j]/i*(i-1); } } } ``` ___ ___ # 同余 ## $Gcd$($GunChuangDan$) ### 描述 $gcd(a,b)$表示 $a,b$ 的最大公约数 ### 板子 ```cpp int Gcd( int a , int b ){ if(a<b) swap(a,b); if(!b){ return a; } return Gcd(b,a%b); } ``` ## 扩欧(扩展欧几里德,$Exgcd$) ### 描述 整数对 $x,y$ ，使得 $gcd(a,b)\ =\ ax + by$。 ### 板子 ```cpp int Exgcd( int a , int b , int &x , int &y ){ if(!b){ x = 1; y = 0; return a; } int q = Exgcd(b,a%b,y,x); y -= a/b*x; return q; } ``` ## 不定方程 [一篇好文](https://www.cnblogs.com/khan724/p/4148954.html) ### 定义 看着像 $ ax+by \ = \ c$ 的式子，就是不定方程 ### 性质 $ ax + by = c\ $有正整数解的条件为 $c\ mod\ gcd(a,b) = 0$ 若 $x,y$ 是方程解，那么 $x+n \cdot b\ ,y-n \cdot a\ (\ n \in Z\ )$ 也是方程解 ## 贝祖定理（裴蜀定理） 若a，b是整数，且 $gcd(a,b)\ =\ d$ ，那么对于任意的整数$x,y$ , $ ax+by \ = \ c$中的 $m$ 一定是 $d$的倍数。 ## 同余式(同余方程) ### 定义 形如 $ a \equiv b \ \color{Blue}{(mod \ c)}$的式子，应该就是同余式（逃 ### 性质 $ a \equiv b + c \ {\color{Blue}{(mod \ d)}}\quad \Leftrightarrow \quad a-b \equiv c\ {\color{Blue}{(mod \ d)}}$ --- --- # 整除性 以下默认 $\color{blue}{p,q\ are\ primes}$ ### 若$p,q$均为质数，则$p^a$与$q^b$互质