Can we reduce now?

$gcd(2839+n,4520+n)=gcd(2839+n,1681)=gcd(2839+n,41\times 41)$

we want the GCD to be something but one. So, either $41 | 2839+n$ or $41^2 | 2839$ . The smallest $n$ comes for $41 | 2839+n$ when $n=31$

Let 2839 + n = pk and 4520 + n = pm. Adding, 7359 + 2n = p(k + m); subtracting, 1681 = p(m - k). But 1681 = 41^2, so p = 41. Now 7359 + 2n = 41(k + m); but 7339 .cong. 0 (mod 41), so 7339 + 20 + 2n = 41(k + m), and 20 + 2n is divisible by 41, so 20 + 2n = 82, 2n = 62, and n = 31.