Задача
NT-B2-M01-P002 Всегда взаимно просты
#2
★★☆☆☆ Уровень 2 из 5
Докажите, что для любого натурального \(n\) числа \(n^2+n+1\) и \(n+1\) взаимно просты.
Посмотрите на первое число по модулю \(n+1\).
Если \(d\mid n+1\), то \(n\equiv-1\pmod d\). Тогда \(n^2+n+1\equiv1-1+1=1\pmod d\). Общий делитель должен делить \(1\), значит он равен \(1\).
Полезно как быстрый тест на работу с остатком многочлена.