Beweis zum ggT

24.10.2008, 02:47

Bjoern1982

Beweis zum ggT

Hallo,

seien a und m natürliche Zahlen mit m>1

zu zeigen:

$\begin{eqnarray*} ggT(\frac{a^m-1}{a-1},a-1)=ggT(a-1,m) \end{eqnarray*}$

Meine Ideen:

Wegen ggT(a,b)=ggT(b,a mod b) dachte ich dann an den Nachweis von

$\begin{eqnarray*} m\equiv \frac{a^m-1}{a-1}\mod (a-1)= \sum_{k=0}^{m-1}~a^k\mod (a-1) \end{eqnarray*}$

Aber so richtig zeigen kann ich das nicht.

Ist das überhaupt der richtige Ansatz ?

Gruß Björn

24.10.2008, 03:42

WebFritzi

Auf diesen Beitrag antworten »

Jupp, das ist ein Ansatz. Wie wär's mit vollst. Induktion? Augenzwinkern

24.10.2008, 04:16

Bjoern1982

Auf diesen Beitrag antworten »

Ach guck an...nagut dann versuch ich das nochmal eben schnell:

Induktion nach m:

Ind.Anf.

m=2: a^0+a^1=1+a mod (a-1) ist kongruent 2+a mod a und das ist 2 ---> passt

Ind.Schritt

m --> m+1

$\begin{eqnarray*} \sum_{k=0}^{m}~a^k\mod (a-1)=m+a^m \mod (a-1)=m+a^m+1 \mod a \equiv m+1 \end{eqnarray*}$

Das wars schon oder ?

24.10.2008, 07:35

Auf diesen Beitrag antworten »

Also den Schritt musst du mir mal näher begründen:

Zitat:

Original von Bjoern1982
$\begin{eqnarray*} m+a^m \mod (a-1) = m+a^m+1 \mod a \end{eqnarray*}$

24.10.2008, 11:25

Bjoern1982

Auf diesen Beitrag antworten »

Hmm, passt wohl doch nicht so ganz...heute Nacht dachte ich irgendwie das sei möglich aber so nach weiterem drüber Nachdenken ist es wohl nur zufällig so, dass das mit dem Rest auch so hinkommt oder ?

Nagut dann lieber so:

$\begin{eqnarray*} \sum_{k=0}^{m}~a^k\mod (a-1)=m+a^m \mod (a-1)=m+a^m-1+1 \mod (a-1) =m+(a-1) \cdot (\sum_{k=0}^{m-1}~a^k)+1 \mod(a-1) \equiv m+1 \end{eqnarray*}$

Jetzt in Ordnung ?

24.10.2008, 18:28

Auf diesen Beitrag antworten »

Damit kann ich mich anfreunden. Augenzwinkern

Übrigens scheint auch bei dir die Unsitte verbreitet, das Modulo-Zeichen nur als binären Operator $\begin{eqnarray*} \mathbb{Z} \times \mathbb{N} \to \mathbb{N} \end{eqnarray*}$ zu verstehen, statt als Kennzeichnung dafür, dass man im Restklassenring $\begin{eqnarray*} \mathbb{Z}/(a-1)\mathbb{Z} \end{eqnarray*}$ rechnet. Damit würde deine letzte Zeile einfach so lauten:

$\begin{eqnarray*} \sum_{k=0}^{m} ~ a^k \equiv m+a^m = m+a^m-1+1 = m+(a-1) \cdot \left( \sum_{k=0}^{m-1}~a^k \right)+1 \equiv m+1 \mod (a-1) \end{eqnarray*}$

Als binärer Operator betrachtet, dann mit Endergebnis im Bereich $\begin{eqnarray*} 0,\ldots,a-1 \end{eqnarray*}$ wäre die Aussage

$\begin{eqnarray*} \sum_{k=0}^{m} ~ a^k \mod (a-1) = m+1 \end{eqnarray*}$

i.a. sogar falsch: Man betrachte nur mal $\begin{eqnarray*} a=3 \end{eqnarray*}$ und $\begin{eqnarray*} m=1 \end{eqnarray*}$ , dann ist

$\begin{eqnarray*} \sum_{k=0}^{m} ~ a^k \mod (a-1) = (1+3) \mod 2 = 0 \neq 2 \end{eqnarray*}$ .

24.10.2008, 20:22

Bjoern1982

Auf diesen Beitrag antworten »

Stimmt, ich war bzw bin mir manchmal auch unsicher wann ich ein Gleichheitszeichen und wann lieber ein Kongruenzzeichen hinschreiben soll. Mir ist jetzt aber klar warum es so nicht ganz korrekt war. Danke

Björn

Neue Frage »

Antworten »

Beweis zum ggT

Verwandte Themen