Problem
NT-B2-M01-P002 Always Coprime
#2
★★☆☆☆ Level 2 of 5
Prove that for every positive integer \(n\), the numbers \(n^2+n+1\) and \(n+1\) are coprime.
Look at the first number modulo \(n+1\).
If \(d\mid n+1\), then \(n\equiv-1\pmod d\). Therefore \(n^2+n+1\equiv1-1+1=1\pmod d\). A common divisor must divide \(1\), so it is \(1\).
Useful as a quick test of polynomial remainders.