数オリでよく使われるテクニック～平方数に関わる話～
久しぶりでしょうか。PCTです。タイトルが不安定なコーナーですが、鳩ノ巣原理編の続編とでも思ってください。
今日は〇〇が平方数でないことを示せに使われるような解法を説明します。
まず例題をして以下のような問題を上げます。
$3$ の倍数でない正整数 $n$ に対して、$n^2+3n+1$ が平方数にならないことを示せ。
$n$ の制約からしてバレバレなところがありますが $\bmod3$ を取ります。すると $1≡n\bmod3$ の時は $n^2+3n+1≡2\bmod3$ 、$2≡n\bmod3$ の時は $n^2+3n+1≡2\bmod3$ となり、どちらにしても $n^2+3n+1≡2$ となりますが、そのような平方数は存在しないためこの値は平方数にならない。より示された。
ここでルジャンドル記号について話しておきます。
奇素数 $p$、整数 $k$ に対して、$a^2=k\bmod p$ を満たす整数 $a$ が存在する時 $k$ を $p$ の平方剰余という。
$k$ が $p$ の平方剰余である時、$\left(\frac{k}{p}\right)=1$ とし、そうでない時 $\left(\frac{k}{p}\right)=-1$ とする。
$-1,1$ にわざわざする意味があるのか？と思う方もいるかもしれませんが、今から話す定理によりこの定義はかなり強くなります。
$a$ を $p$ と互いに素な整数とする時、$\left(\frac{a}{p}\right)≡a^{\frac{p-1}{2}}$ が成り立つ。
$a,b$ を $p$ と互いに素な整数とする時 $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ が成り立つ。
オイラーの基準の $a$ に $-1$ を代入した場合の $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ が成り立つ。
$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ が成り立つ。
相異なる奇素数 $p,q$ に対して、$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$が成り立つ。
本来は証明まで乗せるべきなのでしょうが僕がまだ証明を理解できていないものもあるので今回はなしとさせていただきます。いつか証明をする記事を投稿します。
例えば今回の $x^2≡2\bmod3$ となる整数 $x$ が存在するかですが、平方剰余の第二補充法則より、$\left(\frac{-1}{3}\right)=(-1)^{\frac{2}{2}}=-1$ となるため平方剰余でないことが分かります。
他にも平方数でないことを示すには $2$ 個の隣り合う平方数で挟むという方法もあります。こちらも結構頻出なので一度経験しておくことをお勧めします。
ではここらへんで終わります。お読みいただきありがとうございました。