Để chứng minh hai bài toán trên, ta sẽ sử dụng tính chất cơ bản của ước chung lớn nhất (ƯCLN) như sau:

1. Chứng minh rằng ÖCLN(a, a + b) = ÖCLN(a, b):
Gọi d là ƯCLN của a và b, ta có a = dx và b = dy với x, y là các số nguyên không âm và ƯCLN(x, y) = 1.
Khi đó, a + b = dx + dy = d(x + y).
Ta thấy rằng d cũng chia hết cho a + b, do đó ƯCLN(a, a + b) = d = ƯCLN(a, b).

2. Chứng minh rằng ÖCLN(3n + 1, 2n + 1) = 1:
Gọi d là ƯCLN của 3n + 1 và 2n + 1, ta có:
3n + 1 = d*x và 2n + 1 = d*y với x, y là các số nguyên không âm và ƯCLN(x, y) = 1.
Từ đó, suy ra 3n + 1 - 2n - 1 = d*(x - y) => n = d*(x - y).
Ta thấy rằng d cũng chia hết cho n, do đó ƯCLN(3n + 1, 2n + 1) = d = 1.

Vậy ta đã chứng minh được hai bài toán trên.