Problem
NT-B2-M01-P007 A Small Common Divisor
#7
★★★☆☆ Level 3 of 5
Find all positive integers \(n\) such that \( \gcd(n^2+n+1,2n+1)>1 \).
Multiply \(n^2+n+1\) by \(4\).
Let \(d\) be a common divisor. Since \(d\mid2n+1\), we have \((2n+1)^2\equiv0\pmod d\). But \(4(n^2+n+1)=(2n+1)^2+3\), so \(d\mid3\). Thus the gcd is greater than \(1\) only when \(3\mid2n+1\), that is, \(n\equiv1\pmod3\). In this case \(3\) really divides both numbers. Answer: \(n\equiv1\pmod3\).
A good problem on finding a combination that produces a square.