早教吧作业答案频道 -->数学-->
欧几里得算法提问在看下面证明时有些不明白——————————————————————————————————欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数.
题目详情
欧几里得算法提问
在看下面证明时有些不明白
——————————————————————————————————
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数.其计算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数,则
d | b ,d |r ,但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
-—————————————————————————————————
d|a是d除以a还是d%a?
因为如果是d除以a的话怎么也想不明白,所以我认为是d%a
即使是而r = a - kb怎么就能得到d|r的结论?
本人是个数学初学者,请多多关照
在看下面证明时有些不明白
——————————————————————————————————
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数.其计算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数,则
d | b ,d |r ,但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
-—————————————————————————————————
d|a是d除以a还是d%a?
因为如果是d除以a的话怎么也想不明白,所以我认为是d%a
即使是而r = a - kb怎么就能得到d|r的结论?
本人是个数学初学者,请多多关照
▼优质解答
答案和解析
问题一 d|a表示d整除a,也就是说d是a的一个因子.
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数 --------这一步很简单,d|a,d|b,而r = a - kb,d当然能整除r(因为d是a 和b的因子,当然也是r = a - kb的因子)
假设d 是(b,a mod b)的公约数,则
d | b ,d |r ,但是a = kb +r
因此d也是(a,b)的公约数 ---------d | b ,d |r ,而a= kb +r ,当然d|a,即d是a 和b 的公约数.
通过上两步,d既然是a,b的公约数,也是b和a mod b的公约数,这就证明了欧几里得算法.
你说的问题二 ,因为d整除a,而且d整除b,d当然能整除r = a - kb.
举个例子 3|12 ,3|15,3当然整除12-15k(k为整数).
证明:a可以表示成a = kb + r,则r = a mod b
假设d是a,b的一个公约数,则有
d|a,d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公约数 --------这一步很简单,d|a,d|b,而r = a - kb,d当然能整除r(因为d是a 和b的因子,当然也是r = a - kb的因子)
假设d 是(b,a mod b)的公约数,则
d | b ,d |r ,但是a = kb +r
因此d也是(a,b)的公约数 ---------d | b ,d |r ,而a= kb +r ,当然d|a,即d是a 和b 的公约数.
通过上两步,d既然是a,b的公约数,也是b和a mod b的公约数,这就证明了欧几里得算法.
你说的问题二 ,因为d整除a,而且d整除b,d当然能整除r = a - kb.
举个例子 3|12 ,3|15,3当然整除12-15k(k为整数).
看了欧几里得算法提问在看下面证明时...的网友还看了以下:
紫色的菜放在白水里,白醋里,和含碱的水里各有什么变化?紫色的菜放在白水里,白醋里,和含碱的水里各有 2020-05-12 …
根据信息,填写合适的化学术语:(1)冰箱里常用活性炭除异味,这是利用了活性炭的性;(2)实验室里, 2020-05-13 …
如何求集合的上下极限这个是实变函数里集合运算里德内容,可是我不是很明白,始终没有明白它的概念和求极 2020-05-14 …
黑旋风斗浪里白跳的故事概括 2020-05-16 …
在《水浒传》中,李逵是一个性格鲜明的人.请结合“黑旋风斗浪里白条”的故事简述他的性格特征.150字 2020-05-16 …
在括号里写出句子的修辞手法,应用该修辞手法在写一句话阳光从脚尖悄悄爬上膝盖,也想着“黑旋风”水战“ 2020-05-16 …
Excel表格里,除法公式怎么用呀,在一个己经数据的一个表格里,己经发出除法公式,但是现在我要改变 2020-05-17 …
箱子里有红、白两种玻璃球,红球是白球数的3倍多2个.从箱子里取出7个白球,再放进7个红球.这时箱子 2020-05-20 …
有时早晨的天空先是红色的,后又变成黄色,这是怎么引起的?比较罕见,在很早的时候天上不是只有接近太阳 2020-06-11 …
凯氏定氮法的空白试验。。。。取与处理样品相同量的硫酸铜、硫酸钾、硫酸按同一方法做试剂空白试验。上面 2020-06-19 …