两个互质整数的线性组合问题 |
您所在的位置:网站首页 › a和b互为质数,a+b的值最小是多少 › 两个互质整数的线性组合问题 |
两个互质整数的线性组合问题
本文我们讨论两个互质整数的线性组合问题,以及相关的二元一次不定方程。 两个互质整数的线性组合已知两个整数 a a a和 b b b互质,即 gcd ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1,那么对于任意两个非负整数 x , y x,y x,y来说,线性组合 a x + b y ax+by ax+by,能表示的整数数是多少,不能表示的整数又是多少,最大是多少,以及不能表示的整数的个数是多少呢? 能表示整数的下界设能表示的数为 K K K,则有 a x + b y = K ax+by=K ax+by=K,对两边同时取 b b b的模,则 a x m o d b = K m o d b ax \mod b=K \mod b axmodb=Kmodb,即为线性同余方程 a x ≡ K m o d b ax \equiv K \mod b ax≡Kmodb。又因为 gcd ( a , b ) = 1 \gcd(a,b) = 1 gcd(a,b)=1,因此该线性同余方程一定有解,且有一个解,但是这个解必须满足实际,即 x ≥ 0 , y ≥ 0 x \geq 0,y \geq 0 x≥0,y≥0。 题目中说凑不出来一个数 K K K,说明 a x + b y = K ax+by=K ax+by=K,中 x ≥ 0 , y < 0 x \geq 0,y \lt 0 x≥0,y |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |