問題
\( p \)は\( 3 \)以上の素数であり, \( x, y \)は\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)をみたす整数であるとする。このとき\( x^2 \)を\( 2p \)で割った余りと, \( y^2 \)を\( 2p \)で割った余りが等しければ, \( x=y \)であることを示せ。
下書き
「割った余りが等しい」\( \Leftrightarrow \)「差が割り切れる」は常識。よって, 問題文から直ちに, 「\( x^2 – y^2 \)は\( 2p \)の倍数」と言える。これくらいは使ってよいと思うが, 不安な人は, 以下のように書いておけばよい。
\( x^2 = 2pX + r, y^2 = 2pY + r \)(ただし\( X, Y, r \)は整数)と書けるので, 辺々差を取って, \( x^2 – y^2 = 2p(X-Y) \), すなわち\( 2p \times (整数) \)となり, \( x^2 – y^2 \)は\( 2p \)の倍数。
さて, 整数問題なので因数分解して, \( (x+y)(x-y) = 2pk \)(\( k \)は整数)…①をもとに考えていく。
\( 2 \)と\( p \)は互いに素だから,
「\( x+y \)と\( x-y \)のどちらかが, \( 2 \)の倍数」…②
「\( x+y \)と\( x-y \)のどちらかが, \( p \)の倍数」…③
がどちらも成り立つことが分かる。
今回は特に\( x+y \)と\( x-y \)のどちらかが\( p \)の倍数③が有用で, \( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)…④より, 候補が絞られてくる。
偶奇性をなるべく使わない方法
場合分けをしてすべての場合を調べる。ただし, 枠で囲んだ部分の論理が回りくどく分かりにくいので, 出来れば偶奇性に着目できる方が望ましい。
\( x+y \)が, \( p \)の倍数だったとき
\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( 0 \leqq x+y \leqq 2p \)だから, \( x+y = 0, p, 2p \)に絞られる。
もし, \( x+y = 0 \)であれば, \( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④の範囲を考えると, \( x = y = 0 \)しかあり得ないのでOK。
\( x+y = 2p \)のときも, \( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④の範囲を考えると, \( x = y = p \)しかあり得ないのでOK。
\( x+y = p \)のときは, 仮に\( x=y \)とすると\( x = \frac{p}{2} \)となってしまうので, \( x+y = p \)はそもそもあり得ないということを言えばよい。
背理法的に, \( x+y = p \)が成り立つと仮定して, 矛盾を導き, \( x+y \neq p \)を言う。\( x+y = p \)は奇数なので, \( x+y \)と\( x-y \)のどちらかが\( 2 \)の倍数②と合わせると, \( x-y \)の方が\( 2 \)の倍数となる。しかし, このような整数\( x, y \)は存在しない。
これは, 以下のようにして示せる。
\( x + y \)は奇数なので\( x + y = 2k_1 + 1 \), \( x – y\)は偶数なので\( x – y = 2k_2 \)とおける(\( k_1, k_2 \)は整数)。\( y \)を消去すると, \( x = k_1 + k_2 + \frac{1}{2} \)となるがこれは整数ではない。
よって, そもそも\( x+y = p \)となるようなことはない。
\( x-y \)が, \( p \)の倍数だったとき
\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( -p \leqq x-y \leqq p \)だから, \( x+y = -p, 0, p \)に絞られる。
もし, \( x-y = 0 \)であれば, \( x = y \)となるのでOK。
\( x+y = p \)や\( x-y = -p \)のときがあり得ないのは, 上と同様に示せる。
偶奇性を活用する方法
\( x+y \)と\( x-y \)のどちらかが\( 2 \)の倍数②を少し言い換えて, \( x+y \)と\( x-y \)のどちらかは偶数。
ここで, 少し発想が難しいが, 偶奇を意識して足し算をしてみる。\( (x+y) + (x-y) = 2x \)と偶数になるので, \( x+y \)と\( x-y \)の偶奇は一致する(ともに奇数またはともに偶数)ことがわかる。
よって, \( x+y \)と\( x-y \)はどちらも偶数であることが確定する。
あとは\( x+y \)と\( x-y \)のどちらかが\( p \)の倍数③より場合分けをして示す。
\( x+y \)が, \( p \)の倍数だったとき
\( 0 \leqq x+y \leqq 2p \)だから, \( x+y = 0, p, 2p \)に絞られるが, \( x + y \)は偶数なので, \( x + y = 0, 2p \)となる。以下同様。
\( x-y \)が, \( p \)の倍数だったとき
\( -p \leqq x-y \leqq p \)だから, \( x-y = -p, 0, p \)に絞られるが, \( x – y \)は偶数なので, \( x – y = 0 \)となる。以下同様。
解答例
\( x^2 \)を\( 2p \)で割った余りと, \( y^2 \)を\( 2p \)で割った余りが等しいとき, \( x^2 – y^2 = (x+y)(x-y) \)は, \( 2p \)の倍数となる。
\( p \)は\( 3 \)以上の素数より\( p \)と\( 2 \)は互いに素であり, \( x+y \)と\( x-y \)はどちらも整数なので, 「\( x+y \)と\( x-y \)のどちらかは\( p \)の倍数」…①であり, 「\( x+y \)と\( x-y \)のどちらかは\( 2 \)の倍数」…②でもある。
ここで, \( (x+y) + (x-y) = 2x \)は, \( x \)が整数より偶数なので, \( x+y \)と\( x-y \)の偶奇は一致する。よって, \( x+y \)と\( x-y \)のどちらかは\( 2 \)の倍数②と合わせて, 「\( x+y \)と\( x-y \)はともに偶数」…③である。
なお, \( x, y, x+y, x-y \)の範囲は, 以下のとおりである。
\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)…④
\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( 0 \leqq x+y \leqq 2p \)…⑤
\( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( -p \leqq x-y \leqq p \)…⑥
以下, \( x+y \)と\( x-y \)のどちらかは\( p \)の倍数①により(i)(ii)の場合に分けて考える。
(i) \( x+y \)が\( p \)の倍数のとき, \( x+y \)と\( x-y \)はともに偶数③, \( 0 \leqq x+y \leqq 2p \)⑤, \( p \)は奇数より, \( x+y = 0, 2p \)
(i – i) \( x+y = 0 \)のとき, \( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( x=y=0 \)
(i – ii) \( x+y = 2p \)のとき, \( 0 \leqq x \leqq p, 0 \leqq y \leqq p \)④より, \( x=y=p \)
(ii) \( x-y \)が\( p \)の倍数のとき, \( x+y \)と\( x-y \)はともに偶数③, \( -p \leqq x-y \leqq p \)⑥, \( p \)は奇数より, \( x-y = 0 \)すなわち\( x = y \)
以上より, \( x^2 \)を\( 2p \)で割った余りと\( y^2 \)を\( 2p \)で割った余りが等しければ, \( x=y \)が成り立つ。
振り返り
倍数条件が多くて意外と大変。そこから偶奇に注目して絞り込むところも難しい。
しかし, やっていることはほぼ一本道(同値の言い換え→倍数条件→場合分け)なので, 整数問題の標準的な問題として, 解き方を確実に押さえておいてほしい。
コメント