Karena ini adalah biimplikasi (jika dan hanya jika), maka ada dua implikasi yang harus dibuktikan:

1. Jika $\gcd (a,b)=1$ maka $\gcd (ab,a+b)=1$
2. Jika $\gcd (ab,a+b)=1$ maka $\gcd (a,b)=1$

Membuktikan implikasi 1

Implikasi 1 akan dibuktikan melalui kontradiksi.

Asumsikan $\gcd (ab,a+b)=k$ dimana $k>1$

Karena $\gcd (ab,a+b)=k$ maka $k$ pasti habis membagi $ab$ dan $a+b$.

Perhatikan ekspresi $ab$. Karena $k$ habis membagi $ab$ maka setidak-tidaknya salah satu faktor dari $a$ atau $b$ adalah $k$ . Tanpa menghilangkan sifat umum (without loss of generality), anggap saja $k$ adalah faktor dari $a$. Artinya $a=km$

Sekarang, perhatikan ekspresi $a+b$. Karena $k$ habis membagi $a+b$ maka $a+b=kn$

$a+b=kn$
$b=kn-a$
$b=kn-km$
$b=k(n-m)$

Terlihat jelas bahwa ternyata $k$ juga adalah faktor dari $b$.

Sekarang, karena $a$ dan $b$ dua-duanya mempunyai faktor $k$, maka setidak-tidaknya GCD dari $a$ dan $b$ adalah $k$. Karena tadi di awal diasumsikan $k>1$ maka terjadi kontradiksi. Artinya, asumsi yang dibuat di awal salah dan $\gcd (ab,a+b)$ haruslah $1$.

Membuktikan implikasi 2

Implikasi 2 juga akan dibuktikan melalui kontradiksi.

Asumsikan $\gcd (a,b)=k$ dimana $k>1$

Karena $\gcd (a,b)=k$ maka baik $a$ dan $b$ kedua-duanya pasti mempunyai faktor $k$. Katakanlah $a=km$ dan $b=kn$

Perhatikan ekspresi $ab$:
$ab=km\cdot kn$
$ab=k^{2}mn$

Sekarang, perhatikan ekspresi $a+b$:
$a+b=km+kn$
$ab=k(m+n)$

Terlihat jelas bahwa baik $ab$ dan $a+b$ keduanya mempunyai faktor $k$. Artinya, GCD $ab$ dan $a+b$ setidak-tidaknya bernilai $k$. Karena $k>1$ maka terjadi kontradiksi. Artinya, asumsi yang dibuat di awal salah dan $\gcd (a,b)$ haruslah $1$.

Kesimpulan

Karena kedua implikasi sudah dibuktikan. Maka terbuktilah biimplikasi $\gcd (a,b)=1$ jika dan hanya jika $\gcd (ab,a+b)=1$