Problem
NT-B1-M11-P014 GCD with a Parameter
#14
★★★☆☆ Level 3 of 5
Find \(\gcd(n^2+1,n+2)\) for positive integer \(n\).
Replace \(n\) by \(-2\) modulo \(n+2\).
Modulo \(n+2\), we have \(n\equiv-2\), so \(n^2+1\equiv4+1=5\). Thus the GCD is \(\gcd(n+2,5)\). It is \(5\) if \(n\equiv3\pmod5\), and \(1\) otherwise.
Typical olympiad handling of expression GCDs.