求解不定方程

lxx6828

求不定方程 $2y^2 =159x +3$ 的全部整数解

mathe

首先容易判断出y是3的倍数，另y=3s代入 得到x除6余5，另x=6t-1代入，得到 $s^2=53t-7$ 这是一个平方剩余问题，需要判断-7是否53的平方剩余，是就有解，不是无解。 平方剩余好像gxqcn的HugeCalc里面就有函数，具体计算公式我有点记不住了。 不过我们此外还可以通过$phi(53)=52$来判断。先计算$(-7)^26 (mod 53)$是否为1，如果是就是平方剩余，不然不是。 是平方剩余情况，先计算-7关于模53的平方根就好办了。

lxx6828

原帖由 mathe 于 2008-3-22 12:17 发表 首先容易判断出y是3的倍数，另y=3s代入 得到x除6余5，另x=6t-1代入，得到 $s^2=53t-7$ 这是一个平方剩余问题，需要判断-7是否53的平方剩余，是就有解，不是无解。 平方剩余好像gxqcn的HugeCalc里面就有函数，具体 ...

谢谢。但我电脑版面上有的字符不能显示，有可能的话能否给发一个Email:cynlxx6828@163.com

medie2005

x = 159*u + 9 y = 318*u^2 + 36*u +1 and also: x = 159*u + 150 y = 318*u^2 + 600*u + 283

hujunhua

首先容易判断出y是3的倍数，另y=3s代入 得到x除6余5，另x=6t-1代入，得到 $s^2=53t-7$ 这是一个平方剩余问题，需要判断-7是否53的平方剩余，是就有解，不是无解。 平方剩余好像gxqcn的HugeCalc里面就有函数，具体 ... mathe 发表于 2008-3-22 12:17

用二次互反律和Legendre符号啊。比较搞人的是，不作变量代换还容易观察些。 两边mod159 $y^2\equiv 3/2\equiv (159+3)/2\equiv 81\equiv 9^2(mod159)$ $y\equiv \+- 9(mod159)$ 令$y=159u\+- 9$代入后得$318u^2 \+- 36u+1=x$

282842712474

首先容易判断出y是3的倍数，另y=3s代入 得到x除6余5，另x=6t-1代入，得到 $s^2=53t-7$ 这是一个平方剩余问题，需要判断-7是否53的平方剩余，是就有解，不是无解。 平方剩余好像gxqcn的HugeCalc里面就有函数，具体 ... mathe 发表于 2008-3-22 12:17

根据你的计算，那么s=53n+24或者s=53n+29 用VB枚举的：

1. Private Sub Form_Click()
2. Dim s, k As Integer
3. s = 1
4. While s <= 53
5. k = (s * s + 7) Mod 53
6. If k = 0 Then
7. Print "s=" + Str(s) + ",k=" + Str(k)
8. End If
9. s = s + 1
10. Wend
11. End Sub

复制代码

输出：