|
引理: 记 \(d=\min E\,(E=\{d =ua+vb: u,v\in\mathbb{Z}, d > 0\}),\)
\(\qquad\;\gcd(a,b)\) 为 \(a,b\)的最大公约数, 则 \(\gcd(a,b)=d\).
证: 取\(u_0,v_0\in\mathbb{Z}\)使\(d=u_0a+v_0b\). 易见 \(\gcd(a,b)\mid d\)
\(\quad\)作带余除法 \(a=qd+r\,(0\le r< d).\) 若 \(r=(1-qu_0)a-qv_0b>0\),
\(\quad\)则 \(d>r\in E\),与 \(d\) 的最小性矛盾, 故 \(d\mid a\). 同理 \(d\mid b\).
\(\quad\)可见\(d\le\gcd(a,b)\mid d.\quad\square\)
题: 对正整数\(a,b\)及素数 \(p\), 有 \(p\mid ab\implies (p\mid a)\vee(p\mid b)\)
证: 不妨设 \(p\not\mid a\). 则因 \(p\)是素数, 有\(u,v\in\mathbb{Z}\)使\(up+va=1\)
\(\quad\) 于是 \(p\mid ubp+v(ab)=b.\quad\square\) |
|