NT-B2-M01-P014 A Cubic Restriction

Eliminate \(p^3\) using \(p(p^2+1)\).

Let \(d\) be a common divisor. Then \(d\mid p^3+1-p(p^2+1)=1-p\). Thus \(d\mid p-1\). Modulo \(p-1\), \(p\equiv1\), so \(p^2+1\equiv2\). Hence a common divisor can only divide \(2\). If \(p=2\), then \(\gcd(5,9)=1\). If \(p\) is odd, both \(p^2+1\) and \(p^3+1\) are even, so the gcd is \(2\). Answer: all odd primes \(p\).

Here it matters that \(p\) is prime: the final check uses parity.