用辗转相除法判断1547和3135是否互质,要用辗转相除法计算,要写清!

分类: 作业答案 • 2021-12-19 17:21:38

问题描述：

用辗转相除法判断
1547和3135是否互质,要用辗转相除法计算,要写清!

答

3135=1547*2+41（即只要求 44 和 1547 的最大公约数即可）
1547=41*37+30 （同理）
41=30*1+11
30=11*2+8
11=8*1+3
8=3*2+2
3=2*1+1
所以 1 是他们的公约数,即两者互质