设 a , b 是 两 个 不 全 为 零 的 整 数 ， 则 ( a , b ) = m i n 设a,b是两个不全为零的整数，则(a,b)=min 设a,b是两个不全为零的整数，则(a,b)=min{ s : s = a x + b y , ∀ x , y ∈ Z , s > 0 s:s=ax+by,{\forall}x,y\in Z,s>0 s:s=ax+by,∀x,y∈Z,s>0} 证 明 ： 证明： 证明： 由 辗 转 相 除 法 / 欧 几 里 得 算 法 ， 我 们 可 得 ( a , b ) = a t + b s , ∃ t , s ∈ Z , 现 在 令 d = a t ′ + b s ′ , t ′ , s ′ ∈ Z , 假 设 d < ( a , b ) , 则 d = a t ′ + b s ′ = ( a , b ) t ′ ′ t ′ + ( a , b ) s ′ ′ s ′ = ( a , b ) ( t ′ ′ t ′ + s ′ ′ s ′ ) 即 ( a , b ) ∣ d , 这 与 d < ( a , b ) 产 生 矛 盾 ， 所 以 ( a , b ) 是 a , b 的 线 性 组 合 中 最 小 的 由辗转相除法/欧几里得算法，我们可得(a,b)=at+bs,{\exists}t,s \in Z,\\ 现在令d=at'+bs',t',s'\in Z,假设d<(a,b),则\\ d=at'+bs'\\ =(a,b)t''t'+(a,b)s''s'\\ =(a,b)(t''t'+s''s')\\ 即(a,b)|d,这与d<(a,b)产生矛盾，所以(a,b)是a,b的线性组合中最小的 由辗转相除法/欧几里得算法，我们可得(a,b)=at+bs,∃t,s∈Z,现在令d=at′+bs′,t′,s′∈Z,假设d<(a,b),则d=at′+bs′=(a,b)t′′t′+(a,b)s′′s′=(a,b)(t′′t′+s′′s′)即(a,b)∣d,这与d<(a,b)产生矛盾，所以(a,b)是a,b的线性组合中最小的 ( a , b ) ∣ a t ′ + b s ′ ， 还 说 明 (a,b)|at'+bs'，还说明 (a,b)∣at′+bs′，还说明{ s = a x + b y , ∀ x , y ∈ Z , s > 0 s=ax+by,{\forall}x,y\in Z,s>0 s=ax+by,∀x,y∈Z,s>0} 这 个 集 合 是 a , b 的 最 大 公 因 数 的 倍 数 的 集 合 这个集合是a,b的最大公因数的倍数的集合 这个集合是a,b的最大公因数的倍数的集合
