问下关于求最大公约数的问题~8251=6105×1+2146“8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了.”为什么说“8251和6105的公约数就是6105和21
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/02 07:33:51
![问下关于求最大公约数的问题~8251=6105×1+2146“8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了.”为什么说“8251和6105的公约数就是6105和21](/uploads/image/z/14507801-17-1.jpg?t=%E9%97%AE%E4%B8%8B%E5%85%B3%E4%BA%8E%E6%B1%82%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0%E7%9A%84%E9%97%AE%E9%A2%98%7E8251%3D6105%C3%971%2B2146%E2%80%9C8251%E5%92%8C6105%E7%9A%84%E5%85%AC%E7%BA%A6%E6%95%B0%E5%B0%B1%E6%98%AF6105%E5%92%8C2146%E7%9A%84%E5%85%AC%E7%BA%A6%E6%95%B0%2C%E6%B1%828251%E5%92%8C6105%E7%9A%84%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0%2C%E5%8F%AA%E8%A6%81%E6%B1%82%E5%87%BA6105%E5%92%8C2146%E7%9A%84%E5%85%AC%E7%BA%A6%E6%95%B0%E5%B0%B1%E5%8F%AF%E4%BB%A5%E4%BA%86.%E2%80%9D%E4%B8%BA%E4%BB%80%E4%B9%88%E8%AF%B4%E2%80%9C8251%E5%92%8C6105%E7%9A%84%E5%85%AC%E7%BA%A6%E6%95%B0%E5%B0%B1%E6%98%AF6105%E5%92%8C21)
问下关于求最大公约数的问题~8251=6105×1+2146“8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了.”为什么说“8251和6105的公约数就是6105和21
问下关于求最大公约数的问题~
8251=6105×1+2146
“8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了.”
为什么说“8251和6105的公约数就是6105和2146的公约数”?
麻烦解释的详细点……呵呵,脑子不好使.
问下关于求最大公约数的问题~8251=6105×1+2146“8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了.”为什么说“8251和6105的公约数就是6105和21
这叫欧几里德算法,又叫辗转相除法
2146=8251 mod 6105
8251=2146+a*6105 (此处a等于1)
假设b是8251 6105的公约数 ,那么6105能被b整除 ,8251也能被b整除 从而证明2146=8251-a*6105也能被b整除 .
所以所有8251 6105的公约数 都是2146 6105的公约数
所以 两个的最大公约数 也相同