作者herstein (翔爸)
看板Math
标题Re: [中学] (h,k)=1 ====> (h+k,hk) = 1
时间Tue May 17 16:16:01 2011
※ 引述《idforyou (sad)》之铭言：
: 题目主要是给 两数相加的值 及两数的最小公倍数
: 求两数
: 看到计算过程中
: 有用到这概念
: (h,k)=1 则 (h+k,hk)=1
: 但印象中好像没学过这定理
: 有大大可以解说一下吗 thanks ..
假设d=(h+k,hk)不为1，由质因数分解定理可知，
d至少存在一个质因数p。所以p|(h+k)且p|hk。
由於p是质数且p|hk，则p至少是h或k的质因数。
不仿假设p|h。再利用p|h+k我们可知
p|h+k-h。可推得p|k，我们发现p是h与k的公因数。
但由於h与k互质，所以不存在这样的公因数。
於是假设错误，我们便推知d=1。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 128.120.178.219
1F：推 endlesschaos:推 很经典的反证法 05/17 18:55