Problem
NT-B1-M02-P020 GCD of Two Shifted Expressions
#20
★★★☆☆ Level 3 of 5
Find the exact value of \(\gcd(n^2+n+1,n^2+2n+3)\) depending on the integer \(n\).
Subtract the first expression from the second.
Let \(d=\gcd(n^2+n+1,n^2+2n+3)\). Then \(d\mid(n^2+2n+3)-(n^2+n+1)=n+2\). Modulo \(d\), we have \(n\equiv-2\), so from \(d\mid n^2+n+1\), we get \(d\mid4-2+1=3\). Hence \(d\) is \(1\) or \(3\). Both expressions are divisible by \(3\) exactly when \(n\equiv1\pmod3\). Therefore the GCD is \(3\) for \(n\equiv1\pmod3\), and \(1\) otherwise.
A linear combination immediately lowers the degree and gives the exact answer.