数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 239|回复: 8

求解同余方程 x^2-3x+5≡0 (mod15)

[复制链接]
发表于 2021-8-1 13:04 | 显示全部楼层 |阅读模式
请问对于这些同余方程一般的解法要怎样解?



我能不能这样解?
x^2-3x+5=x^2-3x-10=(x-5)(x+2)=0  (mod15)
所以 x=5 (mod15) 或 x=-2=13 (mod15)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2021-8-1 17:15 | 显示全部楼层
本帖最后由 zytsang 于 2021-8-1 22:00 编辑

x=8和x=10也是解


对于 \[ax^2+bx+c≡0 \pmod{n}\]
当 \(\gcd(4a,n)=1\) 的时候,一般的解法为:

第一步:先求解 \( y \) 使其满足
\[y^2\equiv b^2-4ac\pmod{n}\]
第二步:再求解 \( x \) 使其满足
\[2ax\equiv y-b\pmod{n}\]


本题中 \(a=1,b=-3,c=5,n=15\)
第一步:
\[y^2\equiv -11\equiv4\pmod{15}\implies y\equiv \{2,7,8,13\}\pmod{15}\]
第二步:
\[2x\equiv 5\pmod{15}\implies x\equiv10\pmod{15} \]
\[2x\equiv 10\pmod{15}\implies x\equiv5\pmod{15} \]
\[2x\equiv 11\pmod{15}\implies x\equiv13\pmod{15} \]
\[2x\equiv 16\pmod{15}\implies x\equiv8\pmod{15} \]
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-1 23:04 | 显示全部楼层
zytsang 发表于 2021-8-1 17:15
x=8和x=10也是解


对于 \[ax^2+bx+c≡0 \pmod{n}\]


想问一问,如果4a与n不互质时,要怎样解?
回复 支持 反对

使用道具 举报

发表于 2021-8-1 23:19 | 显示全部楼层
本帖最后由 zytsang 于 2021-8-1 23:24 编辑
popo987654 发表于 2021-8-1 23:04
想问一问,如果4a与n不互质时,要怎样解?


在一般情况下,令 \(4a=a_1 a_2\) 并且 \(\gcd(a_2,n)=1\)

原题变为求解
\[y^2\equiv b^2-4ac \pmod{a_1 n}\]
\[2ax\equiv y-b \pmod{a_1 n}\]
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-1 23:25 | 显示全部楼层
zytsang 发表于 2021-8-1 23:19
如果 \(\gcd(4a,n)\ne1\),那么令 \(4a=a_1 a_2\) 并且 \(\gcd(a_2,n)=1\)

原题变为求解

老师好,那如果是这条同余方程 x^2+4x-17=0 (mod20) 可以怎样拆?
回复 支持 反对

使用道具 举报

发表于 2021-8-1 23:32 | 显示全部楼层
本帖最后由 zytsang 于 2021-8-2 00:07 编辑
popo987654 发表于 2021-8-1 23:25
老师好,那如果是这条同余方程 x^2+4x-17=0 (mod20) 可以怎样拆?


有 \(\gcd(4a,n)\ne1\),可令 \(4a=4=4\times1=a_1\times a_2\)

原方程变为求解
\[y^2\equiv 84 \equiv 4 \pmod{80}\implies y\equiv\{2,18,22,38,42,58,62,78\}\pmod{80}\]

第二步可稍作简化:
\[2x\equiv y-4 \pmod{80}\implies x\equiv \frac{y-4}{2} \pmod{40}\]

取所有y值代入
\[y=2\implies x\equiv -1 \equiv 39 \pmod{40}\implies x\equiv19\pmod{20}\]
\[y=18\implies x \equiv 7 \pmod{40}\implies x\equiv7\pmod{20}\]
\[y=22\implies x \equiv 9 \pmod{40}\implies x\equiv9\pmod{20}\]
\[y=38\implies x \equiv 17 \pmod{40}\implies x\equiv17\pmod{20}\]
\[y=42\implies x \equiv 19 \pmod{40}\implies x\equiv19\pmod{20}\]
\[y=58\implies x \equiv 27 \pmod{40}\implies x\equiv7\pmod{20}\]
\[y=62\implies x \equiv 29 \pmod{40}\implies x\equiv9\pmod{20}\]
\[y=78\implies x \equiv 37 \pmod{40}\implies x\equiv17\pmod{20}\]

可得原方程的所有解:
\[x\equiv \{7,9,17,19\}\pmod{20}\]



点评

谢谢,我再多加练习  发表于 2021-8-1 23:58
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-8-1 23:38 | 显示全部楼层
zytsang 发表于 2021-8-1 23:32
有 \(\gcd(4a,n)>1\),可命 \(4a=4=4\times1=a_1\times a_2\)

如果可以的话,能不能麻烦老师您帮忙用这题 x^2+4x-17=0 (mod20) 作范例 ,我有点乱
回复 支持 反对

使用道具 举报

发表于 2021-8-2 09:31 | 显示全部楼层
楼上 zytsang 的解答很好!已收藏。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2021-9-19 04:25 , Processed in 0.078125 second(s), 20 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表