Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Neuer Abschnitt in Berechnung des ggT´s mit dem Satz von
\(\newcommand{\ggT}{\mathbb{ggT}}\) Ich bin in einem Forum [1] auf \[ \sum_{k=1}^{a} \left\lfloor \frac{b}{a}k \right\rfloor \] gestoßen und im Laufe meiner Überlegungen entstand die Idee, den ggT auf diese Art auszudrücken. Die Idee stammt gewiss nicht von mir und soll der Schönheit wegen hier Platz finden. Ich kann aber auch nicht sagen, wer sie vor mir hatte. Bevor wir den Beweis besprechen, möchte ich die/das ein oder andere Definition/Lemma in Erinnerung rufen. 1.2 Definition: (Gauß-Klammer) Für \(x \in \mathbb{R}\) ist \( \lfloor x \rfloor \) die größte ganze Zahl $k$, die kleiner oder gleich $x$ ist. \[ \lfloor x \rfloor := \max \{k \in \IZ : k \leq x\} \] 1.3 Definition: (Gitterpunkte) Ein Punkt \(P(x,y) \in \mathbb{R}^2 \) heißt Gitterpunkt :\( \Leftrightarrow\) \(x,y \in \mathbb{Z}\) 1.4 Lemma: Für die Anzahl $g$ an Gitterpunkten auf der Strecke zwischen zwei verschiedenen Gitterpunkten \( P(x_P,y_P), Q(x_Q,y_Q) \) ohne $P$ und $Q$ gilt: \( g = \mathrm{ggT}\bigl(|x_P - x_Q|,|y_P - y_Q|\bigr)-1 \) Der Beweis wird dem Leser überlassen. $\checkmark$ Es gibt einen Satz, der beschreibt, wie der Flächeninhalt eines Polygons, dessen Ecken auf Gitterpunkten liegt, abhängt von den Gitterpunkten auf dem Umfang und im Inneren des Polygons. 1.5 Satz: (Pick) Für den Flächeinhalt \(A\) eines Polygons (ohne Überschneidung, ohne Löcher) konstruiert aus Gitterpunkten gilt: \[ A = \frac{r}{2} + i - 1 \] Dabei ist \( r = \) Anzahl Gitterpunkte auf dem Rand \( i = \) Anzahl Gitterpunkte im Inneren Beweis: Wir beweisen den Satz von Pick für zwei Figuren. a) Achsenparallele Rechtecke: Seien dazu \(A(0,0), B(a,0), C(a,b)\) und \(D(0,b)\) vier Gitterpunkte.
Man sieht leicht ein: \(\displaystyle \frac{r}{2} + i - 1 = \frac{2a+2b}{2} + ((a-1)(b-1)) - 1 = ab = A_{Rechteck} \) b) Rechtwinklige Dreiecke mit achsenparallelen Katheten: Halbieren wir obiges Rechteck entlang der Diagonale $AC$ und zählen vorsichtig die Gitterpunkte, finden wir: \(\displaystyle \frac{r}{2} + i - 1 = \frac{a+b+\mathrm{ggT}(a,b)}{2} + \frac{(a-1)(b-1)-(\mathrm{ggT}(a,b)-1)}{2} - 1 = \frac{ab}{2} = A_{Dreieck} \) Damit ist der Satz von Pick für unsere Zwecke bewiesen. $\checkmark$ 1.6 Hinweis: Weitere Beweisdetails mögen selbst gesucht werden. Nun können wir unser Theorem beweisen. Theorem: Für zwei natürliche Zahlen \(a, b > 0\) gilt: \[ \mathrm{ggT}(a,b) = {a-b-ab+2 \sum_{k=1}^{a} \left\lfloor \frac{b}{a}k \right\rfloor} \] Beweis: Seien dazu \(A(0,0), B(a,0), C(a,b)\) drei Gitterpunkte. Dann ist \[ h(x) = \frac{b}{a} x,\quad 0 \leq x \leq a \] die Gleichung der Hypotenuse des \(\Delta_{ABC}\). Und \[ S = \sum_{k=1}^{a} \lfloor h(k) \rfloor \] zählt die Gitterpunkte auf dem Umfang und im Inneren, ausgenommen die Gitterpunkte auf der Seite $AB$. Wir können \(S\) auch folgendermaßen darstellen: (bitte selbst überzeugen) \[\begin{equation} \label{1} S = i + b + (\mathrm{ggT}(a,b) - 1) \end{equation}\] Nach Pick gilt für \(i\) (vorsichtig zählen) \[\begin{equation} \label{2} i = \frac{ab - (a + b + \mathrm{ggT}(a,b)) + 2}{2} \end{equation}\] Setzen wir ($\ref{2}$) in ($\ref{1}$) ein und stellen nach $\mathrm{ggT}(a,b)$ um, erhalten wir unser Resultat. $\checkmark$ 1.7 Beispiele: (1) $\underline{a = 5,~ b = 15:}$ \(\displaystyle \mathrm{ggT}(5,15) = {5-15-5*15 +2 \sum_{k=1}^{5} \left\lfloor \frac{15}{5}k \right\rfloor} = -85 + 2*3\frac{5(5+1)}{2} = 5 \) (2) $\underline{a = b:}$ \(\displaystyle \mathrm{ggT}(a,a) = {a-a-a^2 +2 \sum_{k=1}^{a} \left\lfloor \frac{a}{a}k \right\rfloor} = -a^2 + 2\frac{a(a+1)}{2} = a \) 1.8 Aufgabe: a) Man gebe $S$ mit Hilfe einer $3 \times 3$-Determinante an. b) Man bestimme einen Ausdruck, der für ein Dreieck mit beliebigen Gitterpunkten die Gitterpunkte im Inneren des Dreiecks angibt. c) Man zeige ausgehend von \[ \mathrm{ggT}(a,b) = {a-b-ab+2 \sum_{k=1}^{a} \left\lfloor \frac{b}{a}k \right\rfloor} \] die Kommutativität des ggT´s. Ja, das war mein erster Artikel. :) Hoffe, er hat Euch gefallen. LG, easymathematics Quelle: [1] www.math.stackexchange.com/questions/207604/floor-number-sum/
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]