初等数论二

整数唯一分解定理

引理1

若p是一个素数，a是任意整数，则有 $p\mid a或(a,p)=1$

引理2

若p是素数，且 $p\mid ab$ ，则 $p\mid a或p\mid b$

定理1

任何大于1的正整数都能分解为素数得乘积，即对于整数 $a>1,有且仅有唯一表达式a=p_1p_2...p_n,p_1\leq p_2\leq ...\leq p_n,其中p_1,p_2...p_n都是素数$
任意大于1的整数能够唯一写成 $a=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},其中\alpha_i>0,p_i<p_j(i<j)是素数$ 对于a和b， $(a,b)=p_1^{min(\alpha_1,\beta_1)}p_2^{min(\alpha_2,\beta_2)}...p_k^{min(\alpha_k,\beta_k)}.\\ [a,b]=p_1^{max(\alpha_1,\beta_1)}p_2^{max(\alpha_2,\beta_2)}...p_k^{max(\alpha_k,\beta_k)}$

由于x+y=max(x,y)+min(x,y),所以有ab=[a,b] (a,b)

一元不定方程

二元一次不定方程： $a_1x+a_2y=n,其中a_1,a_2,n给定，a_1a_2\neq0$

定理2

二元一次不定方程有解的充要条件是 $(a_1,a_2)\mid n$
证明：有解时显然成立，设 $(a_1,a_2)=1及a_1>0,a_2>0，则a_1u+a_2v=1,于是x=nu，y=nv有解$

定理3

设 $(a_1,a_2)=1$ ，则其全部解表示为 $x=x_0+a_2t,\\ y=y_0-a_1t,\\ x_0,y_0为二元一次不定方程的以一组解$

定理4

$设s\geq 2,s元一次不定方程a_1x_1+...+a_sx_s=n,a_1...a_s\neq0$ 有解的充要条件是 $(a_1,...,a_s)\mid n$

定理5

不定方程 $a_1x_1+a_2x_2=n,(a_1,a_2)=1,a_1>0,a_2>0$ 在 $n>a_1a_2$ 时有整数解初等数论二

同余

定义1

给定正整数m，则a，b同余记为 $a\equiv b(\mod m)$ 否则记为 $a\not\equiv b(\mod m)$
性质1 自反性，对称性，传递性

定理6

整数a，b对模m同余的充要条件时 $m\mid a-b$

定理7

如果 $a\equiv b(\mod m),\alpha \equiv \beta(\mod m),则有\\(1)ax+\alpha y\equiv bx+\beta y(\mod m),\\ (2)a\alpha \equiv b\beta (\mod m),\\(3)a^n\equiv b^n(\mod m),\\ (6)f(a)\equiv f(b)(\mod m).$

定理8

如果 $ac\equiv bc(\mod m),且若（m,c)=d,则\\ a\equiv b(\mod \frac{m}{d})$
初等数论二

定理9

若 $a\equiv b(\mod m_i),i=1,2,...,n则a\equiv b(\mod [m_1,m_2,...,m_n])$ 初等数论二

剩余类和完全剩余系

定义2

设m是一个给定整数，C_r(r=0,1,…,m-1)表示所有形如qm+r的整数组成的集合，其中 $q=0,\pm1,\pm 2...，则C_0,C_1,...,C_{m-1}叫做模m的剩余类$

定理10

设m>0,模m剩余类C_j,则，每个整数都包含在某个剩余类C_j中，两个整数x，y属于同一类的充要条件是 $x\equiv y(\mod m)$

定义3

在模m的剩余类 $C_0,C_1,...,C_{m-1}$ 中各取一个数 $a_j \in C_j$ ,这m个数称为模m的一组完全剩余系

定理11

m个整数成为模m的完全剩余系的充要条件是两两对模m不同余

非负最小完全剩余

0，1，2，。。。，m-1

定理12

设(k,m)=1，而 $a_0,a_1,...,a_{m-1}$ 是模m的一组完全剩余系，则 $ka_0,ka_2,...,ka_{m-1}$ 也是模m的一组完系初等数论二

定理13

$设m_1>0,m_2>0,(m_1,m_2)=1,而x_i,y_j分别通过模m_1,m_2的完系，则m_2x_i+m_1y_j通过模m_1m_2的完系$

$m_2x_1'+m_1x_2'-m_2x_1^{''}-m_1x_2^{''}\equiv 0(\mod m_1m_2)$
初等数论二

初等数论