Zahlentheorie/Beweis mit ggt

23.10.2018, 14:36	InaAldi	Auf diesen Beitrag antworten »
Zahlentheorie/Beweis mit ggt Hallo, Folgendes soll bewiesen werden $\begin{eqnarray} ggt\left(a^{n}- 1,a^{m}- 1\right) = a^{ggt(n,m)} - 1 \end{eqnarray}$ Kann mir einer dabei helfen? Vielen Dank Ina
23.10.2018, 16:29	HAL 9000	Auf diesen Beitrag antworten »
Ich würde es als indirekten Beweis anlegen: Angenommen, es gibt $\begin{eqnarray} n,m \end{eqnarray}$ , so dass diese Gleichung nicht gilt. Der Symmetrie wegen dürfen wir dabei o.B.d.A: $\begin{eqnarray} n\geq m \end{eqnarray}$ annehmen. Dann gibt es auch ein kleinstes $\begin{eqnarray} n_0 \end{eqnarray}$ und zugehörig $\begin{eqnarray} m_0 \end{eqnarray}$ mit $\begin{eqnarray} m_0\leq n_0 \end{eqnarray}$ , so dass $\begin{eqnarray} \operatorname{ggT}\left(a^{n_0}-1,a^{m_0}-1\right) \neq a^{\operatorname{ggT}\left(n_0,m_0\right)}-1\qquad () \end{eqnarray}$ gilt... Daraus kann man einen Widerspruch derart ableiten, dass man ein noch kleineres* Paar (n',m') konstruiert, für das die Gleichung nicht gilt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »