数オリでよく使われるテクニック～平方数に関わる話～

1909

久しぶりでしょうか。PCTです。タイトルが不安定なコーナーですが、鳩ノ巣原理編の続編とでも思ってください。

今日は〇〇が平方数でないことを示せに使われるような解法を説明します。
まず例題をして以下のような問題を上げます。
$3$ の倍数でない正整数 $n$ に対して、 $n^{2} + 3 n + 1$ が平方数にならないことを示せ。

$n$ の制約からしてバレバレなところがありますが $mod 3$ を取ります。すると $1 \equiv n mod 3$ の時は $n^{2} + 3 n + 1 \equiv 2 mod 3$ 、 $2 \equiv n mod 3$ の時は $n^{2} + 3 n + 1 \equiv 2 mod 3$ となり、どちらにしても $n^{2} + 3 n + 1 \equiv 2$ となりますが、そのような平方数は存在しないためこの値は平方数にならない。より示された。

ここでルジャンドル記号について話しておきます。

ルジャンドル記号

奇素数 $p$ 、整数 $k$ に対して、 $a^{2} = k mod p$ を満たす整数 $a$ が存在する時 $k$ を $p$ の平方剰余という。
$k$ が $p$ の平方剰余である時、 $(\frac{k}{p}) = 1$ とし、そうでない時 $(\frac{k}{p}) = - 1$ とする。

$- 1, 1$ にわざわざする意味があるのか？と思う方もいるかもしれませんが、今から話す定理によりこの定義はかなり強くなります。

オイラーの基準

$a$ を $p$ と互いに素な整数とする時、 $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}}$ が成り立つ。

ルジャンドル記号の準同型性

$a, b$ を $p$ と互いに素な整数とする時 $(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p})$ が成り立つ。

平方剰余の第一補充法則

オイラーの基準の $a$ に $- 1$ を代入した場合の $(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}}$ が成り立つ。

平方剰余の第二補充法則

$(\frac{2}{p}) = (- 1)^{\frac{p^{2} - 1}{8}}$ が成り立つ。

平方剰余の相互法則

相異なる奇素数 $p, q$ に対して、 $(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \frac{q - 1}{2}}$ が成り立つ。

本来は証明まで乗せるべきなのでしょうが僕がまだ証明を理解できていないものもあるので今回はなしとさせていただきます。いつか証明をする記事を投稿します。

例えば今回の $x^{2} \equiv 2 mod 3$ となる整数 $x$ が存在するかですが、平方剰余の第二補充法則より、 $(\frac{- 1}{3}) = (- 1)^{\frac{2}{2}} = - 1$ となるため平方剰余でないことが分かります。

他にも平方数でないことを示すには $2$ 個の隣り合う平方数で挟むという方法もあります。こちらも結構頻出なので一度経験しておくことをお勧めします。

ではここらへんで終わります。お読みいただきありがとうございました。

投稿日：2020年11月10日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

PCTprobability

138

6028

中2です。数学をしています。適当に書きたい記事を書いていきます。

他の人のコメント

コメントはありません。

読み込み中

PCTprobability

数オリでよく使われるテクニック～平方数に関わる話～