求解不定方程

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

复制代码

输出：