Problem
NT-B1-M02-P014 GCD of \(n^2+1\) and \(n+3\)
#14
★★★☆☆ Level 3 of 5
Find all integers \(n\) for which \(\gcd(n^2+1,n+3)>1\).
Show that this GCD equals \(\gcd(10,n+3)\).
Modulo \(n+3\), we have \(n\equiv -3\), so \(n^2+1\equiv10\). Hence \(\gcd(n^2+1,n+3)=\gcd(10,n+3)\). This GCD is greater than \(1\) if \(n+3\) is divisible by \(2\) or by \(5\). Thus \(n\) is odd or \(n\equiv2\pmod5\).
It is best to leave the answer as a union of two modular conditions.