Problem
NT-B2-M01-P004 When the GCD Is Greater Than One
#4
★★☆☆☆ Level 2 of 5
Find all positive integers \(n\) such that \( \gcd(n^2+1,n+3)>1 \).
Reduce the gcd to \( \gcd(n+3,10) \).
Modulo \(n+3\), \(n\equiv-3\), hence \(n^2+1\equiv10\). Thus \( \gcd(n^2+1,n+3)=\gcd(10,n+3) \). This gcd is greater than \(1\) exactly when \(n+3\) is divisible by \(2\) or by \(5\). Therefore \(n\) is odd or \(n\equiv2\pmod5\).
This includes a typical final step: turning a gcd condition into residue classes.