关于整除 , 素数的八条性质 证明

· · 个人记录

整除 , 素数的八条性质

$\qquad\qquad\qquad ax+by=(a,b) \qquad$ [裴蜀定理] _证明_ ：设 $d=gcd⁡(a,b)$ ,则 $d\,|\,a,d\,|\,b$。 由整除的性质得，$\forall x,y \in Z$，有 $d\,|(ax+by)$. 设 $s$ 为 $ax+by$ 的最小正值，令 $q = ⌊\frac{a}{s}⌋

则 r=a\,mod\,s=a-q(ax+by)=a(1-qx)+b(-qy),

故 r 为 a，b的线性组合。

由于 r=a\,mod\,s，所以 0 \leq r < s.

由于 s 为 a,b 线性组合的最小正值，可知 r=0.

因此有 s\,|\,a,s\,|\,b,\,\,s为 a,b的公约数，d≥s ①

因为 d\,|\,a,d\,|\,b,且 s 是 a 与 b 的一个线性组合,

所以由整除性质可知 d\,|\,s, 因此 d≤s②.

由①② 得d=s，gcd⁡(a,b)=ax+by , 命题得证。

2$. $\,a,b$ 互素当且仅当存在整数 $x,y$， 使得：$\quad ax+by=1

简化： 已知 \exists \,x,y\,\,\,\, s.t.\,\,\,\, ax + by = 1 , 求证 (a,b)=1

证明 ： \because ax+by=c 有整数解的充要条件是 gcd(a,b)|c ,

------------ $3$. $\,$若 $m\,|\,a,\,m\,|\,b$ , 则 $m\,|\,(a,b)\,;

证明 ： 设 a=km, b=k'm， 则

(a,b)=ax+by=akm+bk'm=(ka+k'b)m \quad\therefore m \,|\, (a,b) 4$. $\,$若 $m>0$ , 则 $(ma,mb)=m(a,b)\,;

证明 ： 回顾辗转相除法的过程，每一项都 \times \,m.

5$. $\,$若 $(a,b)=d$ , 则 $(\frac{a}{d},\frac{b}{d})=1

证明 ： 反证， 若 (\frac{a}{d},\frac{b}{d})>1 , 则

(\frac{a}{d} \times d,\frac{b}{d} \times d) = (a,b)= d \times (\frac{a}{d},\frac{b}{d}) > d ------------ $6$. $\,$若 $(a,m)=1, (b,m)=1$ , 则 $(ab,m)=1

证明 ：\because (a,m)=1 \quad \therefore ax + my = 1

\,\,\,\,\quad\quad \because (b,m)=1$ $\quad \therefore bx' + my' = 1 \therefore (ax + my)(bx' + my') = 1 ab \times x' + amxy + bmx'y + m^2y\,y'=1 \therefore ab(x\,x') + m(axy + bx'y + my\,y') =1 $\therefore (ab, m)=1$ 得证. ------------ $7$. $\,$若 $(a,b)=1$ , 则 $(a^l,b^k)=1

证明 : \,\,(a,b)=1, (a,b)=1 \implies (a^2,b)=1

以此类推，\quad(a^l,b)=1 .

(a^l,b)=1,(a^l,b)=1 \implies (a^l,b^2)=1

以此类推，\quad(a^l,b^k)=1 . 得证.

8$. $\,$若 $b\,|\,ac,\,\,(b,c)=1$ , 则 $b\,|\,a

证明 : \,\,b \,| \, ac \to bk = ac.

(b,c)=1 \implies bx + cy = 1 abx + acy = a, \,\,abx + bky = a, \,\,b(ax+ky)=a