一道初等数论题的推到已知两个正整数 a,b 互质若正整数n>=a*b那么ax+by=nx y一定存在一组正整数解换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程如 3 7 那么 22 可以表示

Question

一道初等数论题的推到
已知两个正整数 a,b 互质
若正整数n>=a*b
那么ax+by=n
x y一定存在一组正整数解
换句话说 大于a*b的整数都可以用 a,b 的x y整数倍表示 求推导过程
如 3 7 那么 22 可以表示为5 * 3 +1 * 7 .

Answer 1

首先,根据条件,正整数加法乘法后还是正整数,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