夜深人静补数学
安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了LOL)
可能学习这些烂大街的结论从直接受益来说并不好,但学习一下计算的技巧还有想法也是不错的,说不定比瞎摸题效率间接高一点(毕竟自己不会推式子)
因此本文章注重证明的过程(顺便捞一堆定理),希望自己思(姿)维(势)方(水)式(平)有所提高
如果\(\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\)的结果是什么,可惜我不会构造个简单的整除,弱的一匹(还给老师系列)
由此就有了烂大街的\(gcd(a,b)=gcd(b,a\ mod\ b)\)
显然\((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\)