NTMRの数学メモ

数学について調べたことを書きます。高校数学に毛が生えた内容。

第一同型定理の証明と第二、第三同型定理の紹介

 過去の記事で、後日改めて同型定理についてまとめると言いつつ放置していましたが、時間的に余裕ができたので整理しました。なお、各同型定理は本来、複数の主張を含んでいますが、独断で一部の主張だけ紹介します。

 まず、第一同型定理は次のような主張になります。

f:id:Natsu1014_brog:20210415110745p:plain

 第二、第三同型定理は紹介までに留めますが、これは証明します。ただし、なるべく定義から証明するようにはしていますが、部分群であるための必要十分条件準同型写像単射であるための必要十分条件など証明せず使うところもあります。

 そもそも  G/Ker( \phi ) Im( \phi ) が群でないといけないので、このことを証明します。

f:id:Natsu1014_brog:20210415113042p:plain

 最後に、これらが同型であること、すなわち  G/Ker( \phi ) から  Im( \phi ) への同型写像が存在することを証明します。

f:id:Natsu1014_brog:20210415113307p:plain

 一応参考書を読みながらではありますが、代数学の証明を書くのはほぼ初めてなので、もしかすると間違えているところもあるかもしれません。ご容赦ください。
 第一同型定理の主張を日本語で書くと「 G から  H への写像が存在して、 G をその写像の核で割ったものはその写像の像と同型である」となります。

 

 続いて、第二同型定理と第三同型定理の紹介をします。

f:id:Natsu1014_brog:20210415113556p:plain

 これらは、第一同型定理をうまく使うことで証明できるみたいです。

 第二同型定理は  (HN)/N は「部分群  H の元と 正規部分群  N の元の積全体を  N で割ったもの」であり、 H/(H \cap N) は「部分群  H H正規部分群  N の共通部分で割ったもの」であり、これらが同型であるということを言っています。
 一応補足すると、 HN H N を含む群になります。恐らくイメージ的には、 H \cap N による  H の割り方を  H \cap N N H HN へと拡大した感じになるのだと思います。

 次に第三同型定理は  G N, \, N' の両方で割れるわけですが、 G/N N' のスケールで分割(表現が難しい…)すると  G/N' に一致する感じだと思います。形式上、なんだか分数みたいで面白いですね。

 一般的に準同型定理と呼ばれるのは第一同型定理のようですが、どうして同型定理は3つ存在するのか考えてみて、群の2つの部分群の包含関係によって3つに分けられているのではないかと思いました。第一は共通部分が空集合、第二は共通部分があるが一方が他方を含まない、第三は一方が他方を含む。それで、それぞれ正規部分群が不要、少なくとも一方、両方のとき、同型な2つの群を見つけることができる、という感じかなと思いました。素人の考えなので、まったく的外れかもしれませんが…。

 今回はこの辺りで。ではまた。

オイラー関数についての不等式

 以前からオイラー関数  \phi(n) を何回反復させれば初めて  1 になるのか興味がありました。特に明確な同機があるわけではないのですが、恐らく約一年前に書いた下の記事の内容がそれとやや関係しているからだったかもしれません。(関係ないですが、しばらく前に書いた記事って今とテンションが違くて恥ずかしいですね。)

natsu1014-brog.hatenablog.com

 まあ、動機は何でもいいです。このことに関して何度か調べても、なかなかオイラー関数の反復について書いているサイトが見つからなかったのですが、今回考察して大分進捗があったのでまとめようと思います。

 まず、今回使った関数の定義(といっても大層なものではありませんが)から説明します。1つ目は  \phi ^k(n) で、これはオイラー関数を  k 回反復させたものを表します。再帰的に定義するなら  \phi ^0(n), \, \phi ^{k+1}(n)=  \phi ( \phi ^k (n)) となるでしょう。

 2つ目は  \chi (n) で、これは  \phi ^k(n)=1 となるような最小の  k を表します。 n \geq 2 の場合は  \phi ^{k-1}(n)=2 となる  k とも言い換えられるでしょう。このときは  n=1 の場合  \chi (n) =0 と個別で定義することになります。
 さて、興味があるのは  \chi (n) がどのような範囲にあるのかということで、結論としては  \log_2 (1+ \log_2 n) \leq \chi (n) \lt 1+ \log_2 n が考察で得られました。

 

 証明は定理1から7に分けて行いました。結論は上からの評価が定理4、下からの評価が定理7で、定理1~3、5~6はそれぞれを証明するための準備です(補題とするべきだったでしょうか)。

f:id:Natsu1014_brog:20210406025138p:plain

 さて、さっそく証明していきます。

f:id:Natsu1014_brog:20210406025232p:plain

f:id:Natsu1014_brog:20210406025243p:plain

  \phi (n) = \frac{n}{ {\rm rad}(n) } \phi ({\rm rad}(n)) については下の記事を参考にしてください。飽くまで  \phi (n) =n(1- \frac{1}{p_1})(1- \frac{1}{p_2}) \cdots (1- \frac{1}{p_m}) の言い換えです。

natsu1014-brog.hatenablog.comf:id:Natsu1014_brog:20210406025827p:plain

 最後の不等号に  = がついていないのは  \phi (n) \gt 3 だからです。この不等式は完全に自力で求めたので、あっているか少し心配ではあります。 \phi (n) 自体のときは定理1のようにまったく抑え込めないのですが、 \phi ^2(n) 以降になると  \phi (n) が正偶数であることから抑え込めるようになるのがポイントです。
 さて、ここまでの結果から  \chi (n) の上からの評価が可能になります。

f:id:Natsu1014_brog:20210406030626p:plain

 次は下からの評価を証明していきます。

f:id:Natsu1014_brog:20210406030711p:plain

 これは証明は兎も角、不等式自体はWikipediaに書いていました(オイラーのφ関数 - Wikipedia)。ただ「簡明な下界」と書いてあり、かなり緩い評価ではあるようです。

f:id:Natsu1014_brog:20210406030715p:plain

 この結果から  \chi (n) の下からの評価が証明できます。

f:id:Natsu1014_brog:20210406031037p:plain

 以上から   \log_2 (1+ \log_2 n) \leq \chi (n) \lt 1+ \log_2 n という結果が得られました。ただ、上からの評価はそこそこ良さそうですが、下からの評価がかなり緩いようです。もっときつくて、かつ扱いやすい  \phi (n) の下からの評価があればよいのですが…。唯一この評価の良い点を挙げるとすれば、上下の評価に  1+ \log_2 n が含まれていて見栄えが良いというところでしょうか。
 少なくとも約一年前の記事に関わるのは上からの評価だけなので、とりあえずは満足です。もっとよい下からの評価があれば、また書こうと思います。
 ではまた。

積で割った余りを合同式で求める。

 高校時代は合同式と相加平均・相乗平均の大小関係が大好きでした。
 それで、高校で普通合同式を使わずに解く問題も合同式を解きたいと思いました。そのために、一般的でない合同式の公式を証明します。

 まずは合同式の定義と一般的な公式の証明をします。

f:id:Natsu1014_brog:20210404121850p:plain

 ここからは  (3),(4) の別バージョンとして  (6),(7) を証明します。

f:id:Natsu1014_brog:20210404121955p:plain

 さて、今回使うのは  (7) だけを使います。

 解きたい問題は「 p,q を互いに素な自然数としたとき,  p で割ると  r 余り,  q で割ると  s 余るとき,  n pq で割った余りを求めよ.]という問題です。 
 まず一般的な方法で解きます。

  n はある整数  k,l が存在して
  n=pk+r, \, n=ql+s

と表される.
このとき  pk+r=ql+s であるから  pk-ql=s-r.
  p q は互いに素であるから, ユークリッド互除法により
  pk' -ql' =1
を満たす組  (k' ,l' )=(k_0,l_0) が求まる.
したがって  p(s-r)k_0-q(s-r)l_0=s-r であるから
  p [ k-(s-r)k_0  ]=q [ l-(s-r)l_0 ] .
  p q は互いに素,  k-(s-r)k_0,l-(s-r)l_0 は整数より,  k-(s-r)k_0 q の倍数である.
よって, ある整数  m が存在して  k-(s-r)k_0=qm \, \therefore k=qm+(s-r)k_0.
このとき,  l=pm+(s-r)l_0.
したがって,  n_0=p(s-r)k_0+r=q(s-r)l_0+s とおくと  n=pqm+n_0 ( m は整数) より  n pq で割った余りは  n_0 pq で割った余りに等しい.

  次に合同式を使った場合です。

  n ≡ r \, ({\rm mod}p) より  qn ≡ qr \, ({\rm mod}pq).
  n ≡ s \, ({\rm mod}q) より  pn ≡ ps \, ({\rm mod}pq).
  p q は互いに素であるから, ユークリッド互除法により
  pk' -ql' =1
を満たす組  (k' ,l' )=(k_0,l_0) が求まる.
したがって  n ≡ (pk_0-pl_0)n ≡ psk_0-qrl_0 \, ({\rm mod}pq).
すなわち  n pq で割った余りは  psk_0-qrl_0 pq で割った余りに等しい.

   n_0=psk_0-qrl_0 となることは簡単に分かります。また、合同式を使った解法だと、本質的には同じですがユークリッド互除法を使わずにゴリ押せます。例題を解いてみましょう。

 [問]  19,11 で割るとそれぞれ  7,5 余る自然数 209 で割った余りを求めよ.
 [答]
  n 19,11 で割るとそれぞれ  7,5 余る自然数とすると,
  n ≡ 7 \, ({\rm mod}19) \, \therefore 11n ≡ 77 \, ({\rm mod}209) \cdots
  n ≡ 5 \, ({\rm mod}11) \, \therefore 19n ≡ 95 \, ({\rm mod}209) \cdots
 ②-① より

  8n ≡ 19n-11n ≡ 95-77 ≡ 18 \, ({\rm mod}209) \, \therefore  8n ≡18 \, ({\rm mod}209) \cdots
 ①-③ より

  3n ≡ 11n-8n ≡77-18≡59 \, ({\rm mod}209) \, \therefore 3n ≡ 59 \, ({\rm mod}209) \cdots

 ④×3-③ より
  n ≡ 3n \times 3 -8n ≡ 59 \times 3 - 18 ≡ 159 \, ({\rm mod}209)
したがって,  n 209 で割った余りは 159 である.

  2 つの合同式から  n ≡ \cdots の式を求めるまでは多少面倒ですが、ユークリッド互除法から式変形するよりはずっと楽ですし、うまくやれば短くできそうです。もしかしたら選んだ整数によっては面倒になるかもしれませんが、そのときは別の方法で。少なくとも以前求めた行列を使った方法をやれば、簡単に求まるはずです。

第一同型定理までの要点まとめ

 「代数学群論入門」の第二章を読み終わり、理解の怪しいところもありますが、とりあえず忘れる前に概要を整理したいと思います。

 


 群というのはある条件を満たした、集合 GG 上で定義される演算 \cdot のペア(G, \cdot ) のことで、ある条件とは結合法則②逆元の存在③単位元の存在の3つです。集合における部分集合のように、群においては部分群が定義できます。

  =, \leq, \subset のような集合の 2 つの元に対して定義される関係(関係の定義は省略)のうち、①反射律②対称律③推移律を満たすものを同値関係といいます。 \sim を集合  A 上で定義される同値関係としたとき、 x \in A に対して  C(x)= \{ x \in A \vert x \sim  y \} x同値類といいます。 A の部分集合で  x \in A に対して  C(x) と表されるもの全体の集合を  A \sim による商といい  A / \sim と書きます。
  \sim を特に、 G を群、 H G の部分群として、 x,y \in G  に対して  x^{-1}y \in H ならば  x \sim y と定義したとき、 x \in G の同値類を  x H による左剰余類と呼び  xH と書きます。また、 G のこの同値関係による商を  G / H と書きます。同様に、 yx^{-1} \in H ならば  x \sim y と定義した場合には  x \in G の同値類を  x H による右剰余類と呼び  Hx と書き、また、 G のこの同値関係による商を  H \backslash G と書きます。

  H を群  G の部分群として、任意の  g \in G, h \in H に対して  ghg^{-1} \in H のとき  H G正規部分群といいます。 N G正規部分群であるとき、任意の  g \in G に対して  gN=Ng となります。また、 G/N 上の演算を  g_1,g_2\in G に対して  (g_1N)(g_2N)=g_1g_2N と定義すると  G/N はこの演算に関して群となります。

  G,H を群として写像 \phi : \, G \to H が、任意の  g_1,g_2 \in G に対して   \phi (g_1g_2)= \phi (g_1) \phi (g_2) となるとき  \phi準同型写像といいます。この準同型写像の逆写像準同型写像のとき  \phi同型写像といい、同型写像  \phi: \, G \to H が存在するならば  G H同型であるといいます。準同型写像  \phi全単射であるとき  \phi は同型写像となります。
  G,H を群とすると、準同型 \phi : \, G \to H に対して  {\rm Ker}( \phi )= \{ g \in G \vert \phi (g)=1_G \}  \phi の核といい、 { \rm Im}(\phi)= \{ \phi (g) \vert g \in G \} \phi の像といいます。 {\rm Ker}( \phi ) G正規部分群 {\rm Im}( \phi ) H の部分群となります。したがって  G/{\rm Ker}( \phi ) は群となります。
 写像 \pi: \, G \to G/{\rm Ker}( \phi ) x \in G に対して  \pi (x)=x{\rm Ker}( \phi ) と定義すると、同型 \psi: G/{\rm Ker}( \phi ) \to {\rm Im}( \phi ) が存在して  G/{\rm Ker}( \phi ) {\rm Im}( \phi ) と同型となります(第一同型定理)。特に  \phi全射のとき  H={\rm Im}(\phi) であるから  G/{\rm Ker}( \phi ) H が同型となります。 

 

 

 後で自分でサッと思い出すために書いたので、詳細や証明は省きました。準同型定理については第一同型定理から第三同型定理まであるので、第二と第三は後日まとめます。以下、いくつか補足をします。

   H が群  G の部分群であることを  H \leq G と書き、特に正規部分群のとき  H \triangleleft G と書きます。また、群  G,H が同型であることを  G \cong H と書きます。

  H を群  G の部分群とすると  \vert G/H \vert = \vert H \backslash G \vert であり、これを  ( G:H ) と書きます。このとき  \vert G \vert = (G:H) \vert H \vert となります(ラグランジュの定理)。


 以上です。ここからは作用というものが登場して、前回学習をしたときはこの辺りから分からなくなり始めたので、多分次まではしばらく期間が開くと思います。
 ただ、演算が集合  A に対する写像 \phi : \, A \times A \to A であるのに対して、(左)作用は群  G と集合  A に対する写像 \psi : \, G \times X \to X であることを考えると、どこで挫折したのか。ベクトルにおけるベクトル加法とスカラー積の違いみたいなものですよね、多分。もしこの段階で混乱していたのだとすれば、案外すんなり理解できるかも?とりあえず次はシローの定理を目標に読み進めます。春休みももう終わるので、次いつ読めるか分かりませんが…。ではまた。

部分群であるための必要十分条件

 しばらく放置してたら完全に忘れてしまった群論入門。0から読み直してるので、知識を整理するために時々まとめていこうかなーと思います。自分の復習用なので、不正確なところがあってもご容赦ください(今回に限らないが)。
 まず、群の定義をまとめます。ついでに環・体の定義も書いておきます。

f:id:Natsu1014_brog:20210401011351p:plain

 まあ、環・体は定義を知っておくだけで、そこまでする予定は今のところないのでいいです。続いて、部分群についてまとめて終わりにします。

f:id:Natsu1014_brog:20210401011540p:plain

 参考にしたのは「代数学群論入門」で、依然読んだときは第4章で挫折したしまったので、どこまで復習できるか…。とりあえず準同型定理まで復習したいな~と思います。ではまた。

一次不定方程式と行列

 自然数  m,n に対して不定方程式  mx+ny={\rm gcd}(m,n) の整数解  (x,y) の1つを、行列を用いて求める方法について考えます。

 前半は高校数学で扱うように、ユークリッド互除法を用います。

【前半】

  r_0=m,r_1=n とおくと, ある非負整数  r_2,r_3, \cdots ,r_n, q_1,q_2, \cdots , q_{n-1} が存在して,
  r_0=r_1q_1+r_2 \hspace{5pt} (0 \lt r_2 \lt r_1)

  r_1=r_2q_2+r_3 \hspace{5pt} (0 \lt r_3 \lt r_2)
  \hspace{15pt} \vdots
  r_{n-2}=r_{n-1}q_{n-1}+r_n \hspace{5pt} (0 \lt r_n \lt r_{n-1})
が成り立つ.

 

すなわち, 整数 k \, (2 \leq k \leq n) に対して
  r_{k-2}=r_{k-1}q_{k-1}+r_k
より

  r_k=r_{k-2}-r_{k-1}q_{k-1}
であるから,  x_k,y_k を整数とすると,

  r_{k-1}x_k+r_ky_k \\ = r_{k-1}x_k+(r_{k-2}-r_{k-1}q_{k-1})y_k \\ = r_{k-2}y_k +r_{k-1}(x_k-q_{k-1}y_k)
が成り立つ.

 

ここで
  x_{k-1}=y_k \\ y_{k-1}=x_k-q_{k-1}y_k
とおくと  x_{k-1},y_{k-1} は整数で,
  r_{k-2}x_{k-1}+r_{k-1}y_{k-1}=r_{k-1}x_k+r_ky_k
が成り立つ.

よって  x_n=0, y_n=1 とすると,
  r_0x_1+r_1y_1 = r_1x_2+r_2y_2 = \cdots = r_{n-1}x_n+r_ny_n=r_n
となり, 特に  r_n={\rm gcd}(r_0,r_1) のとき

  r_0x_1+r_1y_1={\rm gcd}(r_0,r_1) \hspace{5pt} \therefore mx_1+ny_1={\rm gcd}(m,n)
が成り立つので  (x,y)=(x_1,y_1)不定方程式  mx+ny={\rm gcd}(m,n) の整数解の1つ である.

   さて、後半ではようやく行列を使います。

【後半】
整数  k \, (2 \leq k \leq n) に対して
   x_{k-1}=y_k \\ y_{k-1}=x_k-q_{k-1}y_k
より,
  \left( \begin{array}{c} x_{k-1} \\ y_{k-1} \end {array} \right) = \begin{pmatrix} 0 & 1 \\ 1 & -q_{k-1} \end{pmatrix} \left( \begin{array}{c} x_k \\ y_k \end {array} \right)
したがって,
  \left( \begin{array}{c} x_1 \\ y_1 \end {array} \right) \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \left( \begin{array}{c} x_2 \\ y_2 \end {array} \right) \\ = \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \left( \begin{array}{c} x_3 \\ y_3 \end {array} \right) \\ \hspace{15pt} \vdots \\ =  \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -q_{n-1} \end{pmatrix}\left( \begin{array}{c} x_n \\ y_n \end {array} \right) \\ =  \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -q_{n-1} \end{pmatrix}\left( \begin{array}{c} 0 \\ 1 \end {array} \right)

 具体例で試してみましょう。

  19=11 \cdot 1+8 \\ 11=8 \cdot 1+3 \\ 8=3 \cdot 2+2 \\3=2 \cdot 1+1
であり,
  \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \left( \begin{array}{c} 0 \\1 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \left( \begin{array}{c} 1 \\-1 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix} \left( \begin{array}{c} -1\\3 \end{array} \right) \\ = \begin{pmatrix} 0&1 \\ 1&-1 \end{pmatrix}  \left( \begin{array}{c} 3\\-4 \end{array} \right) \\ = \left( \begin{array}{c} -4\\7 \end{array} \right)
ここで  19 \cdot (-4) + 11 \cdot 7 =1 であるから, (x,y)=(-4,7)不定方程式  19x+11y=1 の解の1つである.

[補足(2021/03/31)]  3=2 \cdot 1+1 の後、 2=1 \cdot 2+0 まで計算しないと気持ち悪い!という場合は  \left( \begin{array}{c} 0 \\ 1 \end{array} \right)  \begin{pmatrix} 0&1 \\ 1&-2 \end{pmatrix} \left( \begin{array}{c} 1 \\ 0 \end{array} \right) に置き換えれば良さそうです。

オイラーのφ関数の公式

 オイラー関数の公式を証明したことなかったなと思ったので、証明します。多分あってると思うけど、間違ってたらすみません。

f:id:Natsu1014_brog:20210325001437p:plain

 これは次のように証明します。

f:id:Natsu1014_brog:20210325001538p:plain

 残りは簡単です。

f:id:Natsu1014_brog:20210325001621p:plain

 これは次のように証明します。

f:id:Natsu1014_brog:20210325001641p:plain

 これらを合わせると次のことが分かります。簡単なので証明は省略します。

f:id:Natsu1014_brog:20210325001713p:plain

 これで終わりですが、蛇足程度に  \phi (n) {\rm ABC} 予想で登場する  {\rm rad} (n) を使うと次のように表すこともできます(nは上記の n です)。証明は省略します。

f:id:Natsu1014_brog:20210325002008p:plain

 この表現自体はどうでもいいのですが、右辺の  \phi ( {\rm rad} (n)) は具体的に

   \phi ( {\rm rad} (n)) = (p_1-1)(p_2-1)(p_3-1) \cdots (p_k-1)

となりますね。それだけです。ではまた。