剰余類の星を見る
この記事は、数学A ｢整数の性質｣ が既習の方を対象に書いていますが、
未習の方でもある程度理解できるよう脚注*1 を付しています。
お久しぶりです(^-^)
私事ですが、先日第1志望の大学の入試が無事終了し、現在ドキドキの合格発表待ち期間です。
もともと数学が大好きで、理科も好きなほうだったとはいえ、受験勉強はやっぱり大変で、何度もだらけそうになったりもしました。
でも、志望校を最後まで変えることなく、友達と支え合いながら頑張れましたし、何より体調も崩さず、それなりに良いコンディションで当日を乗り切れて一安心です。
ただ、個人的には試験終わってから合格発表までの期間のほうが苦しくて…不安に潰されそうな毎日で、大丈夫だよって優しい言葉をかけてくれる友達に救われます。
でも、採点期間が長いのは大学の先生方がきちんと厳密に採点してくださっている証拠。
あんまり早いと逆に適当なんじゃないか？！と不安になります。気長に待とうと思います。
受験って、大学によっては複数回チャンスのある場合もありますが、基本一発勝負じゃないですか。もう一度チャレンジしたくても1年間待たなくてはならない。
本番体調が優れなかったなど様々な要因で、努力したにも関わらず結果を残せないというケースもあり得ます。
もし、自分が1番行きたい学校に合格できたら、そんな人たちがいたんだということを常に忘れず、自分がその学校の生徒として認められたことに感謝して最後まで通いたいものですね。
(まあ、そんなの綺麗事じゃんと言われてしまったら何も言い返せないのですが。)
報われるべき人が全員報われる世界があれば誰もが幸せなはずです。
でもそんなものは残念ながら理想論で。
受験だけに限らず、今年も、これからも、報われるべき人が1人でも多く報われることを願っています！
結局1番言いたかったことはこれなのでした。
…と、どこから目線で言っている私は、今回の受験で、｢報われるべき人｣ となれたのでしょうかね。
本題
さて！タイトルにもある通り、本日のテーマは剰余類 (じょうよるい) です。
剰余類とは？
いろいろな数字を、ある数で割った余りで分類したもののことです。
3で割った余りで分類すると、5と11は同じカテゴリー ｢余り2｣ に分類されるということです。
大学で習う定義だともうちょっと複雑だそうですが、高校における剰余類の定義はこれです。
ちょうど4ヶ月ほど前の話ですが、放課後一緒に教室に残って勉強していた友人が、ふとこんなことを教えてくれました。
0から9までの点を円上に並べます。
そして、九九の1の段に出てくる数の下1桁だけを取り出した数を、順番につないでいきます。
1×1=1、1×2=2、ですから、まずこんなふうに1と2がつながれます。
次に、1×3=3、ですから、2と3がつながれます。
これを繰り返していくと (九九だと、1×9=9、で終わりですが、そのまま1×10=10 (→下1桁をとって0) というふうに続けられますね)、最初の点に戻ってきます。1×11以降は同じ線の上をぐるぐる回るようです。
するとこんな図形が出来上がります。正十角形ですね。
九九の2の段で同じことをすると…
2×6=12、ですでに1周してしまいました。正五角形です。2の段ですので奇数の点は通らないのですね。
どんどん続けます。3の段です。
全部の点を通っていますね。
4の段です。
おお、馴染みのある図形が出てきました。星型です。やはり奇数の点は通りませんね。
5の段です。
なんとこれだけです。確かに5の段の下1桁は5か0かの2択ですもんね。5×3=15、の時点ですでに1周です。
6の段です。
あれ、見覚えがありますね。4の段とまったく同じ図形です！
実際に点を指でなぞって確認してほしいのですが、4の段と図形は同じですが逆回りになっているようです。
7の段です。
またもや見覚えのある図形が出てきました。3の段と同じです。こちらも、図形は同じものの逆回りです。
8の段です。2の段と同じ図形、逆回りです。
9の段です。1の段と同じ図形、逆回りです。
九九にはありませんが10の段を考えてみると、下1桁はすべて0なので、線は出てこないですね。
点は10個ですし、このへんで止めておきましょう。
今まで出てきた図形をまとめてみます。
緑の字は段の数を表します。
どうやら、1と9、3と7のように、足して10になる段数のときに、同じ図形が出てくるようですね。
友人と一緒にこれらのいろいろな図形を黒板に描きながら、私は疑問に思ったのです。
①なぜ、段数が足して10になる組み合わせは同じ図形を描くのか？
②なぜ、1周するまでにすべての点を経由する段と、一部の点だけ経由して1周してしまう段があるのか？
③もし、点が10個ではなかったら、どうなるのか？
私はこれらの問いについて、彼女と考えてみることにしました。
まず①ですが、この10という数字は、点が10個であることと関係がありそうですよね。
ということは、点が10個あるときは ｢足して10｣ ですが、点が9個のときは ｢足して9｣ のときが、同じ図形を描く条件であると考えられます。
順番が前後しますが、①より先に③を考えてみるのが手っ取り早そうですね。
さて、点が10個でないときどうなるか。
そもそもこれらの図形は、計算をした結果の ｢下1桁｣ を考えているからこそ、点が10個あるわけですよね。どんな整数でも、下1桁は0~9 の10個の数字のうちのいずれかになります。これを利用しているわけです。
ここで点を勝手に9個にしてしまったらどうなるのでしょうか。10個の数字のうち、どれかをなくしてみましょうか。
…いやいや、今日世界から突然3を消すなんてことはできませんよね。
問題にぶつかったときは定義にかえることが大切です。
世の中の数字が10種類であるそもそもの理由はなんでしょう？
そうです！
世の中が十進法*2 で回っているからです！！
(余談ですが、十進法が使われている理由としては、人類の指が10本であり、昔から10を1単位としてものを数えてきたからだと言われています。)
ということは、九進法の世界で考えれば点を9個にすることができるし、十一進法の世界なら11個にすることができるということになりますね。
二進法や三進法ですと点が少なすぎて考察しにくそうなので、九進法と十一進法あたりで試してみましょうか。
九進法では、9という数字を使わず、8₍₉₎の次が10₍₉₎ (=9₍₁₀₎) *3 になるので、点が9個になります。
ここから先は、今までやってきたのと同じ操作を、出てくる数字を9進数に変換した数字の下1桁で考えます。
まず1の段です。
9₍₁₀₎=10₍₉₎→0、10₍₁₀₎=11₍₉₎→1
(※ ｢→｣ は数字の下1桁を取り出す操作を表します。)
なので、このようになります。
2の段です。
10₍₁₀₎=11₍₉₎→1、12₍₁₀₎=13₍₉₎→3、
14₍₁₀₎=15₍₉₎→5、16₍₁₀₎=17₍₉₎→7、
18₍₁₀₎=20₍₉₎→0、20₍₁₀₎=22₍₉₎→2
なので、このようになります。
十進法では奇数の点は通りませんでしたが、九進法ではすべての点を通っていますね。問②につながりそうです。
同様に繰り返します。どんどんいきましょう。
…うーん、3や4の倍数を9進数に変換していく作業がなかなか面倒です。
なにかもっと簡単な方法はないでしょうか。
今回も、｢定義にかえって｣ みますよ。
今やっている作業は、10進数での操作を9進数に拡張するというものです。
10進数での操作、それは段の数の倍数の下1桁を取り出すというものでした。
下1桁を取り出すって、一体何をしているのでしょうか？
十の位以上の位がどのような数字であれ、すべての数をたった10種類に分類している、ということです。
気付いていただけましたか？
キーワードは ｢分類｣ です。冒頭で私が述べたこと、そしてこのお話のタイトルを思い出してほしいのです。
そう！下1桁で数字を分類するということは、｢10で割ったときの剰余類｣ を考えるということと同値ではないでしょうか！
では、9進数に変換したのちに下1桁を取り出すという操作ならば…？
｢9で割ったときの剰余類｣ ですよね。
すなわち、これまで点の横に書いていた1桁の数字は、剰余類における ｢カテゴリー｣ を表していたというように考えることができます。
このように考えると、わざわざ9進数に変換することなく、9で割ったときの余りをつないでいくことで同じ操作が可能ですね。
確かに、数字を9で割ったとき、とりうる余りは0から8までの9通りですので、用意した9個の点に一致しています。
よって3の段は
3→3、6→6、9→0、12→3
(※ ｢→｣ は9で割った余りへの変換を表します。)
なので、こうなりますね。
正三角形が現れました。
4の段は
4→4、8→8、12→3、16→7、20→2、
24→6、28→1、32→5、36→0、40→4
なので、
このようになります。
さて、先ほど、点が9個のとき、段数が ｢足して9｣ になるときは同じ図形を描くという仮説を立てましたよね。
実際、5の段をやってみると…
やはり、4の段と同じ図形が出てきました！
同様に、6の段は3の段、7の段は2の段、8の段は1の段と一致します。
まとめると次のようになります。
そろそろ飽きてきたと思うので、11進数は各段の紹介は割愛して、まとめたものを紹介しようと思います。
っと、その前に少しだけ補足を。
11進数では、10進数の ｢10｣ にあたる数を1文字で表す必要があります。が、この世界が十進法で回っているため、アラビア数字は10種類しかありません。なので、一般にアルファベットの ｢A｣ が使われています。10₍₁₀₎=A₍₁₁₎です。
16進数ですと、10進数の10, 11, 12, 13, 14, 15 を、それぞれA, B, C, D, E, F で代用しているということですね。位取り記数法*4 において、組み合わせる数字を1文字にしておかないと、混乱しますからね。
さて、11進数の図形はこのようになります。余りが10になる数字は点 ｢A｣ を通るわけです。
やはり、｢足して11｣ になっていますね。
※以下、nとkは任意の自然数 (ただしn≧k) とします。
問③：もし、点が10個ではなかったら、どうなるのか？ について、
点が10個でない場合 ── 一般に点がn個の場合 ── でも、
- 段の数の倍数を、n進数に変換したときの一の位、すなわちnで割ったときの剰余類を考えることにより、点が10個のときと同様の操作が定義でき、図形を描くことができる。
- ｢足してn｣ となる2数の段で描かれる図形は一致し、図形の描かれる方向は逆回りである。
という結論が出せました。
では次に、問①：なぜ、段数が足して10になる組み合わせは同じ図形を描くのか？ です。
先ほど、点の数をnに拡張したので、n進法においての ｢足してn｣ の組、といったほうが適当ですね。
これはそれぞれの図形が描かれる過程に着目することで理解できます。
10進数で考えます。
1の段では、1×1、1×2、と進んでいくにつれて、10で割った余りは1ずつ増加する (10の剰余類で考えているため、9から1増えた数は0とします。) ため、つながれる点はすべて隣接し、時計回りにつながれていきます。
一方9の段では、9×1、9×2、と進んでいくにつれて、10で割った余りは1ずつ減少するため、つながれる点はすべて隣接し、こちらは反時計回りにつながれていきます。
そのため、1の段と9の段では、｢隣接している点をつなぐ｣ という規則がともに成り立つので、最終的に1周したとき、できあがる図形は同じで逆回りになるのです。
2の段も見てみましょう。
2の段では、10で割った余りは2ずつ増加するため、点を1個飛ばしで時計回りにつないでいきます。
一方8の段では、1個飛ばしで反時計回りにつながれるのですね。
一般に、k×1、k×2、…をnで割った余りは規則的に変動するので、同じ間隔で点がつながれていきます。その ｢間隔｣ というのが、kの段と(n-k)の段では一致し、符号が反対になるので、1周回ったとき同じ図形が描かれているのです。
nやkなどという文字を使うと一気に難しく感じると思いますが、上で述べた具体例を理解していただければOKです！
これが問①の結論と言えそうです。
では最後に、問②：なぜ、1周するまでにすべての点を経由する段と、一部の点だけ経由して1周してしまう段があるのか？ を考えましょう。
もう一度11進数のときの図形を見てください。
ここで注目してほしいのが、11進数のときだけ、どの段でもすべての点を通っているということです。
そういえば、9, 10, 11 のうち、11だけが素数ですね。それも関係があるのかもしれません。
9, 10, 11進数において、どんなときにすべての点を通るのか考察してみます。
11進数では、すべての数で、すべての点を通ります。
9進数では、
1, 2, 4, 5, 7, 8 の段ではすべての点を通りますが、3, 6 の段では通りません。
10進数では、
1, 3, 7, 9 の段ではすべての点を通りますが、2, 4, 5, 6, 8 の段では通りません。
同じ2の段でも、9進数と11進数ではすべての点を通りますが、10進数では通りません。
つまり、すべての点を通るかどうかは、段の数自体ではなく、｢段数と進数との関係｣ に影響されていると考えられます。
では、10進数のとき、1から9までの数字のうち、1, 3, 7, 9 (以下、グループAとします) だけがもつ共通の性質はなにかないでしょうか？
2, 4, 5, 6, 8 (以下、グループBとします) はもたない性質です。
偶数、すなわち2の倍数が全部グループBに属するのが気になりますね。しかし、奇数である5もグループBなんですね。
…2と5？ 10=2×5、ですよね。
グループBはすべて2の倍数または5の倍数です。
一方、グループAはすべて2の倍数でも5の倍数でもありません。
そして、この2と5というのは、10の約数です。
見えてきましたね。
グループAは、すべて10と共通の素因数*5 をもたないんです！
これを言い換えると…？？
そうです。｢互いに素｣ *6 ですね！
ということは、グループBは、｢互いに素でない｣ グループですね。
これを踏まえて9進数を見てみましょう。
グループA : 1, 2, 4, 5, 7, 8
グループB : 3, 6
確かに、グループAに属する数だけが、すべて9と ｢互いに素｣ です。
11進数も見てみます。
グループA : 1~10すべて
グループB : 要素なし
素数はそもそも1とその数自身しか約数をもたないので、自身より小さい数はすべて ｢互いに素｣ になりますよね。
1~10がすべてグループAに属するのは、11が素数だから、ということで納得ですね！
っと、まだ問②は解決していないですよ。
なぜ段数と進数が ｢互いに素｣ ならばすべての点を通るのかの説明がついていませんからね。
段数と進数が互いに素でないとき、通らない点が存在するというのは直感的にわかりやすいので、説明してみます。
10進数の2の段では、10と2が共通の素因数2をもつため、1個飛ばしで点を選ぶことによって、円周が5等分されてしまいます。そのため、点2から始まって、5回目の移動で点2に戻ってきます。
10個すべての点を通るためには、少なくとも10回の移動が必要ですが、スタート地点に戻った瞬間同じことが繰り返されるので、2の段では5回しか移動できないも同然です。
そのため、2の段ではすべての点は通ることができないのです。
互いに素でない他の組み合わせでも同じことが言えて、10進数なら10回目、9進数なら9回目の移動よりも前に最初の点に戻ってきてしまうと、すべての点は通ることができませんね。
では、互いに素である場合は…？
これがなかなか難しいんですよね。互いに素である場合、最初の点に戻ってくるまでの間に、すべての点を通っているだけでなく、同じ点を重複して通っていないというのもポイントです。
私と友人も、その日はこれについては解決できませんでした。
しかし数日後、数学の問題集を解いているときに、私はこの問を解決できそうな入試問題に出会ったのです！
その問題がこちら。
※以下の説明の都合上、問題に使われている文字を一部変更しています。実際には、nではなくpが、kではなくqが使われています。
n, k を互いに素な正の整数とする。
(1)任意の整数xに対して、n個の整数 x-k, x-2k, ……, x-nk をnで割った余りはすべて相異なることを証明せよ。
(2)略
[2008 奈良県立医大 (一部改変) ]
解答例は記事の最後に。
(1)の問題文は、証明せよと言っているのですから、まあ成り立つわけです。
そして、実はこの命題は、あとで証明で確認してほしいのですが、同様の方法で、文中にある ｢-｣ をすべて ｢+｣ に変えても成り立つことが証明できます。
今回はこの問題の、｢+バージョン｣ に着目したいのです。
この問題において、xは任意の整数、つまりどのような整数でも成り立つということです。なので、x=0としても成り立ちますよね。
すると、上記の問題文の ｢+バージョン｣ は次のように書き換えることができます。
nとkを互いに素な正の整数とする。
このとき、n個の整数 k, 2k, ……, nk をnで割った余りはすべて相異なることを証明せよ。
これは証明ができるので、真な命題です。
ここで、nを進数、kを段数とすると、nとkが互いに素であれば、n個の点すべてを漏れなく、ダブりなく通ることが説明できます。
点はそもそも、剰余類、すなわち、nで割った余りを表しているんでしたよね。
これで問②：なぜ、1周するまでにすべての点を経由する段と、一部の点だけ経由して1周してしまう段があるのか？ が解決です。
長くなりましたが、この記事が、数学Aの整数の性質で学んだ剰余類やn進数などに興味を持っていただけるきっかけになれば幸いです！
今回扱ったのは9, 10, 11進数の場合の図形のみですので、
5進数だとどうなるんだろう？
じゃあ、16進数では？？
と疑問が湧いてきた方は是非！進数や段数をいろんな値に変えた星々を描いて楽しんでみてはいかがでしょう。
最後に、先ほど紹介した問題の解答例を載せて終わります。まだ解いていない人は、良かったら自力で証明できるかチャレンジしてみてくださいね(^^)
〈証明 (もとの問題) 〉
x-akとx-bk (1≦a＜b≦n, aとbは自然数) をnで割った余りが一致すると仮定する。
このとき、(x-ak)-(x-bk) すなわち (b-a)k がnで割り切れる。
ここで、b-aとkは整数であり、1≦a＜b≦n であることから、1≦b-a≦n-1 であるので、b-aがnの倍数であることはない。
よってkがnの倍数である。
これはnとkが互いに素であることに矛盾する。
ゆえに、n個の整数 x-k, x-2k, ……, x-nk をnで割った余りはすべて相異なる。(証明終)
〈証明 (+バージョン) 〉
x+akとx+bk (1≦a＜b≦n, aとbは自然数) をnで割った余りが一致すると仮定する。
このとき、(x+bk)-(x+ak) すなわち (b-a)k がnで割り切れる。
以下、上とまったく同様。(証明終)
*1:←この青字の数字をタップすることでもとの文章の場所に戻れます。
*2:進法とは、数を表記するときに、いくつを単位にして次の位に繰り上げるかということです。私たちが普段使う十進法では、10個単位で次の位に進むため、1が10個集まったものが10で、10が10個集まったものが100で…というふうになっています。そのため、10種類の数字が必要です。例えば二進法では、1が2個集まったものが10であり、その10が2個集まったもの (十進法で言うと4) が100で…となります。そのため、数字は0と1の2種類しか必要ありません。
*3:数字の右下についたカッコ内の数字は、何進数での表記であるかを表します。私たちは日常生活で基本的に十進法しか使わない (コンピュータ内では二進法が使われていますが…) ため、₍₁₀₎は大抵省略されています。
*4:35という数字が、10が3個と1が5個という意味を表すように、数字を右から順に一の位、十の位、…と定めることによって表される数字の書き方のことを、位取り(くらいどり)記数法といいます。位取り記数法が使われていない数字の表し方として有名なものに、ギリシャ数字があります。VIIは7を表しますが、これはV(=5)+I(=1)+I(=1)という意味なので、こんな書き方は実際しないでしょうがIVIと書いても同じ数を表しますよね。その代わり、大きな数を表すとき、大量の数字が羅列して見にくくなることがあります。大きな数でも簡潔に表すことができる一方、数字を入れ替えると異なる数になってしまうというのが位取り記数法の特徴です。
*5:54=2×3³、105=3×5×7、というふうに、すべての数は素数の積に分解することができ、その数を構成する素数を素因数、数字を素因数に分解することを素因数分解といいます。
