Pell方程式

project Eulerで何度も解いているわりによくわかっていないことに気付いたので

問:
dを正整数、cを整数とする。x^2-dy^2=c の整数解を全て求めよ

続きを読む »

136

project euler136
天才解法の細かいところを詰めるのが難しかったので。

式変形して、(x,y,z)はd≦xなる正整数(x,d)と1対1対応し、n=x(4d-x)となる。
ここで、n=abかつa+b=0 mod 4かつa≦bならば、x=bと置くことで、d≦xかつn=x(4d-x)となる(x,d)が必ず作れる。
(a,b)が「n=abかつa+b=0 mod 4かつa≦b」を満たすことを(条件※)を満たすということにする。
またx=aと置くことで異なる(x,d)が出来るための必要十分条件は「a≠bかつb<3a」
したがってnが求めるものであるためには、「『条件※を満たす(a,b)は一意に存在する』(条件A)、かつ、『その(a,b)はa=bまたは3a≦bを満たす』(条件B)」ことが必要十分。mod4で場合分け
・n=1 mod 4のとき
(a,b)=(1,1),(3,3) mod4にしかならない
・n=2 mod 4のとき
(a,b)=(偶,奇)にしかならない
・n=3 mod 4のとき
(a,b)=(1,n)が自明に条件※を満たす。
もしnが4k+1型の素数pを持てば(p,n/p)が、もし4k+3型の(相異なるとは限らない)素数p,qを持てば(pq,n/pq)が(1,n)とは異なる条件※を満たす解となる。よって、条件Aを満たすにはnは奇素数であることが必要。このとき3=3a≦b=nなので条件Bを満たす
・n=4 mod 8のとき
(a,b)=(2,n/2)が自明に条件※を満たす。
もしn/4が(相異なるとは限らない)素数p,qを持てば(2p,n/2p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=4または4pが必要(pは奇素数)。
n=4のとき、a=b=2なので条件Bを満たす。
それ以外のとき、6=3a≦b=n/2なので条件Bを満たす
・n=8 mod 16のとき
(a,b)=(1,0),(2,0)mod 4にしかならない
・n=0 mod 16のとき
(a,b)=(4,n/4)が自明に条件※を満たす。
もしn/16が(相異なるとは限らない)素数p,qを持てば(4p,n/4p)が(1,n)とは異なる条件※を満たす解となる。よって条件Aを満たすにはn=16または16pが必要(pは奇素数)。
n=16のとき、a=4=4なので条件Bを満たす。
それ以外のとき、12=3a≦b=n/4なので条件Bを満たす

以上から、求めるnは4,16,4p,16p,qに限る(pは奇素数、qはmod4で3の素数)
プロフィール

hide(ハイド)

Author:hide(ハイド)

○やりこみとか

DQMキャラバンハートRTA
3:57:15

(11年5月21日)

GB版DQM2
低レベルボス攻略

(14年5月6日)

ぱるメロ
旧曲10780pts %表
ツアー3628630
(12年3月~14年9月)

ポケモン不思議のダンジョン
赤の救助隊
RTA 2:49:59

(14年12月5日)

ポケモン不思議のダンジョン
赤の救助隊
状況再現ありRTA 2:26:36

(15年3月9日)

DQM系データ

フリーノベルゲ攻略

最新記事
カテゴリ
リンク
最新コメント
月別アーカイブ