平方剰余の問題を解いてみます

平方剰余の例題を解いてみます

 これまでに得た知識を総合すると、どのような方程式についても、平方剰余/非剰余の判定ができます(もちろん $a$ や $p$ があまりに大きな値であれば計算は大変です)。判定に必要となる定理をすべて再掲します。

 $p,\:q$ は奇素数、$(a,\:p)=(b,\:p)=1$

[定理 F11 積の法則]
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]

[定理 F13 第1補充法則]
\[\left(\frac{-1}{p}\right)= (-1)^{\frac{p-1}{2}}\]

[定理 F14 第2補充法則]
\[\left(\frac{2}{p}\right)= (-1)^{\frac{p^2-1}{8}}\]

[定理 F15 相互法則]
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]

 それでは合同方程式
 
\[x^2\equiv 18\quad (\mathrm{mod}\:31)\]
に解があるかどうかを調べましょう(このような簡素な問いに答えるために、私たちはここまで頑張ってきたのです!)。ルジャンドル記号を用いて表すと
 
\[\left(\frac{18}{31}\right)\]
の値が $1$ なら解があり(平方剰余であり)、$-1$ なら解なし(平方非剰余)です。まずは積の形に分解します。
 
\[\left(\frac{18}{31}\right)=\left(\frac{2\cdot 3^2}{31}\right)=\left(\frac{2}{31}\right)\left(\frac{3}{31}\right)^2\]
 $\displaystyle\left(\frac{2}{31}\right)$ は第2補充法則によって計算できます。
 
\[\left(\frac{2}{31}\right)=(-1)^{\frac{31^2-1}{8}}=1\]
 $\displaystyle\left(\frac{3}{31}\right)$ の計算には相互法則を用います。相互法則によれば
 
\[\left(\frac{3}{31}\right)\left(\frac{31}{3}\right)=(-1)^{\frac{3-1}{2}}(-1)^{\frac{31-1}{2}}=1\]
なので、
 
\[\left(\frac{3}{31}\right)=\left(\frac{31}{3}\right)\]
と書き直せます。このように変形できることが相互法則の恩恵なのです。なぜなら、$31$ は $\mathrm{mod}\:3$ において $1$ と合同なので、
 
\[\left(\frac{31}{3}\right)=\left(\frac{1}{3}\right)=1\]
と計算できます (任意の $p$ で、$x^2\equiv 1$ は解をもちます)。したがって、
 
\[\left(\frac{18}{31}\right)=1\]
となり、$x^2\equiv18\:(\mathrm{mod}\:31)$ は解をもつことがわかりました。すなわち $18$ は $31$ の平方剰余です。
 

Excel で平方剰余の問題を解いてみます

 コンピュータの力を借りると、平方剰余/非剰余の判定のみならず、実際の解を求めることも比較的容易にできます。さきほどの合同方程式
 
\[x^2\equiv18\quad (\mathrm{mod}\:31)\]
を満たす最小の整数 $x$ を求めてみます。

 Excelによる平方剰余の解法

 A 列に $1$ から $10$ までの整数、B 列にその平方数、C 列には平方数を $31$ で割った値が並んでいます。余りが $18$ となっているセル(緑色に塗られているところ)があります。すなわち解が $x=7$ であることがわかります。このように問題をビジュアル化できるので、Excel は数論にとって相性の良いツールです。
 

VBA で平方剰余の問題を解いてみます

 VBA で平方剰余の問題を解く QR関数をつくっておきました。QR は Quadratic Residue(平方剰余)の頭文字です。VBE を起動して標準モジュールに貼りつけると、ワークシートで Excel 関数のように扱えます。

 Function QR(a As Long, p As Long) As Variant

 Dim x As Long

 'p について a と合同な最小数を得ます
  Do While a > p
   a = a - p
  Loop

  '解が見つからない場合は False を返します
  QR = False

 ' x^2 を p で割った余りが a であれば、x は解です
 For x = 1 To p - 1

  If x ^ 2 Mod p = a Then
   QR = x
   Exit For
  End If

 Next x

 End Function

 QR関数を使うときはセルに

=QR(a,p)

の形で入力します。もし解がなければ(平方非剰余であるならば)、この関数は False を返します。さきほどの合同方程式
 
\[x^2\equiv18\quad (\mathrm{mod}\:31)\]
をこの関数で解いてみましょう。

=QR(18,31)

と入力すると、7 という値が返ってきます。つまり、$18$ は $31$ の平方剰余であり、方程式の解は $x=7$ です。
 

数論講座はまだまだ続きます

 「平方剰余の相互法則」の証明をもって、この講座も一段落しました。これまで私の拙い文章に付き合っていただいて本当にありがとうございます。稚拙であることは承知の上で、整数の世界の魅力が少しでも伝わることを願いつつ、私なりに精一杯の努力をしてきたつもりです。しかし各記事で論理展開の不明瞭さや、誤字脱字などが散見されるかと思います。至らないところがあれば、遠慮なくコメントで御批判ください。

 数論講座はまだまだ続けてゆく予定です。あまり時間をおかずに、次回記事「ペルの方程式」が入ると思いますので、これからもよろしくお願いします。 ≫ 整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください