Problem
NT-B1-M07-P022 A Divisor of \(a^2+1\)
#22
★★★★☆ Level 4 of 5
Let \(p\) be an odd prime, \(p\mid a^2+1\), and \(p\nmid a\). Prove that \(p\equiv1\pmod4\).
From \(a^2\equiv-1\pmod p\), find the order of \(a\) modulo \(p\).
We have \(a^2\equiv-1\pmod p\). Then \(a^4\equiv1\pmod p\), but \(a^2\not\equiv1\pmod p\), since that would give \(-1\equiv1\pmod p\), hence \(p=2\). Thus the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), so \(4\mid p-1\), i.e. \(p\equiv1\pmod4\).
First serious use of order as a restriction on a prime divisor.