x²=-1(mod109)是否有界,如果有解写出详细的求解过程
时间: 2023-07-16 09:12:24 浏览: 79
首先,我们可以使用欧拉判别准则来判断该同余方程是否有解:
由于 $109$ 是一个质数,我们有:
$$\left(\frac{-1}{109}\right)\equiv (-1)^{\frac{109-1}{2}}\equiv (-1)^{54}\equiv 1\pmod{109}$$
因此,方程 $x^2\equiv -1\pmod{109}$ 有解。
接下来,我们可以使用扩展欧几里得算法来求解该同余方程的解。具体来说,我们需要寻找一个整数 $y$,使得 $y^2\equiv -1\pmod{109}$。然后,解可以表示为 $x\equiv ay\pmod{109}$ 的形式,其中 $a$ 是模数 $109$ 的逆元,即 $a\equiv 1^{-1}\pmod{109}$。
我们可以通过对 $109$ 进行质因数分解,然后使用勒让德符号来找到 $y$。具体来说,我们可以将 $109-1=2^k\cdot m$,其中 $m$ 是一个奇数。由于 $109$ 是一个质数,我们有:$\left(\frac{-1}{109}\right)=(-1)^m$。因此,我们可以使用欧拉判别准则得到 $m\equiv 1\pmod{4}$。
现在,我们可以将 $m$ 表示为 $m=4t+1$ 的形式。因此,我们可以将 $109-1=2^k\cdot (4t+1)$,其中 $k\geq 3$。现在,我们可以选择一个随机整数 $b$,然后计算 $b^{t}\pmod{109}$。如果 $b^{t}\equiv \pm 1\pmod{109}$,则我们需要重新选择 $b$,直到找到一个满足 $b^{t}\not\equiv \pm 1\pmod{109}$ 的 $b$。然后,我们可以计算 $y\equiv b^{2^{k-2}}\pmod{109}$。现在,我们可以验证 $y^2\equiv -1\pmod{109}$,如果成立,则我们可以计算 $a\equiv 2^{k-2}t^{-1}\pmod{109}$,然后解得 $x\equiv ay\pmod{109}$。
综上所述,我们可以通过扩展欧几里得算法来求解方程 $x^2\equiv -1\pmod{109}$ 的解,具体过程如下:
1.使用欧拉判别准则判断方程是否有解。
2.将模数进行质因数分解,然后使用勒让德符号来找到 $y$。
3.选择一个随机整数 $b$,然后计算 $b^{t}\pmod{109}$,直到找到一个满足 $b^{t}\not\equiv \pm 1\pmod{109}$ 的 $b$。
4.计算 $y\equiv b^{2^{k-2}}\pmod{109}$。
5.验证 $y^2\equiv -1\pmod{109}$,如果成立,则计算 $a\equiv 2^{k-2}t^{-1}\pmod{109}$。
6.解得 $x\equiv ay\pmod{109}$。