Để chứng minh điều phải chứng minh, ta sẽ sử dụng định lí Euclid về ƯCLN: "ƯCLN(a,b) = ƯCLN(b, a mod b)".

Ta có:
a mod b = a - b
a + b mod (a - b) = a - b
Vậy theo định lí Euclid, ta có:
ƯCLN(a,b) = ƯCLN(b, a - b)

Ta sẽ chứng minh rằng ƯCLN(b, a - b) = ƯCLN(a + b, a - b).

Gọi d = ƯCLN(b, a - b), ta có:
b = d * x
a - b = d * y
trong đó x, y là các số nguyên.

Từ hai phương trình trên, ta có:
a = b + d * y
a = d * x + d * y
a = d * (x + y)

Tương tự, ta có:
a + b = d * (x + y) + d
a - b = d * (x + y) - d

Vậy ta có:
ƯCLN(a + b, a - b) = ƯCLN(d * (x + y) + d, d * (x + y) - d)
= ƯCLN(d, d)
= d

Vậy ta chứng minh được rằng ƯCLN(a,b) = ƯCLN(a+b, a-b).