Beweis ggT

04.11.2012, 10:47	Zwerg^1	Auf diesen Beitrag antworten »
Beweis ggT Meine Frage: Ich hätte eine kurze Frage, und zwar wie kann man das folgende beweisen? Hat da jemand einen gut formulierten Beweis zur Hand? Ich komme nicht drauf.. und bräuchte die Aufgabe dringend zur Vorbereitung. Meine Ideen: Also die Aufgabe lautet ggT $\begin{eqnarray} (x^{m} - 1, x^{n} -1) = x^{ggT (m,n)} -1 \end{eqnarray}$ m,n,x sind aus den natrülichen Zahlen und x größer als 1. Wäre sehr dankbar für Hilfe..
04.11.2012, 10:58	Mystic	Auf diesen Beitrag antworten »
RE: Beweis ggT Du musst Folgendes zeigen: Sind $\begin{eqnarray} a,b,q,r \end{eqnarray}$ natürliche Zahlen mit $\begin{eqnarray} a=qb+r, \quad 0\le r <b \end{eqnarray}$ d.h., q und r sind Quotient bzw. Rest bei der Division von a durch b, so gibt es dann ein Polynom $\begin{eqnarray} \tilde{q}(X) \in \mathbb{Z}[X] \end{eqnarray}$ , sodass $\begin{eqnarray} X^a-1=\tilde{q}(X)(X^b-1)+(X^r-1) \end{eqnarray}$ Alles weitere folgt ja dann aus dem Euklidischen Algorithmus...
04.11.2012, 11:08	HAL 9000	Auf diesen Beitrag antworten »
Beweistechnisch kann man das ganze auch als indirekten Beweis anlegen, ohne auf den Euklidischen Algorithmus zurückzugreifen: Für alle $\begin{eqnarray} (x,m,n) \end{eqnarray}$ , für die die Aussage nicht gilt, gibt es auch ein Tripel mit minimalen $\begin{eqnarray} \max(m,n) \end{eqnarray}$ ...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »