Problem
NT-B1-M12-P014 Set 3. Prime Divisors of \(a^2+1\)
#14
★★★☆☆ Level 3 of 5
Let an odd prime \(p\) divide \(a^2+1\). Prove that \(p\equiv1\pmod4\).
From \(a^2\equiv-1\pmod p\), it follows that \(a^4\equiv1\pmod p\).
Since \(p\mid a^2+1\), we have \(a^2\equiv-1\pmod p\). Then \(a^4\equiv1\pmod p\), but \(a^2 ot\equiv1\pmod p\). Thus the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), hence \(4\mid p-1\), so \(p\equiv1\pmod4\).
Above-average for Book 1, but an important order idea.