NumberTheory1

huangx607087 学习数论的笔记1

1.勾股定理及费马大定理（数论概论$2,3,4$章）

表达式：$a^2+b^2=c^2$

本源勾股数组：满足$\gcd(a,b,c)=1$

生成本源勾股数组： $a=st,b=\frac{s^2-t^2}{2},c=\frac{s^2+t^2}{2}$。其中$s>t≥1$且$s,t$均为奇数且$\gcd(s,t)=1$

本源勾股数组的性质： $a,b$一定是一个奇数一个偶数，$a,b$中一定有一个是$3$的倍数，$a,b,c$中一定有一个是$5$的倍数

费马大定理：**$n≥3$时，方程$a^n+b^n=c^n$无正整数解。**

2.最大公约数$\gcd$的相关性质(数论概论$5,6$章)

互质:$\gcd(a,b)=1$

求 $\gcd$ 的方法：欧几里得辗转相除，时间复杂度：$O(\ln b)$

C++代码

int gcd(int x,int y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}

线性方程： $ax+by=\gcd(a,b)$

求解$x,y$的C++代码

long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		long long R=exgcd(b,a%b,y,x);
		y-=x*(a/b);
		return R;
	}
}

逆元代码：(Python直接用命令inverse(a,p))

long long modinverse(long long a,long long p)
{
	long long x0,y0;
	exgcd(a,p,x0,y0);
	long long A=(x0+750*p)%p;
	return A;
}

3.余数与整除(数论概论$7,8,9,10,11$章)

1.表示方法：如果$m$ 整除$a-b$，可以记作：$a \equiv b \mod m$。例如：$7+6 \equiv 3 \mod 10$

性质1.若$a\equiv A \mod m,b\equiv B\mod m$：有：$a+b \equiv A+B \mod m,ab \equiv AB \mod m$.

设关于$x$的同余方程：$ax \equiv c \mod m$，求$x$?

性质2.设$g=\gcd(a,m)$,若$c\equiv 0 \mod g$ 那么这个方程有$g$个解。我们可以求$au+mv=g$这个方程的解。然后计算$x_0=\frac {cu}{g}$这样我们就可以求出$x_0$。然后我们设$\delta =\frac{m}{g}$（显然$\delta$是整数）那么$x_1=x+\delta,x_n=x_{n-1}+\delta$,$n=1,2,3,..,g-1$.

举个例子：

假如我们要求方程$4x \equiv 6 \mod 18$的值，我们计算：$g=\gcd(4,18)=2$，所以这个方程有$2$个解。$\delta=\frac{18}{2}=9$。我们可以计算出：$u=-4\equiv 14 \mod 18$。那么$x_0=\frac {6×14}{2} \equiv 6 \mod 18$。那么$x_1=x_0+\delta=6+9=15$。所以这个方程有两解$6$和$15$

若推广到高次方程，我们可以得到$f(x)=\sum_{i=0}^{n} a_ix^i \equiv 0 \mod p$ 至多有$n$个在$Z_p$内的解。

性质3.费马小定理：$a^{p-1} \equiv 1 \mod p $ 其中$a \not\equiv 0 \mod p$.

利用这个定理，我们可以在$\ln p$级别的时间复杂度内判断$p$是不是素数。例如：由于$2^{1234566} \equiv 899557 \mod 1234567$。所以$1234567$不是素数。而$535776^{998244352}\equiv 1 \mod 998244353$ 所以$998244353$是素数。

注意：这个方法实际上是有反例的。也就是说，$a^{p-1} \equiv 1 \mod p $ 是“$p$是素数”的 必要不充分条件。最小的一个反例是$561$ .这个结论将在笔记$3$中提到。

性质4.推广费马小定理: $a^{\phi(m)} \equiv 1 \mod m$其中$m \not\equiv 0 \mod a$.

$\phi(x)$表示在小于$x$的数中与$x$互质的数个数。其中：对于质数$p$有$\phi(p)=p-1$,$\phi(p^k) = p^k-p^{k-1}$。对于任何数字有$\phi(ab)=\phi(a)\phi(b)$

性质5.中国剩余定理。见0xGame Div 2 的第一题wp.