作业帮如何判断互素数
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/30 12:58:39
如何判断互素数
如何判断互素数
如何判断互素数
判断两数是否互素就是判断该两数有无1以外的公约数,如果只有“1”这个公约数,则两数互素.有两个方法.1、将两数分别分解质因数后,观察有无1以外的公约数.
2、用“辗转相除法”求公约数.先用小数除大数（即大数除以小数）,得商及余数,再用余数除小数,得新的商及余数,再用此余数除上次余数……如此辗转相除,至余数为1时,判定原两数互素；若相除至余数为0（无余数）,则两数还有一个公约数（为最后相除时的除数）.
例1 、 343和91 343÷91=3余70,91÷70=1余21,70÷21=3余7,21÷7=3.无余数,说明243和91有公约数1及7.例2、 71和22 71÷22=3余5 ,22÷5=4余2,5÷2=2余1.说明71和22是互素的.
两种判断方法熟练后,还可以做得更简化一些.如例1中至70÷21时即可断定有公约数7.