Задача
NT-B1-M02-P015 НОД делит 3
#15
★★★☆☆ Уровень 3 из 5
Докажите, что \(\gcd(n^2+n+1,n-1)\mid3\). Когда этот НОД равен \(3\)?
По модулю \(n-1\) замените \(n\) на \(1\).
По модулю \(n-1\) имеем \(n\equiv1\). Тогда \(n^2+n+1\equiv1+1+1=3\). Следовательно, НОД равен \(\gcd(n-1,3)\), значит, он делит \(3\). Он равен \(3\) тогда и только тогда, когда \(3\mid n-1\), то есть \(n\equiv1\pmod3\).
Прямое попадание в требование структуры: \(\gcd(f(n),g(n))\).