Buktikan bahwa (n n1, n2)=(n n1)=(n n2)

Menggunakan sifat FPB (a,b) = (a-b, b), maka (n+m, n) = (n+m-n, n) = (m, n) = (n, m).

Pembahasan

Untuk membuktikan kesamaan $(n + m, n) = (n, m)$, kita menggunakan sifat-sifat dari Faktor Persekutuan Terbesar (FPB) atau greatest common divisor (GCD).

Menurut definisi FPB:
FPB(a, b) adalah bilangan bulat positif terbesar yang dapat membagi habis a dan b.

Kita tahu bahwa:
FPB(a, b) = FPB(a - b, b)
FPB(a, b) = FPB(a + b, b)
FPB(a, b) = FPB(a, b - a)
FPB(a, b) = FPB(a, b + a)

Mari kita terapkan sifat ini pada $(n + m, n)$:
$(n + m, n) = (n + m - n, n)$
$(n + m, n) = (m, n)$

Karena urutan dalam FPB tidak penting, yaitu $(m, n) = (n, m)$, maka terbukti bahwa $(n + m, n) = (n, m)$.

Ini adalah aplikasi dari Algoritma Euklides, yang menyatakan bahwa FPB dari dua bilangan tidak berubah jika bilangan yang lebih besar dikurangi dengan bilangan yang lebih kecil.