欧几里得原理(辗转相除法)
创始人
2025-06-30 02:36:47
欧几里得原理(辗转相除法)
就是把上一轮有余数的除法计算中，
除数变为下一轮计算的被除数，
余数变为下一轮计算的除数，
一直这样计算下去，
直到最后一次计算余数为零，
在最后一轮计算中的被除数，即为所求的最大公约数。
举例：
105和85的最大公约数
第一轮计算
105÷85=1...20
第二轮计算
85÷20=4...5
第三轮计算
20÷5=4
第三轮没有余数，
因此
105和85的最大公约数就是第三轮计算的被除数
5.
至于c语言编程，下边是我自己写的g函数(思想就是辗转相除法求最大公约数)
int
g(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}
“|”表示整除
如果存在整数d，使得bc=a*d。那么就称a整除bc，用“a|bc”表示。
首先，该定理是正确的！
|是整除的意思，a|b表示存在整数c使b=ac
证明：因为(a,b)=1,所以存在整数x,y使得ax+by=1
故acx+bcy=c
又a|bc,所以a|acx+bcy即a|c
证毕！
若a|bc,(a,b)=1,则a|c
翻译：若整数a能整除b、c的乘积，且a、b的最大公约数是1，则a能整除c.
这个“|”是“整除”的意思。（除数在前，被除数在后）
就是把上一轮有余数的除法计算中，
除数变为下一轮计算的被除数，
余数变为下一轮计算的除数，
一直这样计算下去，
直到最后一次计算余数为零，
在最后一轮计算中的被除数，即为所求的最大公约数。
举例：
105和85的最大公约数
第一轮计算
105÷85=1...20
第二轮计算
85÷20=4...5
第三轮计算
20÷5=4
第三轮没有余数，
因此
105和85的最大公约数就是第三轮计算的被除数
5.
至于c语言编程，下边是我自己写的g函数(思想就是辗转相除法求最大公约数)
int
g(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}
“|”表示整除
如果存在整数d，使得bc=a*d。那么就称a整除bc，用“a|bc”表示。
首先，该定理是正确的！
|是整除的意思，a|b表示存在整数c使b=ac
证明：因为(a,b)=1,所以存在整数x,y使得ax+by=1
故acx+bcy=c
又a|bc,所以a|acx+bcy即a|c
证毕！
若a|bc,(a,b)=1,则a|c
翻译：若整数a能整除b、c的乘积，且a、b的最大公约数是1，则a能整除c.
这个“|”是“整除”的意思。（除数在前，被除数在后）
相关内容
热门资讯
山水皆有情！丽江两山一江的千年...
去过丽江、走过虎跳峡的人，大概率都听过哈巴雪山和金沙江的传说。很多人站在峡谷之下，望着奔腾不息的金沙...
活力中国调研行丨“殷”你而来 ...
9月12日，游客在殷墟博物馆“甲骨文展厅”内参观。位于河南省安阳市的殷墟博物馆新馆是首个全景式展现商...
浦江之夜赴美好相逢，第37届上...
9月12日晚，黄浦江畔灯火璀璨，第37届上海旅游节大巡游在外滩中山东一路上演。不少观众早早便来到外滩...
美丽中国丨秋韵紫鹊界 梯田入画...
这是9月11日拍摄的紫鹊界梯田（无人机照片）。 金秋九月，湖南省娄底市新化县紫鹊界梯田稻谷渐次成熟。...
中国之巅奏响《共同的节日》，千...
千吨阻尼器，“迎世赛、游上海旅游节”。9月13日，由上海市文化和旅游局指导推出上海旅游·会客│巅峰之...