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).

Published On :2021-08-24 16:11:00

 

[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 2left( { - 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{ }}forleft( {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{ }}havefrac{{{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}]