关于丢番图方程x^2-dy^2=-1
我們知道丟番圖方程,其中d是非完全平方正整數(shù)，那么此方程就是Pell方程，到目前為止對于它的最優(yōu)求解方
?
法就是經(jīng)典的連分數(shù)問題。可以看這里：http://blog.csdn.net/acdreamers/article/details/8529686
?
那么對于上述的Pell方程來說，它一定是有解的，而現(xiàn)在我們研究另一個丟番圖方程：
?
，其中同樣要求d是非完全平方正整數(shù)，對于這個方程，它就不一定有解了。
?
那么我們來研究如下一個結(jié)論：
?
設(shè)，當并且為素數(shù)，那么一定有正整數(shù)解。
?
?
下面我們就來簡略證明一下這個結(jié)論
?
證明：我們知道對于方程一定有正整數(shù)解，當然本文討論中的所有都是非完全平方正整數(shù)。
?
假設(shè)是方程的最小正整數(shù)解，顯然一奇一偶，假設(shè)，，
?
那么就得到矛盾，所以只能是，
?
那么這樣可以知道都是整數(shù)，并且都相差1，所以必有一奇一偶，所以
?
?
進一步有：，那么得到：
?
(還有一種情況不符合舍去)。那么就是方程的最小正整數(shù)解。我們可以發(fā)現(xiàn)這樣的做法就是根據(jù)
?
方程的最小正整數(shù)解來求方程的最小正整數(shù)解，最后開個方就行了。
?
?
其實這種方法看起來很麻煩，我們作如下簡化：
?
因為求方程的解是用連分數(shù)，那么我們也可以直接對方程用連分數(shù)求解。這里的還是滿足
?
?
那么我們有如下結(jié)論：
?
如果，并且，那么方程的解可以這樣求：
先把寫成連分數(shù)的形式，那么我們只需要保存它的第一個循環(huán)節(jié)的部分，然后把它回帶成的形式，那么這里的p和q就
?
是方程的最小正整數(shù)解。
??
其實直接套這里的模版即可：http://blog.csdn.net/acdreamers/article/details/9531793
?
?
?
那么，接下我們來看一個同余方程：，其中要求為奇素數(shù)，且，求x的最小正整數(shù)解。
?
結(jié)論：先求丟番圖方程：的最小正整數(shù)解的值。然后得到，那么此時方程小于p的正整數(shù)解就分
?
別是和，這兩個數(shù)中的較小的那個就是上述方程的最小正整數(shù)解。
?
?
?
為什么是這樣呢？我只作一點簡單的描述，這個首先得從二次剩余說起。
?
二次剩余當中最重要的一些定理如下：
?
設(shè)m是正整數(shù)，若同余式，且，有解，那么a叫做模m的二次剩余，否則a叫做模m的二次非剩余。
歐拉判別條件給出了模為奇素數(shù)p有解判斷條件：
?
(1)a是模奇素數(shù)p的二次剩余的充要條件是：
?
(2)a是模奇素數(shù)p的二次非剩余的充要條件是：
?
并且有：當a是模奇素數(shù)p的平方剩余時，同余式恰有兩個小于p的正整數(shù)解。并且這兩個解之和為p。
?
所以對于同余方程來說，注意，很明顯-1一定是p的二次剩余，所以它有兩個解。?
?
然后上面解法的正確性我給出了打表證明：http://paste.ubuntu.com/5998778/
可以從結(jié)果中看出，第一個數(shù)x用連分數(shù)和暴力求解都是一樣的，解在范圍內(nèi)恰好有兩個，而第二個數(shù)沒有用，因
為這兩個解都是通過x得來的，上面的講解都說了。
?
?
上面介紹的是連分數(shù)求方程的最小正整數(shù)解，其中且p是素數(shù)。
細心的讀者會發(fā)現(xiàn)，當p很大時還是行不通，因為一是循環(huán)節(jié)太大，而是可能在求循環(huán)節(jié)時有數(shù)字超過整數(shù)范圍的。
?
那么下面我將介紹我認為是解決這個問題的最好方法。把下面的n換為-1就是上面的方程了。
?
http://algo.ftiasch.com/tag/number-theory/
?
注意這里是在二次域上做計算的，w不是實數(shù)。
?
?
總結(jié)
以上是生活随笔為你收集整理的关于丢番图方程x^2-dy^2=-1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： POJ3608(旋转卡壳--求两凸包的最
- 下一篇： 表为平方和初级版