判断同余式x∧2≡365（mod1847）是否有解

判断同余式x∧2≡365（mod1847）是否有解

题：判断同余式x^2≡365 (mod1847) 是否有解
注：本题解答末尾附有legendre符号计算要点。这里首先摘抄几条。注意(7/p)可以用二次互反律方便计算，不过这里也附录了相关公式。
(-1/p)=(-1)^((p-1)/2)=(-1)^[p/2]=(-1)^[(pmod4)/2]=(p amr 4)，
这里定义 amr 表示绝对最小剩余，即abs min remainder。或在r后添加下标|min|来表示。
如 2 ==-1 mod 3, 写成 2 amr 3=-1； 3 ==-1 mod 4, 写成 3 amr 4=-1。
(-2/p)=(-1)^.[(pmod8)/4])
(2/p)=(-1)^([p/2]+[p/4]) 注：此式利于速算。当p较小。
=(-1)^([(pmod8)/2]+[(pmod8)/4]) 注，此式利于速算,当p较小。
=(p amr 4)*(-1)^.[(pmod8)/4]) 注：此时也较利于计算，不过思路略要转弯。

二次互反律：p,q为奇素数，则有
(p/q)=(q/p)*(-1)^((p-1)/2*(q-1)/2)=(q/p)*(-1)^( [p/2]*[q/2] )
=q/p)*(-1)^TRUE(p&q amr 4=-1),　即当且仅当p与q均为-1 mod 4时，(p/q)=-(q/p).否则(p/q)=(q/p).

(3/p)=(p amr 3)(p amr 4)
(5/p)=(p/5)=(1 if p==1,4 mod 5; -1 if p==2,3 mod 5)
内注：其实(p/5)很简单的，因为p的既约剩余仅有1,2,3,4四个，并且必定有且只有一半数量为平方剩余，即有两个。很显然就是1,4.

解：1847是素数。
下面来计算legendre 符号
(365;1847)
=(5;1847)*(73; 1847)
易见
故(5;1847)=(1847;5)=(2;5)=-1

而(73;1847)=(1847;73)=(22;73)=(2;73)*(11;73)
(2;73)=(73 amr 4) * (-1)^.[(73mod8)/4]) =1*1=1
或(2;73)=(-1)^([p/2]+[p/4])=(-1)^(36+18)=1
(73;11)=(7;11)=-(11;7)=-(4;7)=-1
故(73;1847)=(2;73)*(11;73)=-1
(365;1847)=(5;1847)*(73; 1847)=1
故同余式x^2≡365 (mod1847) 有解

外一则：
可参考我的博文 二次剩余及其速算法，摘要如下：
legendre符号计算要点：
计算要点

(aa/p)=1, 当a,p互质时;

同余性：(a/p)=((a modp) /p)；

因子分解：(ab/p)=(a/p)(b/p)及其向多因子分解的推广。

二次互反律简化形式：
(p/q)=(q/p)*(-1)^TRUE(p&q amr 4=-1),　即当且仅当p与q均为-1 mod 4时，(p/q)=-(q/p).否则(p/q)=(q/p).
易见当其中出现p amr 4=1，即p==1 mod 4时，即有(p/q)=(q/p)；当出现 p amr 4=-1时，即有(p/q)=(q/p)*(q amr 4)

二次互反律的两个充分且必要的补充(由此原则上可以方便的计算所有的(p/q)，其中p/q为奇素数)
　　补充计算式一：
(-1/p)=(-1)^((p-1)/2)=(-1)^[p/2]=(-1)^[(pmod4)/2]，这个我们在上面对二次互反律进行简化时曾见到过。
现在我们看到，(p/q)=(q/p)*(-1/p)^ [q/2] =(q/p)*(-1/q)^ [p/2]
　　补充计算式二：
(2/p)=(-1)^((pp-1)/8)
(2/p)=(-1)^([p/2]+[p/4])
=(-1)^([(pmod8)/2]+[(pmod8)/4]) 注，此式利于速算。
=(-1)^([(pmod4)/2]+[(pmod8)/4])
=(p amr 4)*(-1)^.[(pmod8)/4]) 注，此式利于速算。
由上二者还可以得到 (-2/p)=(-1)^[p/4]==(-1)^[(pmod8)/4]

CCC其它特殊值的计算：(以下p指奇素数)

(3/p)=(p amr 3)(p amr 4) 注：此式利于速算。

证明一：
(3/p)=(p/3)*(-1)^ [p/2]=((p mod 3)/3)*(-1)^ [(p mod4)/2]=((p mod 3)/3) * (p amr 4)
因为(1/3)=1, (-1/3)=-1, 故((p mod 3)/3)=(p amr 3)
得证。
证明二，列举检验法。
将质数p按模12=3*4可分为四类(注意12以下与12互质的只有四个)，p=1,5,7,11 mod 12
例如质数p=13;5;7;11，分别代入(p/3)=((p mod 3)/3)*(-1)^ [(p mod4)/2]得到
(3/p)=1*(-1)^0, -1*(-1)^0, 1*(-1)^1, (-1)*(-1)^1=1*1, -1*1, 1*(-1), (-1)*(-1)
即p=1,5,7,11mod12时，(3/p)分别取值1,-1,-1,1
由前述amr的定义，易见：
(3/p)=(p amr 3)(p amr 4)
　　　　另一种算法(计算不太方便，可能方便表述与研究)：
(3/p)=(-1)^⌈(p+1)/6⌉=(-1)^upint((p+1)/6), 这里upint(x)即向上取整，即不小于x的最小整数。在某些程序语言中（包括数学软件）用ceiling(x)函数。excel软件中是ceiling(x,1)，手写常写成⌈x⌉.

(5/p)=(p/5)=(1 if p==1,4 mod 5; -1 if p==2,3 mod 5)
注：其实(p/5)很简单的，因为p的既约剩余仅有1,2,3,4四个，并且必定有且只有一半数量为平方剩余，即有两个。很显然就是1,4.
证明：
由二次互反律，(5/p)=(p/5)*(-1)^([p/2]*[5/2])=(p/5).
在明白上面的过程后我们知道(p/5)计算很简单。
　　　　另一种算法(计算不太方便，可能方便表述与研究)：
(-1)^⌊(p-2)/5⌋=(-1)^ int((p-2)/5)， 这里int(x)是向下取整函数，即不大于x的最大整数。在某些程序语言中（包括数学软件）用floor(x)函数。excel软件中是floor(x,1)，手写常写成⌊x⌋.

(7/p)=( 1 if p==±1,±9,±25=±(1, 3^2, 5^2) mod 28 ; -1 if p==±(1-14), ±(9-14), ±(25-14)=±(13, 5, 11) mod 28)
　　　　上式很好记。从小到大写即是 (7/p)=( 1 if p==1,3,9,19,25,27 mod 28 ; -1 if p==5, 11, 13, 15, 17, 23 mod 28)
证：
引1：(7/p)=(p/7)*(-1)^([p/2]*[7/2])=(p/7)*(-1)^[p/2]=(p/7)*(p amr 4)
引2：当且仅当p=1,2,4mod7时，(p/7)=1,即7的二次剩余有三个，即1, 4, 9==2，也即1,2,4. 其二次非剩余即3,5,6==-4,-2,-1；也可以由(-1/7)=-1, 直接将-1乘1,2,4得到7的二次非剩余为-1,-2,-4.
当(p/7)=1且p==1 mod 4，或(p/7)=-1且p=-1 mod 4时，得(7/p)=1，分说如下：
由p==1,2,4 mod 7及p==1 mod 4得p==1,9,25 mod 28;
由p==-1,-2,-4 mod 7及p==-1 mod 4得p==-1,-9,-25 mod 28，即p=27,19,3 mod 28.
当(p/7)=-1且p==1 mod 4，或(p/7)=-1且p=1 mod 4时，得(7/p)=-1，下略。