Problem
NT-B1-M02-P015 The GCD Divides 3
#15
★★★☆☆ Level 3 of 5
Prove that \(\gcd(n^2+n+1,n-1)\mid3\). When is this GCD equal to \(3\)?
Modulo \(n-1\), replace \(n\) by \(1\).
Modulo \(n-1\), we have \(n\equiv1\). Then \(n^2+n+1\equiv1+1+1=3\). Therefore the GCD is \(\gcd(n-1,3)\), so it divides \(3\). It equals \(3\) exactly when \(3\mid n-1\), i.e. \(n\equiv1\pmod3\).
Directly matches the structure requirement: \(\gcd(f(n),g(n))\).