2017-03-22

ユークリッドの互除法について

数学

$a,b$ の最大公約数を ${\rm gcd}(a,b)$ と表す．

定理．（ユークリッドの互除法）
$a, b(a \geq b)$ を整数として， $a$ を $b$ で割った余りを $r$ とする．
このとき， ${\rm gcd}(a,b)={\rm gcd}(b,r)$ ．

教科書の証明はなんだか文章ばかりで難しかった覚えがある．
今ならできるだろうか…？

（証明）
$a$ を $b$ で割った商を $q$ とすると $a=bq+r$ と表せる．
右辺をみると $b,r$ の公約数は $a$ の約数となっており，
$a,b$ の公約数になっていることがわかる．
また $r=a-bq$ と変形すると $a,b$ の公約数は $r$ の約数となっており，
$b,r$ の公約数になっていることがわかる．
つまり $a,b$ の公約数の集合と $b,r$ の公約数の集合は等しいので，
最大公約数は等しい．（証明終）

あっさり解決できた．少しくらいは簡単な整数論が身についているようだ．
このユークリッドの互除法は使いかたが問題である．

例えば $73, 17$ の最大公約数を求める場合は，「どんどんスライドさせて割っていく」のである．
$73=17 \times 4 + 5$ （割り算の原理）
$17=5 \times 3 + 2$ （割る数と余りで割り算する．以下繰り返す．）
$5=2 \times 2 + 1$
$2=2 \times 1$ （割り切れたら終了）
よって最大公約数は $1$ である．

ひとまずユークリッドの互除法の使いかたはいいだろう．
ところで上の証明を見ると，結局は次の問題に帰着される．

問．
${\rm gcd}(a,b)={\rm gcd}(a-b,b)$ を示せ．

証明は $a=(a-b)+b$ とすれば，上の証明となんら変わらない議論で示せる．
これがいわゆる，ユークリッドの互除法の原理と呼ばれるものである．

2017-03-04

二次形式って何ですか？

日記

正直に告白すると、二次形式というものを勉強したことがない。
使ったことが全くない。

Wikipediaによれば、二次形式は多方面で中心的な地位を占めるもののようだ…。
全く知らない。

いままで中心を回避して勉強していたということなのだろうか。
まるで複素積分のようである。

2017-01-28

カップル成立の確率

数学

安田亨先生の伝説の良問100を読んでいたら，次の問題があった。

問．
男性が2人，女性が2人いる。各々は自分の異性をでたらめに1人指名する。
互いに相手を指名すればカップルが成立するものとして，
ちょうど1組カップルが成立する確率を求めよ。

n人まで一般化する方法も書いてあり，包除原理で計算している。

2017-01-14

微分と積分の交換可能の条件

数学解析学ルベーグ積分

ルベーグの優収束定理を用いて，微分と積分の交換可能の条件を求める．

定理
$\mathbb{R}^2$ 上の関数 $f$ が次の条件を満たすとする．
1) 各 $x$ に対して $f(x,y)$ は $y$ で積分可能である．
2) $\displaystyle \frac{\partial f}{\partial x}$ は存在し，ある1変数関数 $g \in L^1$ で $\displaystyle |\frac{\partial f}{\partial x}(x,y)| \leq g(y)$ となるものが存在する．
このとき $\displaystyle \frac{\partial}{\partial x} \int_\mathbb{R} f(x,y)dm(y) = \int_\mathbb{R} \frac{\partial f}{\partial x}(x,y)dm(y)$ が成立する．

2017-01-13

ルベーグ積分の収束定理（ルベーグの優収束定理）

数学解析学ルベーグ積分

定理（ルベーグの優収束定理）
関数列 $\{ f_j \}_{j=1}^\infty$ は次の条件を満たすとする．
1) $f_j \to f$ a.e.
2) ある $g \in L^1$ ですべての $j$ に対して $|f_j| \leq g$ a.e.を満たすものが存在する．
このとき $\displaystyle \lim_{j \to \infty} \int f_j dm = \int \lim_{j \to \infty} f_j dm = \int f dm$ が成立する．

注意
1) 関数列に $L^1$ の条件を課す必要はない．
2) $\lim$ と積分との交換がこのような単純な条件でできることが，ルベーグ積分が優れている点のひとつである．

（証明）
$|f_j| \leq g$ a.e
より
$-g \leq f_j \leq g$ a.e.
であるから
$0 \leq g+ f_j \leq 2g, 0 \leq g -f_j \leq 2g$ a.e.
ファトゥの補題から
$\displaystyle \int \liminf_{j \to \infty} ( g+ f_j )dm \leq \liminf_{j \to \infty} \int (g +f_j)dm$
より
$\displaystyle \int (g+f) dm \leq \liminf_{j \to \infty} \int (g +f_j)dm$
から
$\displaystyle \int f dm \leq \liminf_{j \to \infty} \int f_j dm$
である．また
$\displaystyle \int \liminf_{j \to \infty} ( g-f_j )dm \leq \liminf_{j \to \infty} \int (g -f_j)dm$
より
$\displaystyle \int (g-f) dm \leq \liminf_{j \to \infty} \int (g - f_j)dm$
から
$\displaystyle \int (-f) dm \leq \liminf_{j \to \infty} \int (- f_j)dm$
となるので
$\displaystyle \int f dm \geq \limsup_{j \to \infty} \int f_jdm$
である．つまり
$\displaystyle \limsup_{j \to \infty} \int f_jdm \leq \int f dm \leq \liminf_{j \to \infty} \int f_j dm$
でこれは $\displaystyle \lim_{j \to \infty} \int f_j dm = \int f dm$ を意味する．（証明終）

系（有界収束定理）
$m(E) < \infty$ で，関数列 $\{ f_j \}_{j=1}^\infty$ は次の条件を満たすとする．
1) $\{ f_j \}_{j=1}^\infty$ は $E$ で概収束する．
2) ある $M \in \mathbb{R}$ ですべての $j$ に対して $|f_j| \leq M$ a.e. となるものが存在する．
このとき $\displaystyle \lim_{j \to \infty} \int_E f_j dm = \int_E \lim_{j \to \infty} f_j dm$ が成り立つ．

2017-01-12

ルベーグ積分の収束定理（ファトゥの補題）

数学解析学ルベーグ積分

補題（ファトゥの補題）
$f_j \geq 0$ ならば
$\displaystyle \int \liminf_{j \to \infty} f_j dm \leq \liminf_{j \to \infty} \int f_j dm$
が成り立つ．

（証明）
関数列 $\displaystyle g_j :=\inf_{j \leq k} f_k$ を考える．各 $j$ に対して
$g_j \leq f_k (j \leq k)$
$\displaystyle \int g_j dm \leq \int f_k dm (j \leq k)$
$\displaystyle \int g_j dm \leq \inf_{j \leq k} \int f_k dm$
$\displaystyle g_1 \leq g_2 \leq g_3 \leq \cdots \to \liminf_{j \to \infty} f_j$ であるから，単調収束定理が使える．
$\displaystyle \int \liminf_{j \to \infty} f_j dm$
$\displaystyle =\int \lim_{j \to \infty} g_j dm$
$\displaystyle =\lim_{j \to \infty} \int g_j dm$
$\displaystyle \leq \lim_{j \to \infty} \inf_{j \leq k} \int f_k dm$
$\displaystyle = \liminf_{j \to \infty} \int f_jdm$
で従う．（証明終）