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:
Jika \( \gcd(a, b) = 1 \) maka \( \gcd(ab, a + b) = 1 \)

Pembuktian melalui kontradiksi sebagai berikut:

Asumsikan \( \gcd(ab, a + b) = k \) dimana \( k \gt 1 \) dan \( k \in \mathbb{Z} \)

Karena \( k \gt 1 \) maka \( k \) mempunyai setidak-tidaknya satu faktor bilangan prima. Katakanlah faktor prima tersebut adalah \( p \).
Karena \( \gcd(ab, a + b) = k \) maka \( k \) pasti habis membagi \( ab \) dan \( a + b \). Akibatnya, \( p \) juga pasti habis membagi \( ab \) dan \( a + b \).

Perhatikan ekspresi \( ab \).
Dari lemma Euclid, karena \( p \) habis membagi \( ab \) maka \( p \) habis membagi setidak-tidaknya salah satu dari \( a \) atau \( b \). Tanpa menghilangkan sifat umum (without loss of generality), anggap saja \( p \) adalah faktor dari \( a \). Artinya \( a = pm \)

Sekarang, perhatikan ekspresi \( a + b \).
Karena \( p \) habis membagi \( a + b \) maka \( a + b = pn \)
\( \begin{align*} a + b &= pn \\ b &= pn - a \\ b &= pn - pm \\ b &= p(n - m) \end{align*} \)

Terlihat jelas bahwa ternyata \( p \) juga adalah faktor dari \( b \).

Karena \( a \) dan \( b \) dua-duanya mempunyai faktor \( p \), maka setidak-tidaknya GCD dari \( a \) dan \( b \) adalah \( p \). Karena bilangan prima pasti lebih besar dari \( 1 \), maka \( \gcd(a, b) \gt 1 \). Terjadi kontradiksi. Artinya, asumsi yang dibuat di awal salah dan \( \gcd(ab, a + b) \) haruslah \( 1 \).

Membuktikan implikasi 2

Implikasi 2:
Jika \( \gcd(ab, a + b) = 1 \) maka \( \gcd(a, b) = 1 \)

Pembuktian melalui kontradiksi sebagai berikut:

Asumsikan \( \gcd(a, b) = k \) dimana \( k \gt 1 \) dan \( k \in \mathbb{Z} \)

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 \):
\( \begin{align*} ab &= km \cdot kn \\ &= k^2mn \end{align*} \)

Sekarang, perhatikan ekspresi \( a + b\):
\( \begin{align*} a + b &= km + kn \\ &= k(m + n) \end{align*} \)

Terlihat jelas bahwa \( ab \) dan \( a + b \) keduanya mempunyai faktor \( k \). Artinya, GCD \( ab \) dan \( a + b \) setidak-tidaknya bernilai \( k \). Karena \( k \gt 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 \)