Skip to content

Tag Archives: 数论

《简明数论》的简明笔记(下)

x²≡d (mod p)的问题。 ax²+bx+c≡0 (mod p)可通过配方转化。 (2ax+b)²≡b²-4ac(mod p) d是p的二次剩余当且仅当方程有解,否则为二次非剩余。 既约剩余系中恰有(p-1)/2个二次剩余和(p-1)/2二次非剩余。 d是二次剩余当且仅当d(p-1)/2≡1 (mod p),否则模为-1。 于是两二次剩余或两二次非剩余的积为二次剩余,二次剩余与非剩余的积为二次非剩余。 Legendre符号当d是p的二次剩余、非剩余及p|d时分别取值1、-1、0。 Gauss二次互反律的主要应用似乎是用来简化及计算Legendre符号的值,以求解二次同余方程。 但在编程中可直接利用来计算,复杂度是相同的。 Jacobi符号具有与Legendre符号相同的互反律,但似乎就与二次同余方程没什么关系了,目前还没看到应用。 关于同余方程的Lagrange定理的内容是同余方程的解数不超过它的次数。 可用归纳法证明,很优雅。 n次同余方程有n个解,当且仅当f(x)的次数小于等于p,且f(x)除xp-x所得的余式模p恒等于0。 对于次数大于p的高次同余方程,总存在一个次数不大于p、首项系数为1的等价同余方程,即是xp-x除f(x)所得的余式(再将首项系数化为1)。 例外是余式模p恒等于0,不妨认为此时的等价同余方程就是xp-x。 事实上,简化高次同余方程也可避免做多项式除法,可用Fermat小定理xp≡x (mod p)直接降低次数。 模为素数幂的同余方程的解法看上去很强大,但是前提是需要先解出模为素数的同余方程啊!难道除了直接验证没什么通用的解法?26节先放下。

《简明数论》的简明笔记(中):13~21节

Euler函数φ(m),定义,积性不完全; ; ; 。 用积性证很简单;证明二:按与m的最大公约数分类。 f(n)的Mobius变换:; Mobius逆变换:; 以上两式等价,f(n)与F(n)的积性也等价。 f与g的Dirichlet卷积:,h保持f与g的积性。 同余: a对模m的最小非负剩余、绝对最小剩余; 同余式是等价关系;同余式可加减乘;ca≡cb (mod m)等价于a≡b (mod m/(c,m) ); 对模m的逆的定义。 同余类、完全剩余系定义; 既约剩余系包含的同余类个数即φ(m)。 (a,m)=1时,x遍历m的完全/既约剩余系当且仅当ax遍历m的完全/既约剩余系。 用这个可轻松证明Fermat-Euler定理。 Wilson定理,即(p-1)! ≡ -1 (mod p)。 证:除了-1外,其它因子可与(不相等的)逆元配对抵消。 即,p的既约剩余系的积模p得-1。 扩展:p可换成pk,2pk(这两者p是奇素数)。 事实上,r不取1,2,4,pk,2pk时,r的既约剩余系的积模r得1。 ax≡b (mod m) 型的同余方程。 (a,m)|b 是有解的充要条件,解有(a,m)个。 可求a对m的所有逆元。 注意到一个解是 ,也可用扩展欧几里德求特解。 所有解是,其中0<=t<(a,m)。 形如的一次同余方程组。 若{m_i}两两既约,则解数必为1(中国剩余定理)。 解为。 其中,。 当a_i分别遍历m_i的完全/既约剩余系时,x遍历m的完全/既约剩余系。 若{m_i}并非两两既约,例如(m_i,m_j)=a时,可将模m_i与m_j的两个方程化成模a、m_i/a、m_j/a的三个方程。 编程时,直接化为若干个模p^k的方程似更简便,其中p^k || [m_1,m_2,...,m_i,...]。 f(x)≡0 (mod n) 的解数设为 T(f;n),则T(f;n)是关于n的积性函数。 […]

《简明数论》的简明笔记(上):1~12节

按:数论貌似是我目前还接触太少的领域,遵从vls的推荐借了北大出版社的《简明数论》来浏览,还是很好玩儿的……下面是从中总结的一些比较新鲜的结论。 {a_i} 的最大公约数等于 {a_i} 的所有整系数线性组合组成的集合中的最小正整数; 事实上,被最大公约数整除,等价于能表示成整系数线性组合。 一次不定方程 ∑a_i*x_i=c 有解的充要条件是 c|({a_i}); 解一次不定方程的算法(待实现)。 x^2+y^2=z^2 的本原解:x=r^2-s^2, y=2rs, z=r^2+s^2; 其中r>s>0, (s,r)=1, 2不整除r+s; 等价地刻画了单位圆周上的有理点。 Chebyshev不等式:,; 其实重点在于:O(π(x))=x/log x,O(p_n)=n log n。 (π(x)即不大于x的素数个数;p_n即第n个素数。) 数论函数:[完全]积性函数的充要条件; 除数和函数; F(n)=∑_{d|n}f(d) 保持f(n)的积性。(除数即Divisor) Mobius函数:; 事实上与容斥原理很有关联; 引理: 集合A中与K互质的元素个数,其中A_d是A中被d整除的子集; 将A取不超过x的实数,K取不超过的所有素数的乘积,可得,这样可以在已知不超过的素数的前提下求π(x)。 从算法的角度看似无意义?