剰余類とか合同式は聞いたことありますか？
聞いたことありますね。
本格的には大学で理学部数学科に行ったら代数とかでもっと厳密に習いますが、高校の整数問題でも合同式を使うと解答が簡単に書きやすいので高校の参考書でも多く見られると思いますたぶん。
剰余類って概念と合同式の計算とかは、知らなくても3で割った余りが1の時…とか場合わけしたら必要は無いですが、
例えばこのn^3+2n+1を3で割ると1余ることを証明せよ。の問題でも解答はかなり簡単に書けるので時間が限られている試験では非常に役立ちます。
ただ新しい概念なので理解は難しくても合同式の計算自体は中学生でも扱えるようなものです。
まず3を法とする剰余類って言うのを考えてみます。
整数は3で割ると余り0になるのもの、余り1になるもの、余り2になるものの3つに分類されます。
kを整数として、n=3kの時、n=3k+1、n=3k+2とか場合わけして考えたことあると思います。
整数のうちこの余り0になるものの集合をC0、余り1になるものの集合をC1、余り2になるものの集合をC2とします。
C0は-3とか12とか0とかが入っていて、kを整数として3kとかで表せるものが入っています。
C1には4とか-5(=-2×3+1)とか16とか1が入っていて、3k+1とかで表せるものが入っています。
C2には8とか-4(=-2×3+2)とか17とか2が入っていて、3k+2とかで表せるものが入っています。
どの整数も、C0かC1かC2にわけられます。
このC0とかC1とかC2とか3で割った余りが同じものの集まりを、3を法とした剰余類と言います。
だからn=3kの時とか場合分けしたりして問題を解いたことあると思いますが、それはnが剰余類C0に属する時、n=3k+1の時はnが剰余類C1に属する時、n=3k+2に属する時って言うように実は既に剰余類の考え方をしてきています。
剰余類についてだいぶん分かってきた所で、剰余類に属するものは3で割ると同じ余りになるので、この余りが同じになる整数であるって言うことをどう表すかの問題として
≡
の記号を使います。
-3≡0≡3≡6≡9≡…
これを合同式と言います。
もちろん3が法でないと、こうならないので
6≡9(mod 3)
のように(mod 3)と書きます。
文脈上明らかな時は省略されることもあります。
まあ本にはa-bがmで割り切れる時(a,bが同じ剰余類に属する時)
a≡b(mod m)
と書くとか定義されてると思います。
そしてこの-3≡0≡3≡6≡9≡…(mod 3)のようにC0に入ってるのは≡で結べますが、この≡で結べる整数を一つ代表として簡単な0を選びます。
普通の意味の0と剰余類が同じ意味の0がごちゃごちゃになるから、0~(←0の上にバーをかく)とあらわすこともよくあります。
だから-3≡0、9≡0、12≡0と言うようにC0に入ってる整数は0と表せると考えます。
同じようにC1に属するのを代表して1、C2に属するのを代表して2と表して
4≡10≡-5≡1(mod 3)
5≡14≡-4≡2(mod 3)
それで、この表記を使うとどういうメリットがあるかと言うと足し算と引き算と掛け算が普通に出来て式が簡単に書けて便利と言うことです。
証明はa,bを3で割ると余りi,jになるとすると(a≡i、b≡jであるとすると)整数k、hを用いてa=3k+i、b=3h+jと表せて
a+b≡3(k+h)+i+j≡i+j
a-b≡3(k-h)+i-j≡i-j
ab≡3(3kh+kj+hi)+ij≡ij
で、結構当たり前の計算なので反対にいきなりこれを書くと何のためにこういうことをやってるのかわかりにくいのが特徴です。
余談ですが実はこれは素数を法とした時は割り算も出来ます。
割り算はaで割ると言うことはa×b=1となるbが存在してb(=1/a)をかけると言うことですが
例えば5を法とした時、
2×3≡1だから3で割ると言うことは2かけると言うことです。
これは素数を法とした場合のみの話で、例えば素数ではない4を法とすると2×0≡0、2×1≡2、2×2≡0、2×3≡2というように、2には何をかけても1にはなるのが存在しません。
話がそれました。
またおっさんがなんか言うてるなって思っててください。
参照→合同式の割り算
そしたら、実際に合同式を使って問題をやってみましょう。
[問題]
a^2+3b^2=100000001
を満たす整数a,bが存在しないことを証明せよ。
[解答]
a^2+3b^2=100000001
を満たす整数a,bが存在するとすると
nを整数として、3を法として
n≡0の時、n^2≡0×0≡0
n≡1の時、n^2≡1×1≡1
n≡2の時、n^2≡2×2≡4≡1
より
a^2+3^b≡a^2≡0または1であるが
100000001=99999999+2≡2
より矛盾。
したがって、整数a,bは存在しない。
高校数学の公式や問題の解説
整数問題の解法の解説と問題演習
- 関連記事
-
テーマ:算数・数学の学習 - ジャンル:学校・教育
|
▲ページトップへ
