★本記事は
日曜数学 Advent Calendar 2022
の参加記事として書きました。
Introduction
以前、Twitterで以下のような問題を見かけました。
を以上の素数とする。このとき、はの倍数となることを示せ。
※参考元:
https://mobile.twitter.com/pickover/status/1536796647128276994
上記は、の倍数をの倍数としても成り立つのですが、本記事では話を簡単にするため、主にで考えていきます。また、同じ条件ので、はの倍数、はの倍数になることも確認できます。
この問題は、中高生も十分チャレンジできるもので、さまざまな解答が考えられると思います。
私も最初は、合同式で解いたのですが、だんだん欲が出てきて、「の単元群の構造から何とかできないものか」と考えながらツイートしていたところ、
tsujimotter
さんからTwitterでバシッと教えてもらえました! ありがとうございます!
そのときに教えてもらったことを含め、3つの証明を考えてみました。
まずは初等的に解いてみる
は以上の素数なので、かつである。
よって、かつとなる。
したがって、はの倍数かつの倍数である。
とは互いに素なので、はの倍数であることがわかる。
実は、この問題の条件「は以上の素数」はゆるめることができます。
はと互いに素な整数であるとする(つまり、はと互いに素であり、と互いに素な整数)。
このとき、はの倍数となる。
命題1の証明①
※元の問題の証明とほぼ同様に示せます。
はと互いに素なので、かつである。
よって、かつとなる。
したがって、はの倍数かつの倍数である。
とは互いに素なので、はの倍数であることがわかる。
上記の証明でのポイントとして
① を(互いに素な)とに分けて考える。
② でもでも「はと合同」「は乗するとと合同」という似た性質が出てくる。
といったところが挙げられます。
数論におけるオイラーの定理を使って証明してみる
オイラーの定理
を以上の整数とし、を以上以下の整数のなかでと互いに素なものの個数を表す関数とする。
このとき、をと互いに素な整数とすると
が成り立つ。
※オイラーの定理において、を素数とすると、フェルマーの小定理となります。
オイラーの定理を使って、命題1を証明してみましょう。
命題1の証明②
はと互いに素であり、と互いに素である。
なので、オイラーの定理より
かつ
となる。
したがって、はの倍数かつの倍数である。
とは互いに素なので、はの倍数であることがわかる。
の構造を考えてみる
結論から言うと、以下が成り立ちます。
おそらく、代数系の話に慣れている人はこれを見て「は位数の巡回群の直積になっているから、はでなんだな」とわかると思います。なんなら証明も頭のなかでサクサクできてしまうことでしょう(私はサクサクできません)。
今回は、上記の命題を示すための道具、および、命題の証明を紹介していきたいと思います。「もう問題は解けたし、そこまでしなくても…」と思う方もいるかもしれませんが、代数系の知識や言葉を使うことで、構造が見えてくるところが面白いですし、先述の2つの証明を上空から見下ろすような感じで眺められるようになるのではないかと思います。
きちんと証明していくと長くなりすぎてしまうので、適宜省略していきます。細かいことにはあまり言及しないので、くわしくは代数系の入門書などを参照してみてください。
「群と環の定義はなんとなく知っているけれど、他のことは知らない」という方が読み通せることを目標に説明していきます。できるだけ、抽象的で難しそうな部分は迂回しつつ、命題の証明へ辿り着けるようにがんばって書いてみます。
とについて
を正の整数、を整数とし、
とする。
において、演算を以下で定める。
このとき、は演算に関して可換環をなす。
証明は省略する。
※環の定義などについて:
環の定義とその具体例(高校数学の美しい物語)
※演算がwell-definedであることも示す(well-definedについては後述)。
次に
(のなかで乗法逆元を持つ元全体)
とする。
は演算に関してアーベル群をなす(は命題4で定めたもの)。
また
が成り立つ。
アーベル群であることの証明は省略する。
※群の定義などについて:
群の定義といろいろな具体例(高校数学の美しい物語)
として、であることを示す。
とすると、とは互いに素であることから、ある整数が存在して
を満たす。
※上記のようなの存在について:
一次不定方程式ax+by=cの整数解(高校数学の美しい物語)
よって、であり、
となる。
したがって、なので、であることがわかる。
次に、とする。
が存在することから、ある整数が存在して
を満たす。
よって、となるので
である。
したがって、ある整数が存在して
を満たす。
に共通の素因数が存在すると仮定すると、はで割り切れることになるので、であることに矛盾。よって、は共通の素因数を持たないことがわかる。
したがって、とは互いに素であり、である。
以上より、であることが示された。
巡回群について
巡回群
を群とする。あるの元が存在して
と表せるとき、は巡回群であるといい、を巡回群の生成元という。
また、このとき、とかく。
巡回群の位数は有限であるとし、その位数を、生成元を、単位元をとする。このとき、が成り立つ。
まず、を満たす正の整数が存在することを背理法で示す。
任意の正の整数について、と仮定する。以上の整数に対し、とすると、となる。
仮定より、のときなので、、つまり、であることがわかる。よって、ならばが成り立つ。
したがって、の元は互いに相異なる。このときは無限集合を含むので、の位数が有限であることに矛盾する。
よって、を満たす正の整数が存在することがわかった。
ここで、を満たす最小の正の整数をとおく。
を以上以下の整数で、であるとし、が成り立つとする。
このとき、となる。
であることと、の定義から、でなければならない。よって、ならばが成り立つ。
したがって、の元は互いに相異なる。
を以上の整数とする。をで割ったときの商を、余りをとすると
となる。
また、より、であることから
となり、なので、先ほどと同様に、をで割ったときの商と余りを考えれば、ある以上以下の整数が存在して
を満たす。
したがって、である。
の位数はなので、でなければならない。よって、の定義から、であることがわかる。
巡回群の位数は有限であるとし、その位数を、単位元をとする。このとき、の任意の元に対して、が成り立つ。
の生成元をとすると、の任意の元に対して、ある整数が存在して
とかける。
よって、命題6より
となる。
準同型写像や同型について
群の準同型写像と同型
を群とし、をからへの写像とする。
に対し、となるとき、を準同型写像という。
特に、が全単射であるとき、を同型写像とよび、とは群として同型であるという。
また、このとき、とかく。
環の準同型写像と同型
を環とし、をからへの写像とする。
に対し、となり、であるとき、を準同型写像という。
特に、が全単射であるとき、を同型写像とよび、とは環として同型であるという。
また、このとき、とかく。
群での演算を、いずれも同じ記号で定義を書きましたが、本来はの演算を、の演算をなど、区別して書くべきかもしれません。
しかし、そのように書かれている本などを見かけたことがないので、どちらもと書くことにします。
環での演算についても同様です。
足立恒雄「ガロア理論講義」pp.31-32では、群の準同型写像や同型について、以下のように書かれています。
[前略]写像が群の演算を保存しているとき準同型写像であるというのである.
代数学では, 集合の材質, 色彩, 要素の大きさなど物理的な意味には一切関知しないで, 単に元(構成要素)の間の演算にだけ関心を限定している.したがって群が同型であるとは, 群という数学的概念のカテゴリーでは「同一である」とみなしてよいということを主張しているのである.
これらの記述は、準同型写像や同型について「わかりにくい」と感じる方のヒントになるかもしれない、と思ったので引用しました。
は位数の巡回群であるとする。このとき、が成り立つ。
は演算に関するアーベル群である。
の生成元を、単位元をとする。写像からへの写像を
として定める。
とすると
となるので、は準同型写像である。
任意のに対し、となるので、は全射である。
とすると、となるので、はの倍数である。
の位数はなので、命題6より、となる。よって、が成り立ち、は単射であることがわかる。
直積について
を群とする。
とし、演算を
と定めると、は演算に関して群をなす。
証明は省略する。
を環とする。
とし、演算を
と定めると、は演算に関して環をなす。
証明は省略する。
との構造
を正の整数とし、とは互いに素であるとする。
このとき
が成り立つ。
からへの写像を
として定める。
、つまり、ならば、かつが成り立つ。
よって、ならばとなるのでであることがわかる。
よって、はwell-difined(後述の注意参照)。
は準同型写像であることを示す。
となるので、は準同型写像である。
は全単射であることを示す。
中国剰余定理より、が互いに素なので、任意の整数に対して
を満たす以上以下の整数がただ1つ存在する。
したがって、任意の整数に対して、を満たすが存在し、そのようなはただ1つに定まる。
よって、は全単射である。
well-defined
例えば、なので、となるの取り方は無限に存在しています。
なのに、となってしまっていたら、は写像の定義を満たしません。
そのため、どのようなを取ってきたとしても、は変わらないことをいう必要があります。
命題4についても、どのようなを取ってきたとしても、,という演算の結果は変わらないことをいう必要があります。
を正の整数とし、とは互いに素であるとする。
このとき
が成り立つ。
からへの写像を
として定める(は命題10の証明におけるのへの制限となっている)。
が(群の)準同型写像であること、単射であることは命題11の証明より従う。
が全射であることを示す。
の元を任意にとる。
中国剰余定理より、が互いに素なので、
を満たす以上以下の整数がただ1つ存在する。
とが共通の素因数を持つと仮定すると、もで割り切れるので矛盾。よって、とは互いに素である。
同様にして、とも互いに素であることがわかる。
したがって、とは互いに素である。
よって、を満たすが存在する。
3つ目の証明へ
命題1の証明③
命題11より、とすると
が成り立つ。
例4と例5より、は位数の巡回群である。
をと互いに素な整数とし、写像を命題11の証明と同じものとする。
であることと、命題6の系から
となる。
であり、は単射なので、である。
したがって、はの倍数となることがわかる。
また、命題7を使うと、以下のように書けます(命題3と同じ)。
命題1の証明③を長々と書いてしまいましたが、前に引用した文章
代数学では, 集合の材質, 色彩, 要素の大きさなど物理的な意味には一切関知しないで, 単に元(構成要素)の間の演算にだけ関心を限定している.したがって群が同型であるとは, 群という数学的概念のカテゴリーでは「同一である」とみなしてよいということを主張しているのである.(足立恒雄「ガロア理論講義」pp.31-32)
を念頭に置きつつ、少しお気持ちを書いておきます。
とは同型なので、「群という数学的概念のカテゴリーでは『同一である』とみなしてよい」(上記引用文より抜粋)ということになります。
は位数の巡回群の直積なので、命題6の系から「どんな元をとってきても、乗したら単位元」ということがわかります。
群として「同一である」とみなすと、も、「どんな元をとってきても、乗したら単位元」という性質を持っていることがわかるので、と互いに素な整数について、となることが見えてきます。
24の倍数であること、さらに一般化してみる
24の倍数
についても同様に
となるので、の構造を調べることで、同じことができます。
結論だけ書くと
であり、は位数の巡回群となっているので、も位数の巡回群だったことを合わせれば
となり、のケースでも位数の巡回群の直積で表せます。
をと互いに素な整数(つまり、はと互いに素であり、と互いに素な整数)とすれば、の場合と同様にして、はの倍数となることがわかります。
一般化(の倍数)
について以下が成り立ちます。
※参考:
(Z/nZ)*の群構造(INTEGERS)
例えば、とすれば
となります。
をと互いに素な整数(つまり、はと互いに素であり、と互いに素な整数)とすれば、はの倍数となることがわかります。
(から「どんな元をとってきても、乗したら単位元」ということが見えてきます)
同様に、とすると、をと互いに素な整数(つまり、はと互いに素であり、と互いに素な整数)とすれば、はの倍数となることがわかります。
このように考えていくと、以下が成り立つことがわかります。
はと互いに素であり、と互いに素な整数とし、を以上の整数とする。このとき、はの倍数となる。
感想など
序盤に書いた証明のポイント
① を(互いに素な)とに分けて考える。
② でもでも「はと合同」「は乗するとと合同」という似た性質が出てくる。
ですが、①は
という見方につながり
②は、とが位数の巡回群であり、いずれも
と表せることにつながってくると思います。
また、オイラーの定理を使った証明では、の位数との位数が現れています。
私自身、最初は元の問題を「面白い数遊び」のようにとらえていましたが、代数系の知識や言葉で見てみると、その構造が見えてきて、一層の面白味を感じられるようになってきました。
今回はの構造を考える上で、かなり限定的なシチュエーションのみを扱ってきましたが、より一般の場合については以下の記事が参考になると思います。
(Z/nZ)*の群構造(INTEGERS)
Z/nZの単元群の構造の話(ぱいおつ日記)
最後に、
日曜数学 Advent Calendar 2022
のページに
レベルは問いませんが、面白さを読者が共感できるように「自分はなぜそのトピックを面白いと思ったのか」を熱く書いてもらえると嬉しいです。
と記載されていたので、ちょっとだけ書いておきます。
受験生のとき、「もう勉強つらい」「整数問題、解けない」と思いながら解き始めたのが「マスター・オブ・整数」という参考書でした。
面白くて、受験勉強であることを忘れながら解いた思い出があります。
そして、大学での代数学の授業で、などの話を知り「あのときの整数問題は、こんな話につながっていたのか!」と嬉しくなりました。
そのときの「面白かった!」「もっと知りたい!」という感覚は、何年も経った今でもずっと続いていると感じますし、今回のテーマで記事を書こうと思った原動力にもなっていると思います。
最初は「受験勉強のため」と思ってやり始めたことが、こんなに続くというのは、自分でもちょっと不思議です。「自分の好きなこと」との出会いは意外なところからやってくるのかもしれません。
※余談ですが、この記事を書きながら「私は雰囲気で代数学をやってきたんだな…」と改めて気づき、基礎がガタガタなことを反省しました。