|
本帖最后由 yangchuanju 于 2021-2-3 06:34 编辑
现学现卖
二元一次不定方程ax+by=2n-1的整数解
二元一次不定方程的一般形式为ax+by=c。其中 a,b,c 是整数,ab ≠ 0。此方程有整数解的充分必要条件是a、b的最大公约数整除c。
若a、b互质(互素),即它们的最大公约数为1,(x0,y0)是所给方程的一个解, 则此方程的解可表为{(x=x0+bt,y=y0-at)|t为任意整数}。
例: 求11x+15y=7的整数解.
解: 将方程变形得x=(7-15y)/11,
因为x是整数,所以7-15y应是11的倍数.由观察得x0=2,y0=-1是这个方程的一组整数解,所以方程的解为
x=2+15t, y=-1-11t;式中t为任意整数。
t———— 0 1 2 3 4 5 6
x= 2+15t 2 17 32 47 62 77 92
y=-1-11t -1 -12 -23 -34 -45 -56 -67
验算—— 7 7 7 7 7 7 7
一般地,x=x0+b/(a,b)*t, y=y0-a/(a,b)*t;式中(a,b)是系数a和b的最大公约数;
特别地,当a和b互素时,二元一次不定方程ax+by=c的解为x=x0+bt, y=y0-a,式中t是任意整数。
二元一次不定方程ax+by=c有无穷多组整数解。
以上论述和例题根据360百科《不定方程》整理。
若要求系数a和b必须是与30互素的整数时,由于(a,b)=1整数解的形式变得稍微简单一些。
令n=1,2n-1=c=1,不定方程为ax+by=1,变形x=(1-by)/a,1-by必须是a的倍数,
令a=1,b=1,不定方程为x+y=1,观察得x0=1,y0=0,(a,b)=1;x=1+t,y=0-t
t 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
y 0 -1 -2 -3 -4 -5 -6
验算c 1 1 1 1 1 1 1
令a=1,b=7,不定方程为x+7y=1,观察得x0=1,y0=0,(a,b)=1;x=1+7t,y=0-t
t 0 1 2 3 4 5 6
x 1 8 15 22 29 36 43
y 0 -1 -2 -3 -4 -5 -6
验算c 1 1 1 1 1 1 1
令a=1,b=11,不定方程为x+11y=1,观察得x0=1,y0=0,(a,b)=1;x=1+11t,y=0-t
t 0 1 2 3 4 5 6
x 1 12 23 34 45 56 67
y 0 -1 -2 -3 -4 -5 -6
验算c 1 1 1 1 1 1 1
令a=7,b=11,不定方程为7x+11y=1,观察得x0=8,y0=-5,(a,b)=1;x=8+11t,y=-5-7t
t 0 1 2 3 4 5 6
x 8 19 30 41 52 63 74
y -5 -12 -19 -26 -33 -40 -47
验算c 1 1 1 1 1 1 1
令n=2,2n-1=c=3,不定方程为ax+by=3,变形x=(3-by)/a,3-by必须是a的倍数,
令a=1,b=1,不定方程为x+y=3,观察得x0=1,y0=2,(a,b)=1;x=1+t,y=2-t
t 0 1 2 3 4 5 6
x 1 2 3 4 5 6 7
y 2 1 0 -1 -2 -3 -4
验算c 3 3 3 3 3 3 3
令a=1,b=7,不定方程为x+7y=3,观察得x0=3,y0=0,(a,b)=1;x=3+7t,y=0-t
t 0 1 2 3 4 5 6
x 3 10 17 24 31 38 45
y 0 -1 -2 -3 -4 -5 -6
验算c 3 3 3 3 3 3 3
令a=1,b=11,不定方程为x+11y=3,观察得x0=3,y0=0,(a,b)=1;x=3+11t,y=0-t
t 0 1 2 3 4 5 6
x 3 14 25 36 47 58 69
y 0 -1 -2 -3 -4 -5 -6
验算c 3 3 3 3 3 3 3
令a=7,b=11,不定方程为7x+11y=3,观察得x0=2,y0=-1,(a,b)=1;x=2+11t,y=-1-7t
t 0 1 2 3 4 5 6
x 2 13 24 35 46 57 68
y -1 -8 -15 -22 -29 -36 -43
验算c 3 3 3 3 3 3 3
当a和b只能取与30互素数,在第一周期(1-30)范围内,a,b取值为8*8=64种,n的取值15种,共64*15=960种组合,每一种都有无穷多组解。
令c=2n-1,二元一次不定方程为ax+by=2n-1,变形得x=(2n-1-by)/a,2n-1-by必须是a的倍数,
令a=a0,b=b0,不定方程为a0*x+b0*y=2n-1,设法求得一组x0和y0,由于a和b都与30互素,所以(a,b)=1;x=x0+b0*t,y=y0-a0*t,t为任意整数。
|
|