最小公因数的性质证明

两个数的最小公因数小于大数的一半

数学语言:$gcd(a,b) \geq \cfrac{2}{max(a,b)}$

证明

设$a \lt b$,$gcd(a,b)=n$,$a=k_1n$,$b=k_2n$,其中$\{k_1,k_2\} \in N_+$。

假设$gcd(a,b) \gt \cfrac{2}{max(a,b)}$。

$\because a \lt b$

$\therefore k_1 \lt k_2$

$\because n \lt \cfrac a2$

$\therefore a \lt \cfrac{k_1a}{2}$,$b \lt \cfrac{k_2a}{2}$

$\therefore k_1 \gt 2$

$\because k_2 \lt k_1$,$k_2 \in N_+$

$\therefore k_2 = 1$,此时$a=b$,与假设矛盾。

$\therefore gcd(a,b) \geq \cfrac{2}{max(a,b)}$

Last modification:June 24th, 2019 at 09:45 am
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment