Задача
NT-B2-M01-P007 Маленький общий делитель
#7
★★★☆☆ Уровень 3 из 5
Найдите все натуральные \(n\), для которых \( \gcd(n^2+n+1,2n+1)>1 \).
Умножьте \(n^2+n+1\) на \(4\).
Пусть \(d\) - общий делитель. Так как \(d\mid2n+1\), имеем \((2n+1)^2\equiv0\pmod d\). Но \(4(n^2+n+1)=(2n+1)^2+3\), значит \(d\mid3\). Поэтому НОД больше \(1\) только если \(3\mid2n+1\), то есть \(n\equiv1\pmod3\). При этом условии \(3\) действительно делит оба числа. Ответ: \(n\equiv1\pmod3\).
Хорошая задача на подбор комбинации, где появляется полный квадрат.