谁能向我详细介绍以下欧几里德算法?
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:数学作业 时间:2024/04/30 04:49:30
谁能向我详细介绍以下欧几里德算法?
欧几里德算法就是辗转相除法,用来求最大公约数
求a和b的最大公约数(a,b),假设a>b
若a能被b整除,则a和b的最大公约数(a,b)=1
若a不能被b整除,则求出a除以b的余数c,再用b除以c,若整除,则(a,b)=c.若不能整除,再求出b除以c的余数d,再用c除以d,以此类推,到哪一步整除了,那个除数就是最大公约数.
举例如下
求207900和41262的最大公约数
207900/41262=5余1590
41262/1590=25余1512
1590/1512=1余78
1512/78=19余30
78/30=2余18
30/18=1余12
18/12=1余6
12/6整除
所以207900和41262的最大公约数是6
求a和b的最大公约数(a,b),假设a>b
若a能被b整除,则a和b的最大公约数(a,b)=1
若a不能被b整除,则求出a除以b的余数c,再用b除以c,若整除,则(a,b)=c.若不能整除,再求出b除以c的余数d,再用c除以d,以此类推,到哪一步整除了,那个除数就是最大公约数.
举例如下
求207900和41262的最大公约数
207900/41262=5余1590
41262/1590=25余1512
1590/1512=1余78
1512/78=19余30
78/30=2余18
30/18=1余12
18/12=1余6
12/6整除
所以207900和41262的最大公约数是6
谁能详细介绍以下汽车内燃机的工作原理?
有谁知道微生物在农药降解中的作用?希望能详细的给我介绍以下,
哪个能向我详细介绍一下英国泰晤士报(the Times)的情况?
数控加工中心坐标系~谁 能详细的给我介绍介绍加工中心的坐标系啊 1 机械坐标,从哪里到哪里?怎么算法?2 绝对坐标,从哪
谁能详细给我介绍一下费米气体
谁能给我详细的介绍一下《忆秦娥 娄山关》
谁能给我详细介绍墨西哥湾漏油事件?
谁能把详细的弟子规,介绍给我
谁能向我介绍一下聚二氟乙烯
谁能详细介绍木卫二?
谁能详细介绍费马点?
关于扩展欧几里德算法我要用扩展欧几里德算法计算-n*n' % r=1等式中的n',其中n为已知非负奇数,r=2^k,想问