通常做网站要多久,高端自适应网站设计,网络推广外包sem营销外包,网站建设常用的开发语言介绍研究的对象#xff1a;不定方程 文章目录 研究的对象#xff1a;不定方程不定方程引入#xff1a;裴蜀定理证明#xff1a;欧几里得算法证明#xff1a;充分性证明#xff1a;必要性证明#xff1a; 战术总结#xff1a; 不定方程引入#xff1a;
不定方程#xff0…研究的对象不定方程 文章目录 研究的对象不定方程不定方程引入裴蜀定理证明欧几里得算法证明充分性证明必要性证明 战术总结 不定方程引入
不定方程又称丢番图方程定义为未知数为整数系数也为整数的多项式等式。
形如 a 1 x 1 b 1 a 2 x 2 b 2 . . . a n x n b n c a_1x_1^{b_1} a_2x_2^{b_2}...a_nx_n^{b_n} c a1x1b1a2x2b2...anxnbnc
如果我们能找到一组整数解 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn我们就说这个方程有解。
但是我们并不研究不定方程的一般式而是研究其特殊的形式即一次不定方程 a 1 x 1 a 2 x 2 . . . a n x n c a_1x_1 a_2x_2...a_nx_n c a1x1a2x2...anxnc
这个一次不定方程有解的充要条件是 g c d ( a 1 , a 2 , . . , a m ) ∣ c gcd(a_1,a_2,..,a_m)|c gcd(a1,a2,..,am)∣c 即c为这n个数的倍数的时候该一次不定方程有解
这个推论是由二元一次不定方程有解的情况归纳而来
即 对于二元一次不定方程 a x b y c axbyc axbyc
此方程有解的充要条件是 : g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c
这个结论是裴蜀定理的证明下面将引出裴蜀定理。
裴蜀定理与不定方程的解有什么关系
裴蜀定理给出 对于任何整数 a b m abm abm关于未知数 x , y x,y x,y 的一元二次不定方程 a x b y m axby m axbym 此方程有解的充要条件是 g c d ( a , b ) ∣ m gcd(a,b)|m gcd(a,b)∣m由于只给了一个不定方程所以整数解有无穷多个每一组(x,y)都被称为裴蜀数。 裴蜀定理证明
由于是任意整数 a , b a,b a,b
所以我们先考虑0的情况
1、当 a 0 a 0 a0
该不定方程为 b y m by m bym , 此方程有整数解当且仅当 b ∣ m b\:|\:m b∣m 。
可以写成 g c d ( 0 , b ) ∣ m gcd(0,b)|m gcd(0,b)∣m 写到这里突然有个想法 g c d ( 0 , b ) gcd(0,b) gcd(0,b) 这样的写法是合法的吗 公约数的定义如果有一个数 d d d, 对于 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an都有 d ∣ a i , i ∈ [ 1 , n ] d|a_i,i\in[1,n] d∣ai,i∈[1,n] 这样的数就被称为这些数的公约数。 将 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an的所有公约数放入集合 D D D中 D { d ; d ∣ ( a 1 , a 2 , a 3 , . . . a n ) } D\lbrace d;d|(a_1,a_2,a_3,...a_n)\rbrace D{d;d∣(a1,a2,a3,...an)} 最大公约数gcd的定义是 d m a x ∈ D d_{max}\in D dmax∈D使得 ∀ d ∣ d m a x \forall d|d_{max} ∀d∣dmax其中 d m a x d_{max} dmax被称为 g c d gcd gcd。 0 0 0能被任意非 0 0 0数整除 b b b最大只能被 b b b整除。 当只要求 2 2 2个整数的最大公约数的时候有一方为 0 0 0那么它们的最大公因数就是另一个非零数本身。 都讲到这里了顺便在写一下欧几里得算法的证明
欧几里得算法证明 考虑 g c d ( a , b ) g c d ( b , a m o d b ) gcd(a,b) gcd(b,a\:mod\:b) gcd(a,b)gcd(b,amodb) 的证明面向结果证明 任意一个整数可以写成带余除法因为要用到 a m o d b a\:mod\:b amodb 的形式所以将 a a a写成关于 b b b的带余除法 a k b c a kbc akbc , c a m o d b c a \:mod \:b camodb 并约定 ( b ≠ 0 ) (b\neq0) (b0)。 设 d d d 是 a , b a,b a,b的最大公约数。 有 d ∣ a , d ∣ b d|a ,\: d|b d∣a,d∣b。 两边同时除以d a d k b d c d \frac{a}{d} k\frac{b}{d}\frac{c}{d} dakdbdc。 由于 a d , b d \frac{a}{d},\frac{b}{d} da,db都是整数所以 c d \frac{c}{d} dc也是一个整数。 这说明 d ∣ c d|c d∣c , 这说明 d d d 是 ( a , b , c ) (a,b,c) (a,b,c)的最大公约数。 所以得到了最终的转移式子 g c d ( a , b ) g c d ( b , c ) gcd(a,b) gcd(b,c) gcd(a,b)gcd(b,c) 这个证明过程告诉我们不要忽视整数这个性质 2、当 b 0 b 0 b0 的时候这与 a 0 a 0 a0 的计算过程等价结论也等价所以不过多赘述。
3、下面讨论 a ≠ 0 , b ≠ 0 a\neq0,b\neq0 a0,b0 的情况
再次重申我们要证明的是什么有时候写着写着忘记要干嘛了
证明 a x b y c ax by c axbyc 有整数解 ( x , y ) ⇔ g c d ( a , b ) ∣ c (x,y)\Leftrightarrow gcd(a,b)|c (x,y)⇔gcd(a,b)∣c 充分性证明 证明充分性即证明 a x b y c ⇒ g c d ( a , b ) ∣ c axbyc \Rightarrow gcd(a,b)|c axbyc⇒gcd(a,b)∣c 假设 a x b y c axbyc axbyc有解。 设 A { a x b y ; ( x , y ) ∈ Z 2 } A \lbrace axby ; (x,y)\in \Z^2 \rbrace A{axby;(x,y)∈Z2} 不妨设 c 0 c_0 c0为 A A A的最小正整数元素 a x 0 b y 0 c ax_0by_0c ax0by0c其中 c c c表示A的任意一个正整数元素 a x b y c axbyc axbyc。 作 c c c对 c 0 c_0 c0的带余除法 c q c 0 r c qc_0 r cqc0r 0 ≤ r c 0 0 \leq r c_0 0≤rc0 代入原式 a x b y q ( a x 0 b y 0 ) r axby q(ax_0by_0) r axbyq(ax0by0)r r a ( x − q x 0 ) b ( y − q y 0 ) r a(x-qx_0) b(y - qy_0) ra(x−qx0)b(y−qy0) 显然满足 r ∈ A r\in A r∈A ∵ \because ∵ 0 ≤ r c 0 0\leq r c_0 0≤rc0 而 c 0 c_0 c0是 A A A中的最小正元素。 ∴ \therefore ∴ r r r 不是正元素 即 r 0 r0 r0所以 c c c对 c 0 c_0 c0的带余除法为 c q c 0 cqc_0 cqc0 也就是说 A A A中任意一个正元素 c c c都存在 c 0 ∣ c c_0|c c0∣c。 ∵ a x b y c ∀ c ∈ A , c 0 ∣ c \because axbyc \forall c\in A ,c_0|c ∵axbyc∀c∈A,c0∣c ∴ \therefore ∴ , c 0 ∣ a x c_0 |ax c0∣ax , c 0 ∣ b y c_0|by c0∣by ∵ x , y ∈ Z \because x,y\in\Z ∵x,y∈Z ∴ c 0 ∣ a , c 0 ∣ b \therefore c_0|a,c_0|b ∴c0∣a,c0∣b 即 c c c 是 a , b a,b a,b的公约数。 这是一个关键的进展 接下来我们只要证明 g c d ( a , b ) c 0 gcd(a,b)c_0 gcd(a,b)c0 就能得到 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c 设 d d d为 a , b a,b a,b的任意正公约数 a k d , b l d akd,bld akd,bld。 a x b y k d x l d y ( k x l y ) d c 0 ax by kdxldy(kxly)dc_0 axbykdxldy(kxly)dc0 ∴ d ∣ c 0 \therefore d|c_0 ∴d∣c0 ∴ g c d ( a , b ) c 0 \therefore gcd(a,b)c_0 ∴gcd(a,b)c0 ∴ ∀ a , b , c ∈ Z , a x b y c \therefore \forall a,b,c\in \Z , \:axbyc ∴∀a,b,c∈Z,axbyc 有解 ⇒ g c d ( a , b ) ∣ c \Rightarrow gcd(a,b)|c ⇒gcd(a,b)∣c 充分性证毕 必要性证明 证明当 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c的时候 a x b y c axbyc axbyc 有解 这个问题等价于证明当 g c d ( a , b ) c 0 gcd(a,b)c_0 gcd(a,b)c0时 a x b y c 0 axbyc_0 axbyc0有解 设 d g c d ( a , b ) d gcd(a,b) dgcd(a,b) 等式两边同时除以 d d d等式就被转换为 a ′ x b ′ y 1 axby1 a′xb′y1 其中 g c d ( a ′ , b ′ ) 1 gcd(a,b)1 gcd(a′,b′)1 问题就转化为证明这个等式成立 a ′ x b ′ y 1 axby1 a′xb′y1。 这个求解的过程可以由欧几里得算法顺带求出。 令 a ′ a , b ′ b aa,bb a′a,b′b 模拟求 g c d ( a , b ) gcd(a,b) gcd(a,b)的过程 a k 1 b r 1 a k_1br_1 ak1br1 ⇒ a b , b r 1 \Rightarrow ab,br_1 ⇒ab,br1 b k 2 r 1 r 2 bk_2r_1r_2 bk2r1r2 r 1 k 3 r 2 r 3 r_1k_3r_2r_3 r1k3r2r3 . . . ... ... r n − 1 k n 1 r n r n 1 . . . ( 3 ) r_{n-1}k_{n1}r_{n}r_{n1}...(3) rn−1kn1rnrn1...(3) r n k n 2 r n 1 r n 2 . . . . ( 2 ) r_nk_{n2}r_{n1}r_{n2}....(2) rnkn2rn1rn2....(2) r n 1 k n 3 r n 2 . . . ( 1 ) r_{n1}k_{n3}r_{n2}...(1) rn1kn3rn2...(1) g c d r n 2 gcd r_{n2} gcdrn2 欧几里得算法在 r 0 r0 r0的时候停止并返回 b b b也就是 ( 1 ) (1) (1)式子 所以可以得到 r n 2 1 r_{n2}1 rn21 r n k n 2 r n 1 1... ( 2 ) r_{n}k_{n2}r_{n1}1...(2) rnkn2rn11...(2) 联立 ( 2 ) , ( 3 ) (2),(3) (2),(3)消去 r n 1 r_{n1} rn1 { k n 2 r n 1 1 − r n k n 2 r n 1 k n 2 r n − 1 − k n 1 k n 2 r n \begin{cases} k_{n2}r_{n1}1-r_n\\ k_{n2}r_{n1}k_{n2}r_{n-1}-k_{n1}k_{n2}r_n \end{cases} {kn2rn11−rnkn2rn1kn2rn−1−kn1kn2rn 得 ( k n 2 k n 1 − 1 ) r n 1 k n 2 r n − 1 . . . ( 1 ′ ) (k_{n2}k_{n1}-1)r_n1k_{n2}r_{n-1}...(1) (kn2kn1−1)rn1kn2rn−1...(1′) 联立 ( 1 ′ ) , ( 3 ) (1),(3) (1′),(3)消去 r n r_n rn { r n − 2 k n r n − 1 r n ( k n 2 k n 1 − 1 ) r n 1 k n 2 r n − 1 \begin{cases} r_{n-2} k_{n}r_{n-1}r_n\\ (k_{n2}k_{n1}-1)r_n1k_{n2}r_{n-1} \end{cases} {rn−2knrn−1rn(kn2kn1−1)rn1kn2rn−1 得 ( k n 2 k n 1 − 1 ) r n − 2 1 ( k n 2 k n 1 k n − k n k n 2 ) r n − 1 . . . ( 2 ′ ) (k_{n2}k_{n1}-1)r_{n-2}1(k_{n2}k_{n1}k_{n}-k_nk_{n2})r_{n-1}...(2)\\ (kn2kn1−1)rn−21(kn2kn1kn−knkn2)rn−1...(2′) 我们观察式子的结构不难发现 这个式子只包含 r i , r i − 1 r_i,r_{i-1} ri,ri−1这两个已知量以及常数1以及 r i , r i − 1 r_i,r_{i-1} ri,ri−1前面的系数。 所以我们可以通过不断的消去 r i r_i ri使得最终的式子只包含 ( a , b , k ) (a,b,k) (a,b,k)。 最终的形式一定可以化简 a x b y 1 axby1 axby1。 必要性证毕。 战术总结 本节内容的主要内容如下 1、不定方程的简单介绍。 2、裴蜀定理介绍。 3、裴蜀定理的证明 先证明充分性 假定 a x b y c axbyc axbyc有解证出 ∀ c ∈ A , c 0 ∣ c \forall c\in A,c_0|c ∀c∈A,c0∣c进而得出 c 0 ∣ a , c 0 ∣ b c_0|a,c_0|b c0∣a,c0∣b即 c 0 c_0 c0是 a , b a,b a,b的公约数接着证明 a , b a,b a,b的任意约数 d d d都有 d ∣ c 0 d|c_0 d∣c0得出 c 0 c_0 c0是 a , b a,b a,b的最大公约数。此时证出若 a x b y c 0 axbyc_0 axbyc0有解则 c 0 g c d ( a , b ) c_0gcd(a,b) c0gcd(a,b)在等式两边乘以任意整数可得若 a x b y c axbyc axbyc有解则 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c 再证明必要性 即证明当 c 0 g c d ( a , b ) c_0gcd(a,b) c0gcd(a,b)的时候是否 a x b y c 0 axbyc_0 axbyc0成立两边除以 c 0 c_0 c0问题便转为证明当 g c d ( a , b ) 1 gcd(a,b)1 gcd(a,b)1 时 a ′ x b ′ y 1 axby1 a′xb′y1成立。这个等式由欧几里得算法可以得出是有解的。
