数论学习笔记1——整除、质数、同余与逆元
walk_alone
·
·
个人记录
这是第一篇关于数论的学习笔记，也是整个数论板块最基础的一篇学习笔记，除了逆元以外基本都是小学内容。但是这个系列从本文开始将按照数学的公理化体系来行文。
关于整除，或许不用多言。在小学我们就知道了这个事情：如果被除数b除以除数a没有余数那么则称被除数整除除数，记作a|b。
引入一个性质：若c|a且c|b，则c|a-b。
证明：a=k_ac,b=k_bc,a-b=c(k_a-k_b)，因此c|a-b。
那么我们很自然的关心一个数能够被什么数、多少数整除。我们发现一些数，值能被1和它自己整除，我们将它们归为一类：质数。而还有其他的因数的，我们归为合数。
然后从整除出发，有些可以整除，但是大多数的除法运算都会有余数存在。我们自然关心不同除法运算的余数问题。于是这引出了同余问题：在除数（以后称模数）的情况下，多个被除数做除法得到的余数相同。以后我们会将取余数这一操作成为取模操作，在计算机中使用%运算符进行取模。
首先给出一个取模运算的定义：
显然这一操作基于除法运算。对于这个运算，它有哪些性质呢？
在此先列出以下的几条性质：(约定：$p$为模数)
整除性$kp\%p=0$，当$k$为整数时。
线性性$(\alpha a+\beta b)\%p=(\alpha(a\%p)+(\beta(b\%p)))\%p$。其中$a,b,\alpha,\beta$均为整数。
证明：
$Left=(\alpha (t_ap+k_a)+\beta (t_bp+k_b))$%$p$（使用性质1）
$=(\alpha k_a+\beta k_b)$%$p=Right$。
乘法：$ab\%p=(a\%p)(b\%p)\%p$。
证明：
$$ab\%p=(t_ap+k_a)(t_bp+k_b)\%p=p(t_at_bp+(k_a+k_b))\%p+(k_ak_b)\%p=(a\%p)(b\%p)\%p$$
（此处用到性质1和性质2）
但是除法运算不成立：因为取模运算本身就是基于除法运算，因此无法证明。但是我们可以找到一个替代的方法：用乘法换成除法。而这个被替代的数被成为逆元。下给出定义：
如果$ab\equiv 1\mod p$，则称$a$是$b$的逆元。注意逆元具有相互性，也就是说$b$也是$a$的逆元。同时，该式可以记为$\displaystyle a\equiv\frac{1}{b} \mod p$。通过该式，我们可以发现该概念的引入扩展了取模运算的适用对象，将有理数也加入了取模运算的范畴。
例如，$\displaystyle \frac{a}{b}\equiv at \mod p$，其中$bt\equiv1 \mod p$。
在之后的几节中将会谈到如何求解逆元。
从这篇文章开始，往后的学习笔记大体可以分成以下两条线：质数与合数、同余方程与同余方程组。