数论学习笔记

发布于 2019-01-25  420 次阅读


一些废话基础

我们约定用\mathbb{Z}表示整数集,\mathbb{N}表示自然数集,最大公因数和最小公倍数分别用(a,b)[a,b]表示。
唯一分解定理:任一整数N(N>1)都可以唯一地分解为一组质数幂的乘积:
\displaystyle \prod_{k=1}^\infty {p_k}^{e_k}
其中e_k\in\mathbb{N}。我们称这个分解为N的标准分解。
N等价类:对于任意整数a和正整数b,存在唯一整数对(n,r)满足0 \leq r < ba = bn +r

加减乘除

( \left| a \right| , \left| b \right| ) = (a,b) = (b,a)
(a,0) = \left| a \right|
(a,b) = (a \pm b,b)
(na,nb) =n (a,b)
a \equiv b (\mod n)
对于任何\displaystyle a_1 \equiv b_1 (\mod n) \displaystyle a_2 \equiv b_2 (\mod n),无论彼此加减乘除还是整系数多项式都仍同余。
\displaystyle ac \equiv bc (\mod n)
只有当n,c互质时才可直接约掉c。即\displaystyle a \equiv b (\mod \frac{n}{(n,c)})

膜的新世界

完全剩余系:对于一个整数模n的余数,得到n个数的集合。
同余类:一组同余的集合。
缩剩余系\Phi_n:\displaystyle \Phi_n=c_1,c_2,\cdots,c_{\varphi (n)}
欧拉函数\varphi _(n):小于等于n且互质的正整数个数。
\displaystyle \varphi(x) = x\prod_{i=1}^n(1-\frac{1}{P_i})
P_i表示x的第i个质因子,且x \geqq 2,\in \mathbb{Z}。特殊的,\varphi(1)=1
费马小定理:\displaystyle a^{p-1} \equiv 1 (\mod p)
欧拉定理:(a,n)=0,满足
\displaystyle a^{\varphi (n)} \equiv 1 (\mod n)

欧几里得的游戏

辗转相除:\displaystyle (a,b)=(b, a \mod b)
裴蜀定理:扩展欧几里得是在计算最大公约数的同时找到x,y,使得ax + by =d
我们首先解\displaystyle ax + by =(a,b)
我们假设已经找到了一组解x^{'} , y^{'}使得
\displaystyle bx^{'} + (a \mod b)y^{'} = (b,a \mod b)
我们根据积可以知道这两代数式恒等。
因为
\displaystyle a \mod b = a -[\frac{a}{b}]b
所以化简得
\displaystyle ax+by=ay^{'}+b(x^{'}-[\frac{a}{b}]y^{'})
最终
最终\displaystyle x = y^{'},y = x^{'} -[\frac{a}{b}]y^{'}

后话

本文部分内容来自一些blog还有<<初等数论>>。
文中大多数简单的证明已匿去,如有需要可私信。


我是一个局部环,你是我的唯一极大理想。