夜深人静补数学

安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了,LOL)

Note: 博客迁移导致乱码，懒得fix了

如果$\sum a_i=\sum b_i$,除掉删除的一项,所有的项都是$c$的倍数,那么删除的一项也是$c$的倍数

移项后提取$c$得证

$a=bq+r,(0≤r<b)$是唯一确定的

证明: 如果存在另一个$a=bq_1+r_1,(0≤r_1<b)$ 与原式作差后得到$0=b(q-q_1)+(r-r_1)$ ,观察到$r-r_1$是$b$的倍数,而由前面的限制条件得到 $|r-r_1|<b$,所以$r-r_1=0$

这里使用了作差的技巧

如果$a=bq+c$,则$a$和$b$的公约数集合与$b$和$c$的公约数集合相同,由此推出$(a,b)=(b,c)$,这是$gcd$算法的依据

其实我从来没思考过这是如何证明的orz,大概想到应该是对称性,换了个位置$c=a-bq$然后瞪了几秒没啥发现了

上网搜了一下,设$d$ 为 $a,b$的公约数,既 $d|a,d|b$,由 $c=a-bq$,得到 $c/d=a/d-bq/d=m$,观察到 $m$是整数,所以 $d|c$,d也是$c$的公约数

自己的想法也只是离正确答案一步之遥,原因在于我只是想过程而没考虑到我需要的结果,很显然我需要知道$c/d$的结果是什么,可惜我不会构造个简单的整除,弱的一匹(还给老师系列)

显然$(am,bm)=(a,b)m$

设 $d|a,d|b,(a/d,b/d)=(a,b)/d$ ,特别地,$a/(a,b)$与$b/(a,b)$互素

$(a,b)=(a/d*d,a/d*d)=(a/d,b/d)d$ ←比较有用的式子

定理↓

若$(a,b)=1$,则$(ac,b)=(c,b)$

十分显然的结果,因为$a$与$b$互质,从唯一分解定理可知只可能是$c$对$b$有$gcd$的贡献

书上的证明:$$(ac,b)

ac$且$(ac,b)

bc$(★),由公约数集合相同的定理,$(ac,b)

[(ac,bc)=(a,b)c=c]$$ ←有点绕

又$$(ac,b)

b$,所以$(ac,b)

(c,b)$$ ←很跳

反之,$$(c,b)

ac$和$(c,b)

b$,所以$(c,b)

(ac,b)$$

既$(ac,b)=(c,b)$

↑还没反应过来就完了,感觉使用姿势比较高只能从猜测得证,很难对未知的结果进行借鉴,突破口是对$abc$的组合的讨论,引出$(ac,bc)$,可以看作是补全的技巧

**若$(a,b)=1$且$$b

ac$,则$b

c$$**

套用上面的方法,因为$$b

ac$且$b

bc$,所以$b

(ac,bc)$,既$b

c$$

集合$A$与集合$B$中的元素两两互素,则$\prod{a_i}$与$\prod{b_i}$也互素

个人证明还是用唯一分解定理,两个集合的元素中分解得到的素数$p$都不一样(没有交集)怎么乘都没所谓啊

书里给出的是很厉害的使用定理1,$(a_i,b_j)=1$,推出$(a_ia_k,b_j)=(a_i,b_j)=1$,不断迭代得$(\prod{a_i},b_j)=1$,对$b$也用相同的套路,

得$(\prod{a_i},\prod{b_i})=1$

连分式跳过

课后习题部分记入OneNote

---

$n!$中,素数$p$的次方数为$\sum[n/p_i]$

引用某段解释,以下为$20!$时$p=2$的情况

2、4、6、8、10、12、14、16、18、20能被2整除

4、8、12、16、20能被4整除(即被2除一次后还能被2整除)

8、16能被8整除(即被2除两次后还能被2整除)

16能被16整除(即被2除三次后还能被2整除)

顺便总结一下其他定理 $n$的约数个数:若$n=\prod p_i^{k_i}$,则约数个数为$\prod (1+k_i)$,由组合可知

$a/b$的约数个数:若$a=\prod p_i^{k_i}$,$b=\prod q_i^{m_i}$,则约数个数为$\prod(k_i-m_i+1)$

积性函数:$f(p)f(q)=f(pq)$,其中$p,q$互素(不是一定要素数)

完全积性函数多出的性质:$f(n^k)=f^k(n)$

**对于积性函数,$$\sum_{d

n}f(d)=\prod_{i=1}^{m}\sum_{j=0}^{k_i}f(p_i^j)$,其中$m$为$n$分解得到的素数个数,$k_i$为素数$p$$的最高次方数**

证明:顺着证明似乎有难度,我们可以反过来想,不同的约数均为$n$分解素数的不同组合,总有一个$f(d)=\prod f(p_i^j)$,对于不重不漏的约数函数和即为上式的组合(没有系统学过组合不好说话)

$f(d)=d$时既可计算出$n$的约数的总和,这是$f(d)=d^s$的特殊情况

---

Mobius

$$μ(n)=0,i^2

n$$ (某个数的平方->某个素数存在平方以上的次数)

$μ(n)=(-1)^k$,$k$为$n$的素约数个数 ($n=\prod p_i^{k_i}$)

***$$\sum_{d

n}μ(d)f(d)=\prod_{i=1}^{m}(1-f(p_i))$$**

若$n=1$则右式为$1$

**所以,当$f(d)=1$时,$$\sum_{d

n}μ(d)=[n==1]$$**

令$f(d)=\frac{1}{d}$,

**当$n>1$时,$$\sum_{d

n}\frac{μ(d)}{d}=\prod_{i=1}^{m}(1-\frac{1}{p_i})$$**

$n=1$时,后者为$1$

补充一下书里缺少(书写风格极其诡异)的但有必要知道的莫比乌斯反演 $f(n)$不易求出但$\sum_{d|n}f(d)$容易求得时

**令$$F(n)=\sum_{d

n}f(d)$$=>$$f(n)=\sum_{d

n}μ(d)F(n/d)$$**

**反过来也行$$F(n)=\sum_{n

d}f(d)$$=>$$f(n)=\sum_{n

d}μ(d/n)F(d)$$**

欧拉函数的补充:

$φ(a)=[gcd(x,a)==1]$的个数,$x<a$(分别对应书中的$δ=gcd(x,a)$和$f=1$)

$$S'=[δ==1],S_d'=[d|δ=(x,a)]$$

而$(x,a)$是$d$的倍数只有在$d$是$a$的约数时成立

$S_d'$成为$$[d

x]$的个数,既$a/d$$

**那么$$φ(n)=\sum_{d

n}μ(d) \frac{n}{d}$$**

**还有另一常见反演$$\sum_{d

n}φ(d)=n$$**

参考数论变换入门:

重新把前面两个式子写出来

①:$$\sum_{d

n}μ(d)=[n==1]$$(此处指个数)

②:$$\sum_{d

n}φ(d)=n$$

对$n$变个样子有:

①:$$[(a,b)==1]=\sum_{d

(a,b)}μ(d)$$

②:$$(a,b)=\sum_{d

(a,b)}φ(d)$$

---

同余

与等式相似的性质

1.可传递,$a≡c$,$b≡c$,则$a≡b$(均为模$m$)

2.可相加,$a≡b$,$c≡d$,则$a+c≡b+d$

3.可移项,$a+c≡b+d$,则$a+c-c≡b+d-c$,既$a≡b+d-c$

4.任一边可加模$m$任意倍数,$a≡b$,$mk≡0$,既$a+mk≡b$

5.可逐项相乘,$a≡b$,$c≡d$,则$ac≡bd$,$ak≡bk$($k$任意)

两边可以被公约数$d$整除(如果$d$与模$m$互质)

$a≡b,a=a_1d,b=b_1d$,则$(a-b)≡0$,既$(a_1-b_1)d≡0$,由$(d,m)=1$,得$$(a_1-b_1)

m$$

$$a_1≡b_1$$

更多性质

1 两边和模可乘上同一整数,$a≡b(mod \ m)$,则$ak≡bk(mod \ mk)$

2 两边和模可被三者任意公约数取模 $a_1d≡b_1d(mod \ m_1d)$,则$a_1≡b_1(mod \ m_1)$

3 $a≡b$对于模$m_i$均成立,则$$(a-b)

m_i$,既$a≡b(mod \ lcm(m_i))$$

4 若$a_1d≡b(mod \ m_1d)$,则$b/d$是整数

5 若$a≡b(mod \ m)$,则$(a,m)=(b,m)$

Last Update:2018/03/03