# Show that gcd(9t+4, 2t+1)=1 for all integers tElementary number theory

### 2 Answers | Add Yours

The gcd of two numbers a and b is equal to (a*b)/lcm(a,b)

For 9t+4 and 2t+1, we have

gcd(9t+4, 2t+1) = (9t+4)(2t+1)/lcm((9t+4),(2t+1))

9t+4 = 4(2t+1)+t. 4(2t+1)+t is a multiple of 2t+1 only when 2t+1 = t or t = -1. When t = -1, 9t+4 = -5 and 2t+1=-1. -5 and -1 have a gcd of 1. If 2t+1 is not equal to t, 4(2t+1)+t cannot be a multiple of 2t+1. The lcm of (9t+4) and (2t+1) is therefore equal to (9t+4)(2t+1)

The value of the gcd of the two terms is given by (9t+4)(2t+1)/(9t+4)(2t+1) = 1

**This proves that the gcd of (9t+4) and (2t+1) is 1**.

Why is 4(2t+1)+t a multiple of 2t+1 only when 2t+1=t<=>t=-1?