jmc

Question

As n ranges over the positive integers, what is the maximum possible value that the greatest common divisor of 13n + 8 and 5n+3 can take?

Accepted Answer

We can apply the Euclidean algorithm here. align* (13n+8, 5n+3) &= (5n+3, (13n+8)-2(5n+3)) &= (5n+3, 3n + 2) &= (3n+2, (5n+3)-(3n+2)) &= (3n+2, 2n + 1) &= (2n+1, (3n+2)-(2n+1)) &= (2n+1, n+1) &= (n+1, (2n+1)-(n+1)) &= (n+1, n) &= (n, (n+1)-n) &= (n, 1) &= 1. align*