早教吧 育儿知识 作业答案 考试题库 百科 知识分享

一道初等数论题的推到已知两个正整数 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 .
▼优质解答
答案和解析
首先,根据条件,正整数加法乘法后还是正整数,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