FC2ブログ

雅楽多文書館

Entry 356   Permanent LIN K

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

--/--/--   スポンサー広告    

ggT(a,b)

Satz
Für $a, \, b \in \mathbb{Z}$ mit $b \ne0$ bezeichne $g=\text{ggT} (a, b)$.
$M=\{ ax+by : x, y \in \mathbb{Z}\}$
$N= \{gk : k \in \mathbb{Z}\}$
Dann gilt
$M=N$.


Lemma 1
Sei $d=ax_0+by_0$ das kleinste Element mit $ 0 < d \in$ M. Dann teilt $d$ alle Elemente von M.
Beweis.
Seien $q$ der Quotient und $r$ der Rest, wenn $ax+by$ durch $d$ dividiert.
\[ ax+by=dq+r \quad ( 0 \leqq r < d) \] \begin{align*}
r&=ax+by-qd\\
&= ax+by-(ax_0+by_0)q\\
&=a(x-x_0q)+b(y-y_0q) \in \text{M}.
\end{align*} Da $0 \leqq r < d$ ist und $d$ als kleinste positive Zahl ist, folgt $r=0$.
Also ist $d$ ein Teiler alle Elemente von M. $\quad$ w.z.b.w.

Lemma 2
Sei $d=ax_0+by_0$ das kleinste Element mit $ d \in$ M. Dann gilt $d=g$.
Beweis.
Aus $g|a$ und $g|b$ folgt $g|d$.  $\therefore\quad g \leqq d \cdots ➀$.
Auf der anderen Seite
$a=a \times1+b \times 0 \in \text{M}$,   $b=a \times 0+b \times 1 \in \text{M}$.
Nach Lemma1 gilt $d|a, \, \, \, d|b$, somit ist $d$ ein gemeinsamer Teiler von $a$ und $b$.
$\therefore\quad g \geqq d \cdots ➁$
Aus ➀ und ➁ folgt $g=d$. $\quad $ w.z.b.w.

Beweis von Satzt
Für alle $ax+by \in \text{M}$, gilt $d|ax+by$ (Nach Lemma 1).
Nach Lemma 2 gilt $g|ax+by$, d.h. $ax+by=gk, '\, \exists k ' \in \mathbb{Z}$.
$\therefore \quad ax+by \in N$.
$\therefore \quad $ M $\subseteq N \cdots ➂$
Auf der anderen Seite
Für $\forall gk \in \text{N}$.
Da $g=d=ax_0+by_0$ ist, folgt
$gk=dk=(ax_0+by_0)k=a(kx_0)+b(ky_0) \in \text{M}$.
$\therefore \quad $ N $\subseteq M \cdots ④$.
Aus ③ und ④ folgt M = N. $\cdots$ w.z.b.w.


コメント
難しいのはドイツ語.


スポンサーサイト

2015/06/10   Mathematik     356TB 0   356Com 0  

Comment

 

P.W.   Secret    

Trackback

http://kiyosi38.blog.fc2.com/tb.php/356-5be9ae1d

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。