Question

python输入两个正整数,判断他们是否为互质数

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<=m<p,因为x是正整数)
有：
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=<m<p
所以有：
0=<(by+ap-n)/a<p,
解得：
（n-ap）/b=<y<n/b，
p是n的整数部分，就有n<2p=<ap（说明下：一个分数的整数部分是
肯定比分数部分大的，所以可得
n<2p）
于是n-ap<0,所以y最终的范围是（0，n/b）,且y为正整数，可见：
确实存在这样的y,能使m为一在确定范围内的整数，反之，易知：
存在m，可使y=(by+ap-n)/a为整数。
好难的问题啊，我想了好久的。纯手打得阿，采纳以下阿

Answer 2

根据互质数的定义，可总结出一些规律，利用这些规律能迅速判断一组数是否互质。
（1）两个不相同的质数一定是互质数。如：7和11、17和31是互质数。
（2）两个连续的自然数一定是互质数。如：4和5、13和14是互质数。
（3）相邻的两个奇数一定是互质数。如：5和7、75和77是互质数。
（4）1和其他所有的自然数一定是互质数。如：1和4、1和13是互质数。
（5）两个数中的较大一个是质数，这两个数一定是互质数。如：3和19、16和97是互质数。
（6）两个数中的较小一个是质数，而较大数是合数且不是较小数的倍数，这两个数一定是互质数。如：2和15、7和54是互质数。
（7）较大数比较小数的2倍多1或少1，这两个数一定是互质数。如：13和27、13和25是互质数。