素数のある2次形式による表現について

203

　素数$p$は$60$と互いに素とする。このとき、次のことが成り立つ。
$$\begin{array}{ccc} p\equiv 1, 49\md{60}&\leftrightarrow&p=x^2-15y^2~と書ける \\[5pt] \hline p\equiv 11,~59\md{60}&\leftrightarrow&p=-x^2+15y^2~と書ける \\[5pt] \hline p\equiv 17,~53\md{60}&\leftrightarrow&p = 5x^2-3y^2~と書ける \\[5pt] \hline p\equiv 7,~43\md{60}&\leftrightarrow&p=3x^2-5y^2~と書ける \end{array}$$
確かめてみる。

具体例

$p=9181$は$60$で割って$1$余る素数で次のように書ける：
$$ 9181 = {139}^2 - 15\cdot{26}^2. $$
$p=9769$は$60$で割って$49$余る素数で次のように書ける：
$$ 9769 = {128}^2 - 15\cdot {21}^2. $$
$p=9491$は$60$で割って$11$余る素数で次のように書ける：
$$ 9491 = -{38}^2 + 15\cdot {27}^2. $$
$p=9539$は$60$で割って$59$余る素数で次のように書ける：
$$ 9539 = -{94}^2 + 15\cdot {35}^2. $$
$p=9677$は$60$で割って$17$余る素数で次のように書ける：
$$ 9677 = 5\cdot {44}^2 - 3\cdot 1^2.$$
$p=9533$は$60$で割って$53$余る素数で次のように書ける：
$$ 9533 = 5\cdot {44}^2 - 3\cdot 7^2. $$
$p=9967$は$60$で割って$7$余る素数で次のように書ける：
$$ 9967 = 3\cdot {58}^2- 5 \cdot 5^2. $$
$p=9883$は$60$で割って$43$余る素数で次のように書ける：
$$ 9883 = 3\cdot {61}^2 - 5\cdot {16}^2. $$

大雑把な証明

まず、もし$p$がこのような式を満たすならば、上二つだとすると、$x,y$は$p$と互いに素だから、
$$0\equiv x^2-15y^2\md{p},~~~~x^2\equiv 15y^2\md{p},~~~~\sqrs{x^2}{p}=\sqrs{y^2}{p}\sqrs{15}{p}$$
となって
$$\sqrs{15}{p}=1$$
を得る。ここで、$p$は$p^2$で割り切れないので、$x$も$y$も$p$と互いに素であることを用いた。あるいは下二つであっても、やはり$x,y$は$p$と互いに素なので、
$$0\equiv 3x^2-5y^2\md{p},~~~~3x^2\equiv 5y^2\md{p},~~~~\sqrs{3}{p}\sqrs{x^2}{p}=\sqrs{5}{p}\sqrs{y^2}{p}$$
から
$$\sqrs{3}{p}=\sqrs{5}{p},~~~~\sqrs{15}{p}=\sqrs{3}{p}\sqrs{5}{p}=\sqrs{5}{p}^2=1$$
を得る。ゆえに、いずれの場合も$15$がモジュロ$p$での平方剰余になる。
　逆に、$15$が$p$を法とする平方剰余のとき、
$$15 = b^2 - pc$$
を満たす整数$b,c$が取れる。このとき、$2$次形式：
$$f(x,~y)=px^2 + 2bxy + cy^2$$
の判別式は$15$になる。なお、通常の判別式の$1/4$のものを採用している。ところで、多少込み入った議論により、判別式が$15$の$2$次形式は次のいずれかに同値である。同値というのは、整数の変換：
$$x= \alpha u + \beta v,~~~y=\gamma u + \delta v,~~~~\alpha\delta - \beta \gamma = 1$$
という整数$\alpha,\beta,\gamma,\delta$による変換：$f(x,~y)\to g(u,~v)$で移りあうことをいう。次の形式である：
$$x^2-15y^2,~~~-x^2+15y^2,~~~ 5x^2-3y^2,~~~3x^2-5y^2. $$
　ところで、
$$f(1,~0)=p$$
であり、$f(x,~y)$は同値変形でこれらに移る、その際、整数組に関しては可逆変換を繰り返すから、結果的に$g(u,~v)$になったとすると、
$$g(u_0,~v_0)=p$$
を満たす整数$u_0,v_0$が取れることになる。
　あとは、いずれに該当するかを調べればいい。これについても平方剰余記号を使って調べられる。
$$p=x^2-15y^2~~ならば~~\sqrs{p}{3}=1~~かつ~~\sqrs{p}{5}=1.$$
$$p=-x^2+15y^2~~ならば~~\sqrs{p}{3}=-1~~かつ~~\sqrs{p}{5}=1.$$
$$p=5x^2-3y^2~~ならば~~\sqrs{p}{3}=-1~~かつ~~\sqrs{p}{5}=-1.$$
$$p=3x^2-5y^2~~ならば~~\sqrs{p}{3}=1~~かつ~~\sqrs{p}{5}=-1.$$
証明には$2$や$-1$が$3$や$5$を法として平方剰余かどうかによりおなじみの計算で確かめられる。
　$15$が$p$を法とする平方剰余になるための条件は、$60$で割った余りが、
$$1,~7,~11,~17,~43,~49,~59,~53$$
のどれかになること。これは、
$$ 1=\sqrs{15}{p}=\sqrs{3}{p}\sqrs{5}{p}=\sqrs{-1}{p}\cdot \sqrs{p}{3}\sqrs{p}{5} $$
と書けることからわかる。これを$4$パターンに分類して主張を得る。

もっと大きい数で

今年の素数年でやってみる。

$\mathrm{mod}~60$で$1$か$49$

\begin{align*} 20200801\equiv 1\md{60},~~~20200801 &= {4529}^2 - 15 \cdot {144}^2.\\[5pt] 20201101\equiv 1\md{60},~~~20201101 &= {4579}^2 - 15 \cdot {226}^2.\\[5pt] 20200309 \equiv 49\md{60},~~~20200309&={4678}^2 - 15\cdot{335}^2.\\[5pt] 20200429 \equiv 49\md{60},~~~20200429&={5683}^2 - 15\cdot{898}^2.\\[5pt] 20200729\equiv 49\md{60},~~~20200729&={4592}^2-15\cdot {243}^2.\\[5pt] 20201029\equiv 49\md{60},~~~20201029&={5738}^2-15\cdot {921}^2. \end{align*}
こんな感じ。

$\mathrm{mod}~60$で$11$か$59$

\begin{align*} 20200511\equiv 11\md{60},~~~20200511 &= -{1183}^2 + 15 \cdot {1200}^2.\\[5pt] 20201231\equiv 11\md{60},~~~20201231 &= -{2428}^2 + 15 \cdot {1319}^2.\\[5pt] 20200619\equiv 59\md{60},~~~20200619 &= -{439}^2 + 15\cdot {1166}^2. \end{align*}
この3つ。

$\mathrm{mod}~60$で$17$か$53$

$17$の方は無かったです。$53$が１つだけ。
$$ 20200613\equiv 53\md{60},~~~20200613 = 5\cdot {2452}^2-3\cdot {1813}^2. $$

$\mathrm{mod}~60$で$7$か$43$

\begin{align*} 20201227\equiv 7\md{60},~~~20201227 &= 3\cdot {2597}^2 -5 \cdot {80}^2.\\[5pt] 20200123\equiv 43\md{60},~~~20200123 &= 3\cdot {2616}^2 -5\cdot {257}^2.\\[5pt] 20200723\equiv 43\md{60},~~~20200723 &= 3\cdot {3724}^2 -5\cdot {2069}^2.\\[5pt] 20200903\equiv 43\md{60},~~~20200903 &= 3\cdot {3619}^2 -5\cdot {1954}^2. \end{align*}

求めるのに使ったコード

はじめに、何らかの方法で1～10000の間の素数を$p$という配列に入れる。それを使えばこのコードで指定した範囲の素数を取り出せる。日付素数はこれで出した。

      def getLargePrimes(p, a, b):
    # 1～100000000のうち、aとbの間にあるものを抽出する感じ。
    # pには1～10000の中の素数がすべて入っているとする。
    result = []
    for i in range(a, b):
        isPrime = True
        for k in p:
            if k * k > i: break
            if i % k == 0:
                isPrime = False
                break
        if isPrime:
            result.append(i)
    return result

その中から然るべきモジュロの素数を出してからは、次のコードで$2$次形式を変換しつつ整数解を求めるコードを使う。簡易的な簡約操作なので、最終形の$(a,~b,~c)$が$(2,~1,~-7)$または$(-2,~1,~7)$になる場合がある。この場合は、
$$2x^2+2xy-7y^2=5(x-y)^2-3(x-2y)^2,$$
$$-2x^2+2xy+7y^2=3(x+2y)^2-5(x+y)^2$$
を用いて欲しい値を出す。そのために$3$パターン出力している。

      def routine(q):
    # まずa, b, cを出すには、モジュロqでの15の平方根を出す必要がある。
    # それをbとし、aはqで、cについては15=b^2-acから出す。すなわちc=(b^2-15)/q.
    b = 0
    for i in range(q):
        if i * i % q == 15:
            b = q - i
            break
    a = q
    c = int((b*b - 15) / q)
    # 2次形式(a, b, c)を簡約してaが±1か±2になるようにする感じ。
    # 各ステップでは新しい(c, b', a')をまずb'がbと|c|でモジュロで同じでかつ
    # 2|b'|≦|c|となるようにする。で、b'^2-a'c=15からa'を出す。
    # そのあとn=(b-b')/cを出してx'=nx+y, y'=xと変換する(x=1,y=0からスタート）。
    # 最後にxとyを出力して終了。
    x=1
    y=0
    for i in range(100):
        if abs(a)==1 or abs(a)==2: break
        if int(b) == 0: break
        b2 = b % abs(c)
        a2 = int((b2*b2-15) / c)
        n = (b - b2) / c
        a = c
        b = b2
        c = a2
        z = x
        x = n * x + y
        y = z
    print("(x, y) = (" + str(x) + ", " + str(y) + ")")
    print("(x-y, x-2y) = (" + str(x-y) + ", " + str(x-2*y) + ")")
    print("(x+2y, x+y) = (" + str(x+2*y) + ", " + str(x+y) + ")")
    print(a, b, c)

def main():
    routine(20200903)
"""
    出力結果：
    (x, y) = (289.0, 1665.0)
    (x-y, x-2y) = (-1376.0, -3041.0)
    (x+2y, x+y) = (3619.0, 1954.0)
    -2 1 7
    -2 1 7なので(x+2y, x+y)を採用。
"""