Proof The quadratic congruence x^2+1≡0 (mod p), where p is an odd prime, has a solution if and only if p≡1 (mod 4).

 

\[\begin{array}{l} The\;quadratic\;congruence\;\;{x^2} + 1 \equiv 0\;(modp),where\;p\;is\;an\;odd\;prime,\\\\ has\;a\;solution\;if\;and\;only\;if\;p \equiv 1\;(mod4).\\\\ Proof.\\\\ Let\;a\;be\;any\;solution\;of\;\;{x^2} + 1 \equiv 0\;(modp),so\;that\;{a^2} \equiv - 1\;(modp).\\\\ Because\;p\;does\;not\;divide\;a,the\;outcome\;of\;applying\;Fermat's\;little\;theorem\;is\\\\ 1 \equiv {a^{p - 1}} \equiv {\left( {{a^2}} \right)^{\left( {p - 1} \right)/2}} \equiv {\left( { - 1} \right)^{\left( {p - 1} \right)/2}}\;\;\;\;\left( {mod\;p} \right)\\\\ Therefore,\;must{\rm{ }}\;be{\rm{ }}\;of{\rm{ }}\;the\;{\rm{ }}form\;\;that\;{\rm{ }}is\;.\\\\ Now{\rm{ }}\;for{\rm{ }}\;the\;{\rm{ }}opposite\;{\rm{ }}direction.{\rm{ }}\;In\;{\rm{ }}the\;{\rm{ }}product\\\\ \left( {p - 1} \right)! = 1 \times 2 \times \ldots \frac{{p - 1}}{2} \times \frac{{p + 1}}{2} \times \ldots \left( {p - 2} \right)\left( {p - 1} \right)\\\\ We{\rm{ }}\;have{\rm{ }}\;the{\rm{ }}\;congruences\\\\ p - 1 \equiv - 1\;\;\;\;\left( {mod\;p} \right)\\\\ p - 2 \equiv - 2\;\;\;\;\left( {mod\;p} \right)\\\\ \frac{{p + 1}}{2} \equiv - \frac{{p - 1}}{2}\;\;\;\;\left( {mod\;p} \right)\\\\ Rearranging\;{\rm{ }}the\;{\rm{ }}factors\;{\rm{ }}produces\\\\ \left( {p - 1} \right)! \equiv 1 \times \left( { - 1} \right) \times 2\left( { - 2} \right) \times \ldots \times \frac{{p - 1}}{2} \times \left( { - \frac{{p - 1}}{2}} \right)\;\left( {mod\;p} \right)\\\\ \equiv {\left( { - 1} \right)^{\frac{{p - 1}}{2}}}{\left( {1 \times 2 \times \ldots \times \frac{{p - 1}}{2}} \right)^2}\;\left( {mod\;p} \right)\\\\ Because\;{\rm{ }}there\;{\rm{ }}are\;\;\left( {p - 1} \right)/2minus{\rm{ }}\;signs\;{\rm{ }}involved.{\rm{ }}\;It\;{\rm{ }}is\;{\rm{ }}at\;{\rm{ }}this\;{\rm{ }}point{\rm{ }}\\\\ that\;{\rm{ }}Wilson's\;{\rm{ }}theorem\;{\rm{ }}can{\rm{ }}\;be\;{\rm{ }}brought\;{\rm{ }}to\;{\rm{ }}bear;\;{\rm{ }}for\left( {p - 1} \right)! \equiv - 1\;\left( {mod\;p} \right),{\rm{ }}\;whence\\\\ - 1 \equiv \left( {{\rm{p}} - 1} \right)! \equiv {\left( { - 1} \right)^{\frac{{p - 1}}{2}}}{\left[ {\left( {\frac{{p - 1}}{2}} \right)!} \right]^2}\;\left( {mod\;p} \right)\\\\ If\;we\;assume\;that\;p\;is\;of\;the\;form\;\;4k + 1,then\;{( - 1)^{(p - 1)/2)}} = 1,leaving\;us\;with\;\\\\ the\;congruence\\\\ - 1 \equiv {\left[ {\left( {\frac{{p - 1}}{2}} \right)!} \right]^2}\;\left( {mod\;p} \right)\\\\ The{\rm{ }}\;conclusion{\rm{ }}\;is\;{\rm{ }}that\;{\rm{ }}the\;{\rm{ }}integer\;satisfies\;{\rm{ }}the\;{\rm{ }}quadratic{\rm{ }}\;congruence\\\\ {x^2} + 1 = 0\;(modp).\\\\ \;\;\;Let\;{\rm{ }}us\;{\rm{ }}take\;{\rm{ }}a{\rm{ }}\;look\;{\rm{ }}at\;{\rm{ }}an{\rm{ }}\;actual\;{\rm{ }}example,{\rm{ }}\;say,{\rm{ }}\\\\ the\;{\rm{ }}case\;\;which\;{\rm{ }}is\;{\rm{ }}a\;{\rm{ }}prime\;{\rm{ }}of\;{\rm{ }}the\;{\rm{ }}form\;4k + 1.{\rm{ }}\;\;Here,{\rm{ }}\;we\;{\rm{ }}have\frac{{{\rm{p}} - 1}}{2} = 6\;,\\\\ \;{\rm{ }}and{\rm{ }}it{\rm{ }}is{\rm{ }}easy\;{\rm{ }}to{\rm{ }}\;see{\rm{ }}\;that\\\\ 6! = 720 \equiv 5\;\;\;\;\left( {mod\;13} \right)\\\\ And\\\\ {5^2} + 1 = 26 \equiv 0\;\;\;\;\left( {mod\;13} \right)\\\\ Thus,the\;assertion\;that{[((p - 1)/2)!]^2} + 1 = 0\;(modp)\;is\;correct\;for\;p = 13.\\\\ See{\rm{ }}\left( {Burton,{\rm{ }}2011,{\rm{ }}p.95} \right) \end{array}\]