如何判断互素数
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/08/18 04:34:10
如何判断互素数
![如何判断互素数](/uploads/image/z/16340049-9-9.jpg?t=%E5%A6%82%E4%BD%95%E5%88%A4%E6%96%AD%E4%BA%92%E7%B4%A0%E6%95%B0)
判断两数是否互素就是判断该两数有无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.
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.