2021-09-12

統計的な推測（数B）の備忘録

統計学

　数Bといえばベクトルと数例ですが、一応「確率分布と統計的な推測」という単元もあります。高校では習わず独学で勉強しましたが、何しろ問題を解く機会がない（手元の問題集にも載っていないものが多い）ため、すぐ忘れてしまいます。そのため、備忘録として一部の内容をまとめました。（教科書読んだ方が速いかもしれませんが…）

　数学Bで習う確率分布には二項分布 $B(n,p)$ と正規分布 $N(m, \sigma ^2)$ があります。それらの違いを簡単に下にまとめると、次のようになります。

f:id:Natsu1014_brog:20210912131606p:plain

　また、二項分布 $B(n,p)$ は「ある試行 $T$ を行って事象 $A$ が起きる確率が $p$ であるとき、試行 $T$ を $n$ 回行って事象 $A$ が起きた回数」を $X$ としたとき、 $X$ が従う確率分布となります。

　両者には重要な関係があり、 $n$ が十分大きいとき二項分布 $B(n,p)$ は正規分布 $N(np, np(1-p))$ に近似できます。 $np$ 、 $np(1-p)$ というのはそれぞれ二項分布 $B(n,p)$ に従う確率変数の期待値と分散です（証明略）。

　さて、母集団から１つの個体を無作為に抽出し、その変量（個体がもつ特性を表す数量）の値を $X$ とすると、これは確率変数となります。そして、 $X$ が従う確率分布を母集団分布といい、期待値 $m$ を母平均、標準偏差 $\sigma$ を母標準偏差といいます。さらに、複数の個体を無作為に抽出し、それらの変量の平均を $\overline{X}$ とすると、これも確率変数となり、期待値は母平均 $m$ と一致し、標準偏差は母標準偏差を標本の大きさ $\underline{n}$ の平方根で割ったもの $\frac{\sigma}{\sqrt{n}}$ となります。そして、母集団分布が正規分布に従うならば標本平均も正規分布に従いますが、母集団分布が正規分布に従わないとしても標本の大きさが十分に大きければ近似的に正規分布 $N(m, \frac{\sigma ^2}{n})$ に従います。

　一方、母集団におけるある特性 $A$ をもつ個体の割合 $p$ を母比率といい、抽出された標本における特性 $A$ をもつ個体の割合 $R$ を標本比率といいます。そして、標本比率 $R$ は確率変数となり、標本の大きさが十分に大きいとき近似的に正規分布 $N(p,\frac{p(1-p)}{n})$ に従います。これは「母集団から $n$ 個の個体を無作為に抽出して、それらのうち特性 $A$ をもつものの個数」を $X$ と定義した時、 $X$ は二項分布 $B(n,p)$ に従うことから分かります。

　標本平均と標本分布について特徴をまとめると下の表のようになります。

f:id:Natsu1014_brog:20210912131706p:plain

　いずれもある確率変数 $X_k \, (k=1,2,3, \cdots ,n)$ が存在して $\overline X($ または $R)=\frac{1}{n} (X_1+X_2+ \cdots +X_n)$ と定義されますが、 $X_k$ が標本平均の場合は複数の値をとるのに対し、標本比率の場合は１か０の値しかとらないのが本質的な違いだと思います。この違いにより $m$ は $p$ に、 $\sigma$ は $p(1-p)$ に変化していると解釈できます。

　さて、正規分布に従う確率変数の確率は計算することが出来ません。そこで、期待値０、標準偏差１の正規分布である標準正規分布 $N(0,1)$ に従う確率変数 $X$ に対して、 $P(0 \leq X \leq a)$ の値が複数の $a$ に対してまとめられた表が存在します。また、確率変数 $X$ がいかなる正規分布 $N(m,\sigma^2)$ に従っているとしても、 $Z=\frac{X-m}{\sigma}$ とおくと確率変数 $Z$ は標準正規分布 $N(0,1)$ に従います（ $Z$ を $X$ の標準化変数といいます）。

　そして、その表によると $P(0 \leq Z \leq a)=0.475$ となる $a$ の値はおよそ1.96と分かります。つまり、95%の確率で $-1.96 \leq Z \leq 1.96$ という不等式が成り立ちます。 $Z=\frac{x-m}{\sigma}$ であったので、これを代入して整理すると95%の確率で $X-1.96\sigma \leq m \leq X+1.96 \sigma$ が成り立つと言えます。

　この不等式を標本平均 $\overline{X}$ （近似的に正規分布 $N(m, \frac{\sigma^2}{n})$ に従う）、標本比率 $R$ （近似的に正規分布 $N(p, \frac{p(1-p)}{n})$ に従う）について立てると、

　標本比率：　 $\overline{X}-1.96 \frac{\sigma}{\sqrt{n}} \leq m \leq \overline{X}+1.96\frac{\sigma}{\sqrt{n}}$

　標本平均：　 $R-1.96\sqrt{\frac{p(1-p)}{n}} \leq p \leq R+1.96\sqrt{\frac{p(1-p)}{n}}$

という不等式が95%の確率で成り立つと言えます。

　これらの不等式は、それぞれ母平均、母比率を推定するのに役立ちます。たとえば、標本平均 $\overline{X}$ について母標準偏差 $\sigma$ が分かっていれば、母平均 $m$ は95%の確率で $[ \overline{X}-1.96 \frac{\sigma}{\sqrt{n}}, \overline{X}+1.96\frac{\sigma}{\sqrt{n}} ]$ の範囲に含まれていることが分かります。このような範囲のことを信頼度95%の信頼区間といいます。しかし、母標準偏差 $\sigma$ が分かっていなければ標本の標準偏差 $S$ で代用することもできます。母比率を推定したいときも同様に、母比率 $p$ は標本比率 $R$ で代用します（そうでないと、母比率の信頼度95%の信頼区間に母比率が含まれてしまい役に立ちません…）。したがって、標本比率 $R$ について母比率の信頼度95%の信頼区間は $[ R-1.96 \sqrt{\frac{R(1-R)}{n}} , R+1.96\sqrt{\frac{R(1-R)}{n}} ]$ となります。

　以上です。センター試験では選択問題に存在しているのを見たことがありますが、それ以上の難易度の問題って存在するんですかね。一応、「大学の統計学」という本を途中まで読んで興味を持っているので、コロナが落ち着いたころに統計検定など受けたいなと思ったり思わなかったり。ではでは。

2021-04-15

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

その他

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

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

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

　一応参考書を読みながらではありますが、代数学の証明を書くのはほぼ初めてなので、もしかすると間違えているところもあるかもしれません。ご容赦ください。
　第一同型定理の主張を日本語で書くと「 $Ｇ$ から $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'$ に一致する感じだと思います。形式上、なんだか分数みたいで面白いですね。

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

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

2021-04-06

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

場合の数・確率・整数・数列

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

natsu1014-brog.hatenablog.com

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

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

　２つ目は $\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$ が考察で得られました。

　証明は定理１から７に分けて行いました。結論は上からの評価が定理４、下からの評価が定理７で、定理１～３、５～６はそれぞれを証明するための準備です（補題とするべきだったでしょうか）。

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.com f:id:Natsu1014_brog:20210406025827p:plain

　最後の不等号に $=$ がついていないのは $\phi (n) \gt 3$ だからです。この不等式は完全に自力で求めたので、あっているか少し心配ではあります。 $\phi (n)$ 自体のときは定理１のようにまったく抑え込めないのですが、 $\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$ が含まれていて見栄えが良いというところでしょうか。
　少なくとも約一年前の記事に関わるのは上からの評価だけなので、とりあえずは満足です。もっとよい下からの評価があれば、また書こうと思います。
　ではまた。

2021-04-04

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

場合の数・確率・整数・数列

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

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

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$ の式を求めるまでは多少面倒ですが、ユークリッド互除法から式変形するよりはずっと楽ですし、うまくやれば短くできそうです。もしかしたら選んだ整数によっては面倒になるかもしれませんが、そのときは別の方法で。少なくとも以前求めた行列を使った方法をやれば、簡単に求まるはずです。

2021-04-03

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

その他

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

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

　 $=, \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$ であることを考えると、どこで挫折したのか。ベクトルにおけるベクトル加法とスカラー積の違いみたいなものですよね、多分。もしこの段階で混乱していたのだとすれば、案外すんなり理解できるかも？とりあえず次はシローの定理を目標に読み進めます。春休みももう終わるので、次いつ読めるか分かりませんが…。ではまた。

2021-04-01

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

その他

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

f:id:Natsu1014_brog:20210401011351p:plain

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

f:id:Natsu1014_brog:20210401011540p:plain

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

2021-03-31

一次不定方程式と行列

図形・ベクトル・線形代数

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

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

【前半】
$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)$ の整数解の１つである.

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

【後半】
整数 $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$ の解の１つである.

[補足(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)$ に置き換えれば良さそうです。