11
大学数学基礎解説
文献あり

「p^2-1は12の倍数(p>3)」を群論っぽく考えてみる~整数問題から代数系へ~

1499
1

★本記事は 日曜数学 Advent Calendar 2022 の参加記事として書きました。

Introduction

以前、Twitterで以下のような問題を見かけました。

p5以上の素数とする。このとき、p2112の倍数となることを示せ。

※参考元: https://mobile.twitter.com/pickover/status/1536796647128276994

上記は、12の倍数を24の倍数としても成り立つのですが、本記事では話を簡単にするため、主に12で考えていきます。また、同じ条件のpで、p4148の倍数、p8196の倍数になることも確認できます。

この問題は、中高生も十分チャレンジできるもので、さまざまな解答が考えられると思います。

私も最初は、合同式で解いたのですが、だんだん欲が出てきて、「Z/nZの単元群の構造から何とかできないものか」と考えながらツイートしていたところ、 tsujimotter さんからTwitterでバシッと教えてもらえました! ありがとうございます!

そのときに教えてもらったことを含め、3つの証明を考えてみました。  

まずは初等的に解いてみる

p5以上の素数なので、p±1(mod3)かつp±1(mod4)である。

よって、p21(mod3)かつp21(mod4)となる。

したがって、p213の倍数かつ4の倍数である。

34は互いに素なので、p2112の倍数であることがわかる。

実は、この問題の条件「p5以上の素数」はゆるめることができます。

a12と互いに素な整数であるとする(つまり、a3と互いに素であり、2と互いに素な整数)。

このとき、a2112の倍数となる。

命題1の証明①

※元の問題の証明とほぼ同様に示せます。

a12と互いに素なので、a±1(mod3)かつa±1(mod4)である。

よって、a21(mod3)かつa21(mod4)となる。

したがって、a213の倍数かつ4の倍数である。

34は互いに素なので、a2112の倍数であることがわかる。

上記の証明でのポイントとして

12を(互いに素な)34に分けて考える。
mod3でもmod4でも「a±1と合同」「a2乗すると1と合同」という似た性質が出てくる。

といったところが挙げられます。

数論におけるオイラーの定理を使って証明してみる

オイラーの定理

n2以上の整数とし、ϕ(n)1以上n1以下の整数のなかでnと互いに素なものの個数を表す関数とする。

このとき、anと互いに素な整数とすると

aϕ(n)1(modn)

が成り立つ。

※オイラーの定理において、nを素数pとすると、フェルマーの小定理となります。

オイラーの定理を使って、命題1を証明してみましょう。

命題1の証明②

a3と互いに素であり、4と互いに素である。

ϕ(3)=2, ϕ(4)=2なので、オイラーの定理より

a21(mod3)かつa21(mod4)

となる。

したがって、a213の倍数かつ4の倍数である。

34は互いに素なので、a2112の倍数であることがわかる。

(Z/12Z)×の構造を考えてみる

結論から言うと、以下が成り立ちます。

(Z/12Z)×(Z/3Z)××(Z/4Z)×Z/2Z×Z/2Z

おそらく、代数系の話に慣れている人はこれを見て「(Z/12Z)×は位数2の巡回群の直積になっているから、a2mod121なんだな」とわかると思います。なんなら証明も頭のなかでサクサクできてしまうことでしょう(私はサクサクできません)。

今回は、上記の命題を示すための道具、および、命題の証明を紹介していきたいと思います。「もう問題は解けたし、そこまでしなくても…」と思う方もいるかもしれませんが、代数系の知識や言葉を使うことで、構造が見えてくるところが面白いですし、先述の2つの証明を上空から見下ろすような感じで眺められるようになるのではないかと思います。

きちんと証明していくと長くなりすぎてしまうので、適宜省略していきます。細かいことにはあまり言及しないので、くわしくは代数系の入門書などを参照してみてください。

「群と環の定義はなんとなく知っているけれど、他のことは知らない」という方が読み通せることを目標に説明していきます。できるだけ、抽象的で難しそうな部分は迂回しつつ、命題の証明へ辿り着けるようにがんばって書いてみます。

Z/nZ(Z/nZ)×について

nを正の整数、aを整数とし、

a+nZ={xZ | xa(modn)}

Z/nZ={0+nZ,1+nZ,,(n1)+nZ}

とする。

a+3Z={xZ | xa(mod3)}

Z/3Z={0+3Z,1+3Z,2+3Z}

a+4Z={xZ | xa(mod4)}

Z/4Z={0+4Z,1+4Z,2+4Z,3+4Z}

Z/nZにおいて、演算+,を以下で定める。

a,bZ
(a+nZ)+(b+nZ)=(a+b)+nZ
(a+nZ)(b+nZ)=ab+nZ

このとき、Z/nZは演算+,に関して可換環をなす。

証明は省略する。

※環の定義などについて: 環の定義とその具体例(高校数学の美しい物語)

※演算がwell-definedであることも示す(well-definedについては後述)。

次に

(Z/nZ)×={a+nZZ/nZ| (a+nZ)1が存在する}
Z/nZのなかで乗法逆元を持つ元全体)

とする。

(Z/nZ)×は演算に関してアーベル群をなす(は命題4で定めたもの)。

また

(Z/nZ)×={a+nZZ/nZ| anは互いに素}

が成り立つ。

アーベル群であることの証明は省略する。

※群の定義などについて: 群の定義といろいろな具体例(高校数学の美しい物語)

A={a+nZZ/nZ| anは互いに素}

として、A=(Z/nZ)×であることを示す。

a+nZAとすると、anは互いに素であることから、ある整数x,yが存在して

ax+ny=1

を満たす。

※上記のようなx,yの存在について: 一次不定方程式ax+by=cの整数解(高校数学の美しい物語)

よって、ax1(modn)であり、

(a+nZ)(x+nZ)=ax+nZ=1+nZ

となる。

したがって、(a+nZ)1=x+nZなので、a+nZ(Z/nZ)×であることがわかる。

次に、a+nZ(Z/nZ)×とする。

(an+Z)1が存在することから、ある整数xが存在して

(a+nZ)(x+nZ)=1+nZ

を満たす。

よって、ax+nZ=1+nZとなるので

ax1(modn)

である。

したがって、ある整数yが存在して

ax+ny=1

を満たす。

a,nに共通の素因数pが存在すると仮定すると、ax+nypで割り切れることになるので、ax+ny=1であることに矛盾。よって、a,nは共通の素因数を持たないことがわかる。

したがって、anは互いに素であり、a+nZAである。

以上より、A=(Z/nZ)×であることが示された。

(Z/3Z)×={1+3Z,2+3Z}

(Z/4Z)×={1+4Z,3+4Z}

巡回群について

巡回群

Gを群とする。あるGの元gが存在して

G={gn | nZ}

と表せるとき、Gは巡回群であるといい、gを巡回群Gの生成元という。

また、このとき、G=<g>とかく。

群の位数

Gの濃度(元の総個数)をGの位数とよぶ。

巡回群Gの位数は有限であるとし、その位数をl、生成元をg、単位元をeとする。このとき、gl=eが成り立つ。

まず、gm=eを満たす正の整数mが存在することを背理法で示す。

任意の正の整数mについて、gmeと仮定する。0以上の整数a,b (ab)に対し、ga=gbとすると、gba=eとなる。

仮定より、ba>0のときgbaeなので、ba=0、つまり、a=bであることがわかる。よって、ga=gbならばa=bが成り立つ。

したがって、{e,g,g2,g3,}の元は互いに相異なる。このときGは無限集合{e,g,g2,g3,}を含むので、Gの位数が有限であることに矛盾する。

よって、gm=eを満たす正の整数mが存在することがわかった。

ここで、gm=eを満たす最小の正の整数mm0とおく。

a,b0以上m01以下の整数で、abであるとし、ga=gbが成り立つとする。

このとき、gba=eとなる。

0bam01であることと、m0の定義から、ba=0でなければならない。よって、ga=gbならばa=bが成り立つ。

したがって、{e,g,g2,,gm01}の元は互いに相異なる。

s0以上の整数とする。sm0で割ったときの商をt (0t)、余りをr (0rm01)とすると

gs=gm0t+r=(gm0)tgr=egr=gr

となる。

また、ggm01=eより、g1=gm01であることから

gs=(g1)s=(gm01)s=gs(m01)

となり、s(m01)0なので、先ほどと同様に、s(m01)m0で割ったときの商と余りを考えれば、ある0以上m01以下の整数rが存在して

gs=gr

を満たす。

したがって、G={gn | nZ}={e,g,g2,,gm01}である。

Gの位数はlなので、m0=lでなければならない。よって、m0の定義から、gl=eであることがわかる。

巡回群Gの位数は有限であるとし、その位数をl、単位元をeとする。このとき、Gの任意の元aに対して、al=eが成り立つ。

Gの生成元をgとすると、Gの任意の元aに対して、ある整数mが存在して

a=gm

とかける。

よって、命題6より

al=(gm)l=gml=(gl)m=em=e

となる。

(Z/3Z)×={1+3Z,1+3Z}=<1+3Z>

となり、(Z/3Z)×は位数2(=ϕ(3))の巡回群である。

また、(1+3Z)2=1+3Zとなる。

(Z/4Z)×={1+4Z,1+4Z}=<1+4Z>

となり、(Z/4Z)×は位数2(=ϕ(4))の巡回群である。

また、(1+4Z)2=1+4Zとなる。

準同型写像や同型について

群の準同型写像と同型

G,Gを群とし、TGからGへの写像とする。

x,yGに対し、T(xy)=T(x)T(y)となるとき、Tを準同型写像という。

特に、Tが全単射であるとき、Tを同型写像とよび、GGは群として同型であるという。

また、このとき、GGとかく。

環の準同型写像と同型

R,Rを環とし、TRからRへの写像とする。

x,yRに対し、T(xy)=T(x)T(y), T(x+y)=T(x)+T(y)となり、T(1)=1であるとき、Tを準同型写像という。

特に、Tが全単射であるとき、Tを同型写像とよび、RRは環として同型であるという。

また、このとき、RRとかく。

G,Gでの演算を、いずれも同じ記号で定義を書きましたが、本来はGの演算をGの演算をなど、区別して書くべきかもしれません。

しかし、そのように書かれている本などを見かけたことがないので、どちらもと書くことにします。

R,Rでの演算+,についても同様です。

足立恒雄「ガロア理論講義」pp.31-32では、群の準同型写像や同型について、以下のように書かれています。

[前略]写像Tが群の演算を保存しているとき準同型写像であるというのである.

代数学では, 集合の材質, 色彩, 要素の大きさなど物理的な意味には一切関知しないで, 単に元(構成要素)の間の演算にだけ関心を限定している.したがって群が同型であるとは, 群という数学的概念のカテゴリーでは「同一である」とみなしてよいということを主張しているのである.

これらの記述は、準同型写像や同型について「わかりにくい」と感じる方のヒントになるかもしれない、と思ったので引用しました。

Gは位数nの巡回群であるとする。このとき、GZ/nZが成り立つ。

Z/nZは演算+に関するアーベル群である。

Gの生成元をg、単位元をeとする。写像GからZ/nZへの写像T

T(ga)=a+nZ (aZ)

として定める。

a,bZとすると

T(gagb)=T(ga+b)=(a+b)+nZ=(a+nZ)+(b+nZ)=T(ga)+T(gb)

となるので、Tは準同型写像である。

任意のa+nZZ/nZに対し、T(ga)=a+nZとなるので、Tは全射である。

T(ga)=T(gb)とすると、a+nZ=b+nZとなるので、abnの倍数である。

Gの位数はnなので、命題6より、gab=eとなる。よって、ga=gbが成り立ち、Tは単射であることがわかる。

例4と例5より、(Z/3Z)×,(Z/4Z)×は位数2の巡回群なので

(Z/3Z)×Z/2Z
(Z/4Z)×Z/2Z

直積について

G,Gを群とする。

G×G={(a,b) | aG, bG}

とし、演算

(a,b)(c,d)=(ac,bd)

と定めると、G×Gは演算に関して群をなす。

証明は省略する。

R,Rを環とする。

R×R={(a,b) | aR, bR}

とし、演算+,

(a,b)+(c,d)=(a+c,b+d)
(a,b)(c,d)=(ac,bd)

と定めると、R×Rは演算+,に関して環をなす。

証明は省略する。

Z/mnZ(Z/mnZ)×の構造

m,nを正の整数とし、mnは互いに素であるとする。

このとき

Z/mnZZ/mZ×Z/nZ

が成り立つ。

Z/mnZからZ/mZ×Z/nZへの写像T

T(a+mnZ)=(a+mZ,a+nZ)(aZ)

として定める。

a+mnZ=b+mnZ、つまり、ab(modmn)ならば、ab(modm)かつab(modn)が成り立つ。

よって、a+mnZ=b+mnZならば(a+mZ,a+nZ)=(b+mZ,b+nZ)となるのでT(a+mnZ)=T(b+mnZ)であることがわかる。

よって、Tはwell-difined(後述の注意参照)。

Tは準同型写像であることを示す。

T((a+mnZ)+(b+mnZ))=T((a+b)+mnZ)=((a+b)+mZ,(a+b)+nZ)=(a+mZ,a+nZ)+(b+mZ,b+nZ)=T(a+mnZ)+T(b+mnZ)

T((a+mnZ)(b+mnZ))=T(ab+mnZ)=(ab+mZ,ab+nZ)=(a+mZ,a+nZ)(b+mZ,b+nZ)=T(a+mnZ)T(b+mnZ)

T(1+mnZ)=(1+mZ,1+nZ)

となるので、Tは準同型写像である。

Tは全単射であることを示す。

中国剰余定理より、m,nが互いに素なので、任意の整数a,bに対して

xa(modm)
xb(modn)

を満たす0以上mn1以下の整数xがただ1つ存在する。

したがって、任意の整数a,bに対して、T(x+mnZ)=(a+mZ,b+nZ)を満たすx+mnZZ/mnZが存在し、そのようなx+mnZはただ1つに定まる。

よって、Tは全単射である。

well-defined

例えば、1+12Z=13+12Z=25+12Z=なので、1+12Z=a+12Zとなるaの取り方は無限に存在しています。

1+12Z=13+12Zなのに、T(1+12Z)T(13+12Z)となってしまっていたら、Tは写像の定義を満たしません。

そのため、どのようなa+12Zを取ってきたとしても、T(a+12Z)は変わらないことをいう必要があります。

命題4についても、どのようなa+nZ,b+nZを取ってきたとしても、(a+nZ)+(b+nZ),(a+nZ)(b+nZ)という演算の結果は変わらないことをいう必要があります。

m,nを正の整数とし、mnは互いに素であるとする。

このとき

(Z/mnZ)×(Z/mZ)××(Z/nZ)×

が成り立つ。

(Z/mnZ)×から(Z/mZ)××(Z/nZ)×への写像S

S(a+mnZ)=(a+mZ,a+nZ)(aZ)

として定める(Sは命題10の証明におけるT(Z/mnZ)×への制限となっている)。

Sが(群の)準同型写像であること、単射であることは命題11の証明より従う。

Sが全射であることを示す。

(Z/mZ)××(Z/nZ)×の元(a+mZ,b+nZ)を任意にとる。

中国剰余定理より、m,nが互いに素なので、

xa(modm)
xb(modn)

を満たす0以上mn1以下の整数xがただ1つ存在する。

xmが共通の素因数pを持つと仮定すると、apで割り切れるので矛盾。よって、xmは互いに素である。

同様にして、xnも互いに素であることがわかる。

したがって、xmnは互いに素である。

よって、S(x+mnZ)=(a+mZ,b+nZ)を満たすx+mnZ(Z/mnZ)×が存在する。

3つ目の証明へ

命題1の証明③

命題11より、m=3,n=4とすると

(Z/12Z)×(Z/3Z)××(Z/4Z)×

が成り立つ。

例4と例5より、(Z/3Z)×,(Z/4Z)×は位数2の巡回群である。

a12と互いに素な整数とし、写像Sを命題11の証明と同じものとする。

S(a2+12Z)=(a2+3Z,a2+4Z)=((a+3Z)2,(a+4Z)2)

であることと、命題6の系から

S(a2+12Z)=(1+3Z,1+4Z)

となる。

S(1+12Z)=(1+3Z,1+4Z)であり、Sは単射なので、a2+12Z=1+12Zである。

したがって、a2112の倍数となることがわかる。

また、命題7を使うと、以下のように書けます(命題3と同じ)。

(Z/12Z)×(Z/3Z)××(Z/4Z)×Z/2Z×Z/2Z

命題1の証明③を長々と書いてしまいましたが、前に引用した文章

代数学では, 集合の材質, 色彩, 要素の大きさなど物理的な意味には一切関知しないで, 単に元(構成要素)の間の演算にだけ関心を限定している.したがって群が同型であるとは, 群という数学的概念のカテゴリーでは「同一である」とみなしてよいということを主張しているのである.(足立恒雄「ガロア理論講義」pp.31-32)

を念頭に置きつつ、少しお気持ちを書いておきます。

(Z/12Z)×(Z/3Z)××(Z/4Z)×は同型なので、「群という数学的概念のカテゴリーでは『同一である』とみなしてよい」(上記引用文より抜粋)ということになります。

(Z/3Z)××(Z/4Z)×は位数2の巡回群の直積なので、命題6の系から「どんな元をとってきても、2乗したら単位元」ということがわかります。

群として「同一である」とみなすと、(Z/12Z)×も、「どんな元をとってきても、2乗したら単位元」という性質を持っていることがわかるので、12と互いに素な整数aについて、a21(mod12)となることが見えてきます。

24の倍数であること、さらに一般化してみる

24の倍数

24についても同様に

(Z/24Z)×(Z/3Z)××(Z/8Z)×

となるので、(Z/8Z)×の構造を調べることで、同じことができます。

結論だけ書くと

(Z/8Z)×≅<1+8Z>×<5+8Z>

であり、<1+8Z>,<5+8Z>は位数2の巡回群となっているので、(Z/3Z)×も位数2の巡回群だったことを合わせれば

(Z/24Z)×(Z/3Z)××(Z/8Z)×Z/2Z×Z/2Z×Z/2Z

となり、24のケースでも位数2の巡回群の直積で表せます。

a24と互いに素な整数(つまり、a3と互いに素であり、2と互いに素な整数)とすれば、12の場合と同様にして、a2124の倍数となることがわかります。

一般化(32nの倍数)

(Z/32nZ)×について以下が成り立ちます。

n=1のとき

(Z/6Z)×(Z/3Z)××(Z/2Z)×Z/2Z

n=2のとき

(Z/12Z)×(Z/3Z)××(Z/4Z)×Z/2Z×Z/2Z

n3以上の整数のとき

(Z/32nZ)×(Z/3Z)××(Z/2nZ)×Z/2Z×Z/2Z×Z/2n2Z

※参考: (Z/nZ)*の群構造(INTEGERS)

例えば、n=4とすれば

(Z/48Z)×(Z/3Z)××(Z/24Z)×Z/2Z×Z/2Z×Z/22Z

となります。

a48と互いに素な整数(つまり、a3と互いに素であり、2と互いに素な整数)とすれば、a4148の倍数となることがわかります。
Z/2Z×Z/2Z×Z/22Zから「どんな元をとってきても、4乗したら単位元」ということが見えてきます)

同様に、n=5とすると、a96と互いに素な整数(つまり、a3と互いに素であり、2と互いに素な整数)とすれば、a8196の倍数となることがわかります。

このように考えていくと、以下が成り立つことがわかります。

a3と互いに素であり、2と互いに素な整数とし、n3以上の整数とする。このとき、a2n2132nの倍数となる。

感想など

序盤に書いた証明のポイント

12を(互いに素な)34に分けて考える。
mod3でもmod4でも「a±1と合同」「a2乗すると1と合同」という似た性質が出てくる。

ですが、①は

(Z/12Z)×(Z/3Z)××(Z/4Z)×

という見方につながり

②は、(Z/3Z)×(Z/4Z)×が位数2の巡回群であり、いずれも

(Z/3Z)×=<1+3Z>
(Z/4Z)×=<1+4Z>

と表せることにつながってくると思います。

また、オイラーの定理を使った証明では、(Z/3Z)×の位数ϕ(3)(Z/4Z)×の位数ϕ(4)が現れています。

私自身、最初は元の問題を「面白い数遊び」のようにとらえていましたが、代数系の知識や言葉で見てみると、その構造が見えてきて、一層の面白味を感じられるようになってきました。

今回は(Z/nZ)×の構造を考える上で、かなり限定的なシチュエーションのみを扱ってきましたが、より一般の場合については以下の記事が参考になると思います。

(Z/nZ)*の群構造(INTEGERS)

Z/nZの単元群の構造の話(ぱいおつ日記)

最後に、 日曜数学 Advent Calendar 2022 のページに

レベルは問いませんが、面白さを読者が共感できるように「自分はなぜそのトピックを面白いと思ったのか」を熱く書いてもらえると嬉しいです。

と記載されていたので、ちょっとだけ書いておきます。

受験生のとき、「もう勉強つらい」「整数問題、解けない」と思いながら解き始めたのが「マスター・オブ・整数」という参考書でした。

面白くて、受験勉強であることを忘れながら解いた思い出があります。

そして、大学での代数学の授業で、Z/nZなどの話を知り「あのときの整数問題は、こんな話につながっていたのか!」と嬉しくなりました。

そのときの「面白かった!」「もっと知りたい!」という感覚は、何年も経った今でもずっと続いていると感じますし、今回のテーマで記事を書こうと思った原動力にもなっていると思います。

最初は「受験勉強のため」と思ってやり始めたことが、こんなに続くというのは、自分でもちょっと不思議です。「自分の好きなこと」との出会いは意外なところからやってくるのかもしれません。

※余談ですが、この記事を書きながら「私は雰囲気で代数学をやってきたんだな…」と改めて気づき、基礎がガタガタなことを反省しました。

参考文献

投稿日:2022127
更新日:20231214
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

みぽ
みぽ
161
32129
今日もねこがかわいい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. Introduction
  2. まずは初等的に解いてみる
  3. 数論におけるオイラーの定理を使って証明してみる
  4. $(\mathbb{Z}/12\mathbb{Z})^{\times}$の構造を考えてみる
  5. $\mathbb{Z}/n\mathbb{Z}$$(\mathbb{Z}/n\mathbb{Z})^{\times}$について
  6. 巡回群について
  7. 準同型写像や同型について
  8. 直積について
  9. $\mathbb{Z}/mn\mathbb{Z}$$(\mathbb{Z}/mn\mathbb{Z})^{\times}$の構造
  10. 3つ目の証明へ
  11. 24の倍数であること、さらに一般化してみる
  12. 24の倍数
  13. 一般化($3\cdot 2^{n}$の倍数)
  14. 感想など
  15. 参考文献