一道初等数论题的推到已知两个正整数 a,b 互质若正整数n>=a*b那么ax+by=nx y一定存在一组正整数解换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程如 3 7 那么 22 可以表示
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/23 05:46:24
一道初等数论题的推到已知两个正整数 a,b 互质若正整数n>=a*b那么ax+by=nx y一定存在一组正整数解换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程如 3 7 那么 22 可以表示
一道初等数论题的推到
已知两个正整数 a,b 互质
若正整数n>=a*b
那么ax+by=n
x y一定存在一组正整数解
换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程
如 3 7 那么 22 可以表示为5 * 3 +1 * 7 .
一道初等数论题的推到已知两个正整数 a,b 互质若正整数n>=a*b那么ax+by=nx y一定存在一组正整数解换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程如 3 7 那么 22 可以表示
首先,根据条件,正整数加法乘法后还是正整数,n是一个正整数.
不妨设a>b(因为a、b互质,
n=a*x+b*y
n=a(x+(b/a)*y)
n/a=x+(b/a)*y
因为a、b互质,所以b/a是真分数；
而n>a且n>b,所以n/a必定是假分数,
令其整数部分为p,分数部分就是(n/a)-p=（n-ap）/a；（其中p为整数）
于是比较两边有：
p+(n-ap)/a=x+(b/a)*y 两边变形得：
p-m+(n-ap+am)/a=x+（by）/a； (其中0
52*38+23*26
=52*38+(23/2)*(26*2)
=52*38+11.5*52
=52*(38+11.5)
=52*39.5
=52*(40-0.5)
=52*40-52*0.5
=2080-26
=2054
首先，根据条件，正整数加法乘法后还是正整数，n是一个正整数。
不妨设a>b(因为a、b互质，不会相等)
n=a*x+b*y
n=a(x+(b/a)*y)
n/a=x+(b/a)*y
因为a、b互质，所以b/a是真分数；
而n>a且n>b,所以n/a必定是假分数，
令其整数部分为p,分数部分就是(n/a)-p=（n-ap）/a；（其中p...
全部展开
首先，根据条件，正整数加法乘法后还是正整数，n是一个正整数。
不妨设a>b(因为a、b互质，不会相等)
n=a*x+b*y
n=a(x+(b/a)*y)
n/a=x+(b/a)*y
因为a、b互质，所以b/a是真分数；
而n>a且n>b,所以n/a必定是假分数，
令其整数部分为p,分数部分就是(n/a)-p=（n-ap）/a；（其中p为整数）
于是比较两边有：
p+(n-ap)/a=x+(b/a)*y 两边变形得：
p-m+(n-ap+am)/a=x+（by）/a； (其中0<=m
x=p-m,且by=n-ap+am
解得：
x=p-m,且y=(n-ap+am)/b
下面就是要证存在这个m，使y为正整数，也可以说是，找到正整数对（m,y）
由by=n-ap+am 得：
m=(by+ap-n)/a,而0=
0=<(by+ap-n)/a
n<2P）
于是n-ap<0,所以y最终的范围是（0，n/b）,且y为正整数，可见：
确实存在这样的y,能使m为一在确定范围内的整数，反之，易知：
存在m，可使y=(by+ap-n)/a为整数。
收起