2014/08/13

整数問題のテクニック:平方数でないことの証明

分野: 整数問題  レベル: 数学オリンピック

平方数でないことを証明するためには以下の2つの方法が有効な場合が多い。
1:平方剰余を考える
2:両側から1違いの平方数で挟む


平方数でないことの証明は入試や数学オリンピックの整数問題で頻出のパターンです。

1:平方剰余を考える

まずは両辺を $3$ や $4$ で割った余りを考えて矛盾を示す方法です。

例1

$m^2=3n-1$
を満たす自然数 $m,n$ が存在しないことを証明せよ。

解答

$m$ が $3$ の倍数のとき $m^2$ も $3$ の倍数。
$m$ が $3$ で割って $1$ 余る場合or $2$ 余る場合は $m^2$ は $3$ で割って $1$ 余る。
しかし,右辺:$3n-1$ は $3$ で割って $2$ 余るので矛盾。

このように,平方数を $k$ で割った余りについては制約が加わります。可能な余りのことを平方剰余と言います。
例えば,上記の議論により $3$ の平方剰余は $0,1$ であることが分かります。

上記の例をはじめ多くの入試問題は平方剰余の議論で解決します。
平方剰余のより詳しい話は平方剰余と基本的な問題を参照してください。

2:不等式で挟む

本記事のメインテーマです。

平方剰余でうまくいかないときはこちらの方針を試みてください。
基本的な考え方は,「平方数はとびとびにある」です。
つまり,うまく自然数 $N$ を持ってきて
$N^2 <m <(N+1)^2$ を示せれば $m$ は平方数とはなりえないことが分かります。

さきほどより難易度の高い例題です。

例2

$f(n)=n^4+2n^2+n+5$ が平方数となるような $n$ を全て求めよ。

解答

$(n^2+1)^2=n^4+2n^2+1$
$(n^2+2)^2=n^4+4n^2+4$
よって,
$(n^2+1)^2 <f(n) <(n^2+2)^2$
っぽい。
実際左側の不等式は明らかに成立。
右側の不等式は,$2n^2+n+5 <4n^2+4$ のとき成立。
実際 $n\geq 2$ のときこの二次不等式は満たされることが分かる。
よって,$n\geq 2$ のとき,
$(n^2+1)^2 <f(n) <(n^2+2)^2$
となり $k$ は平方数とはならない。
$n=1$ のときは $f(1)=9$ となり平方数となる。

観察

平方数かどうか判定したいもの $f(n)$ が $n$ の偶数次の多項式で表されているときに有効な方法です。(奇数次だとうまく平方式に直せない)実際上記の例は $4$ 次式なので $2$ 次式の平方式で両側から挟むことができています。

平方剰余による議論がもしうまくいくとすると,「任意の自然数 $n$ に対して $f(n)$ は平方数でない」という結論が得られます。しかし,上記の例では $n=1$ で平方数となっているので,平方剰余による議論はうまく行きそうにないことが分かります。

数オリの問題に挑戦1

2011年アジア太平洋数学オリンピック(APMO)第一問です。APMOにしては簡単な問題です。

問題

$a^2+b+c, b^2+c+a, c^2+a+b$ がいずれも平方数になるような自然数 $a,b,c$ の組が存在しないことを証明せよ。

解答

背理法で証明する。 $a^2+b+c$ は $a^2$ より大きい平方数なので,
$(a+1)^2\leq a^2+b+c$
よって $2a+1\leq b+c$
同様にして $2b+1\leq c+a, 2c+1\leq a+b$
以上3つの不等式を足し合わせると $3\leq 0$ となり矛盾。

数オリの問題に挑戦2

2004年日本数学オリンピック(JMO)本選第一問です。
さすが数学オリンピックの問題,上記の方法に加えて一工夫必要です。

問題

$2n^2+1, 3n^2+1, 6n^2+1$ がいずれも平方数になるような自然数 $n$ が存在しないことを証明せよ。

最初の部分が一番むずかしいです。

解答

平方数の積は平方数なので,もし $3$ つの数がいずれも平方数であるとすると,
$f(n)=(2n^2+1)(3n^2+1)(6n^2+1)$ も平方数である。そのような $n$ は不等式で挟むことで限定できそう。(以下分かるようにそのような $n$ は存在しない!)

あとは不等式で挟む方針を知っていれば簡単。
左辺を展開すると,
$f(n)=36n^6+36n^4+11n^2+1$

$n^6$ と $n^4$ の係数に着目して以下のような平方式を考える:
$(6n^3+3n)^2=36n^6+36n^4+9n^2$
$(6n^3+3n+1)^2=36n^6+36n^4+12n^3+9n^2+6n+1$

よって,任意の自然数 $n$ に対して
$(6n^3+3n)^2 <f(n) <(6n^3+3n+1)^2$
よって $f(n)$ は平方数でないので矛盾

整数問題の多くは剰余,不等式,因数分解のいずれかで解決します。

Tag: 各地の数オリの過去問

分野: 整数問題  レベル: 数学オリンピック