Задача
NT-B1-M02-P020 НОД двух сдвинутых выражений
#20
★★★☆☆ Уровень 3 из 5
Найдите точное значение \(\gcd(n^2+n+1,n^2+2n+3)\) в зависимости от целого \(n\).
Вычтите первое выражение из второго.
Пусть \(d=\gcd(n^2+n+1,n^2+2n+3)\). Тогда \(d\mid(n^2+2n+3)-(n^2+n+1)=n+2\). По модулю \(d\) имеем \(n\equiv-2\), поэтому из \(d\mid n^2+n+1\) получаем \(d\mid4-2+1=3\). Значит, \(d\) равен \(1\) или \(3\). Оба выражения делятся на \(3\) тогда и только тогда, когда \(n\equiv1\pmod3\). Следовательно, НОД равен \(3\) при \(n\equiv1\pmod3\), и \(1\) иначе.
Линейная комбинация сразу снижает степень и дает точный ответ.