Proof: if c is a common factor of a and b, then c is a factor of gcd(a,b)

The notion of of gcd(a,b) here means the greatest common divisor of a and b.

Since c is a factor of a,b, there must be 2 integers m,n which satisfy:

a = mc
b = nc

Let d = gcd(a,b). By Bézout's identity, there exist 2 integers x,y such that:

d = xa + yb

After subsituting a,b, we get:

d = xmc + ync
  = (xm + yn)c

Becasue d is the greatest common divisor of a,b, we know d ≥ c > 0. xm + yn must be positive.

Because m,n,x,y are all integers, xm + yn must also be an integer.

Which leats to the conclusion that xm + yn must be a positive integer. d is a multiple of c. ie c is a factor of gcd(a,b). QED.

本文為〈證明：若 c 為 a 與 b 之共同因數，則 c 為 gcd(a,b) 之因數。〉之英文版。