Homeに戻る  一覧に戻る 

Integral Points on Conic Curve: x^2-xy+y^2=63812593012478171313181


[2001.06.02]x2-xy+y2=63812593012478171313181の整点


Q[\rho]上での有理素数p=3n+1の素因数分解

Euclid整域Q[\rho]上で、有理素数p=3n+1の素因数分解を考察する。
     (a+b\rho)(a+b\rho2)=p --------(1)
となる有理整数(a,b)が存在し、a+b\rho,a+b\rho2は、Q[\rho]の素数である。pが与えられたとき、(a,b)を効率良く求めることができる。

(1)より、Q[\rho]の代数的整数a+b\rhoは、pの約数である。
もし、k2≡ -3 (mod p)となる有理整数kを求めることができれば、
     (k-1-2\rho)(k-1-2\rho2)=k2+3 ≡ 0 (mod p) --------(2)
であり、a+b\rhoは素数なので、Q[\rho]の素因数分解の一意性から、a+b\rhoは(k-1-2\rho)または(k-1-2\rho2)の約数である。
よって、Q[\rho]上でpおよび(k-1-2\rho)のgcdを(Euclidの互除法で)計算すると、a+b\rhoまたはその同伴数(associate)のどれかを得ることができる。

最後に、与えられた(a,p)に対して、x2≡ a (mod p)となる有理整数xを求める方法は、参考文献[2]によると、以下のアルゴリズムで実現できる。

■mod pでのaの平方根、つまりx2≡ a (mod p)なるxを求める。

  1. 乱数nでかつmod pで平方非剰余なるもの,つまり,(n/p)= -1なるnを選択する。
    ただし、(・/・)は平方剰余記号とする。
  2. p-1=2eqを満たすe,q(奇数)を計算する。
  3. y:=nq(mod p), r:=e, x:=a(q-1)/2 (mod p)
  4. b:=ax2(mod p), x:=ax (mod p)
  5. while b \not\equiv 1 (mod p) do:
  6.     m:=min{m >=0 | b2m≡ 1 (mod p)}
  7.     t:=yr-m-1 (mod p), y:=t2 (mod p), r:=m
  8.     x:=xt (mod p), b:=by (mod p).
  9. return x.

■x2-xy+y2=63812593012478171313181の整点を求める。

有理素数63812593012478171313181 ≡ 1(mod 3)をQ[\rho]上で素因数分解することに帰着する。
上記の2次曲線は、x,yについて対称なので、(x,y)がその整点ならば、(y,x)もその整点である。
上記の2次曲線上の整点(x,y)を求めるプログラムを作成して、実行すると、このように、6個の整点が見つかる。
よって、上記の2次曲線の整点はこれらの6個とx,yを入れ替えた点6個、全部で12個である。

     ±(251320726401,253882874381),
     ±(253882874381,2562147980),
     ±(2562147980,-251320726401),
     ±(253882874381,251320726401),
     ±(2562147980,253882874381),
     ±(251320726401,-2562147980)


[参考文献]


Last Update: 2016.11.07
H.Nakao

Homeに戻る[Homeに戻る]  一覧に戻る[一覧に戻る]