Code:
gcd(3n+4, 2n+3) ; n>0
=gcd(3n+4 - (2n+3), 2n+3) ; 3n+4 > 2n+3
=gcd(n+1, 2n+3)
=gcd(n+1, 2n+3-n-1) ; 2n+3 > n+1
=gcd(n+1, n+2)
=gcd(n+1, n+2-n-1) ; n+1 < n+2
=gcd(n+1, 1)
=gcd(n, 1)
=1
if n<=0
gcd(3*0+4, 2*0+3)=gcd(4, 3) = 1
gcd(3*(-1)+4, 2*(-1)+3)=gcd(1, 1) = 1
เรากำหนดให้ $gcd(2a+b, a+2b)=d; d\in \mathbb{N} $
จะได้ว่า d หาร 2a+b ลงตัว และ d หาร a+2b ลงตัว นั้นคือ จะมี $m,n \in \mathbb{N} $ ซึ่ง
$2a+b=md$
$a+2b=nd$
เมื่อเอามาบวกลบกัน จะได้ว่า
$3a=d(2m-n)$
$3b=d(2n-m)$
โจทย์กำหนดให้ $gcd(a, b)=1$ จะได้ว่า
$3gcd(a, b)=3$
$gcd(3a, 3b)=3$
$gcd(d(2m-n) , d(2n-m))=3$
$d\times gcd((2m-n) , (2n-m))=3$
นั้นคือ d หาร 3 ลงตัว และ $0<d<=3$ d จึงเป็น 1 หรือ 3