Mathematik: Berechnung des ggT´s mit dem Satz von Pick
Released by matroid on Mo. 04. Januar 2021 20:20:17 [Statistics]
Written by easymathematics - 1010 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\ggT}{\mathbb{ggT}}\) In diesem Artikel soll es darum gehen den größten gemeinsamen Teiler zweier natürlicher Zahlen \(a,~b~>~0\) mit dem Satz von Pick zu berechnen. Nachfolgendes Theorem verzichtet dabei auf herkömmliche Methoden: a) euklidischer Algorithmus b) Primfaktorzerlegung c) Beziehung zum kgV 1.1 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} \]

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/
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 1010
 
Aufrufstatistik des Artikels
Insgesamt 15 externe Seitenaufrufe zwischen 2021.01 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://google.com320%20 %
https://matheplanet.com213.3%13.3 %
https://google.de213.3%13.3 %
https://www.bing.com320%20 %
https://de.m.wikipedia.org320%20 %
https://www.inoreader.com16.7%6.7 %
https://metager.de16.7%6.7 %

[Top of page]

"Mathematik: Berechnung des ggT´s mit dem Satz von Pick" | 4 Comments
The authors of the comments are responsible for the content.

Danke
von: easymathematics am: Di. 05. Januar 2021 14:42:19
\(\begingroup\)Danke an die fleißigen Helfer. :)\(\endgroup\)
 

Re: Berechnung des ggT´s mit dem Satz von Pick
von: Triceratops am: Di. 05. Januar 2021 19:17:43
\(\begingroup\)Gerne. :)\(\endgroup\)
 

Re: Berechnung des ggT´s mit dem Satz von Pick
von: Ex_Mitglied_53910 am: Di. 05. Januar 2021 21:36:51
\(\begingroup\)Interessante Darstellung des ggT's. Erinnert mich an die Formel von Legendre: https://en.wikipedia.org/wiki/Legendre%27s_formula Hängen die Formeln irgendwie miteinander zusammen?\(\endgroup\)
 

Re: Berechnung des ggT´s mit dem Satz von Pick
von: easymathematics am: Di. 12. Januar 2021 11:44:52
\(\begingroup\)Hallo algbr, diese Formel kenne ich auch. Ob ein Zusammenhang besteht, weiß ich jetzt nicht. Legendres Formel ist für meine Begriffe trivial und ein Spezialfall für die zahlentheoretische Funktion "Exponentenbewertung". (ich glaube, so heißt die) Ich sehe keinen direkten Zusammmenhang. Ich lasse mich aber gerne überzeugen. :)\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]