Beweis zum gemeinsamen Teiler von Potenzen

Question

Aufgabe:

Seien m,n ∈ ℕ und a ∈ ℕ \ {1}. Nun soll ich zeigen, wenn d∈ℕ ein gemeinsamer Teiler von m und n ist, dann ist a^d - 1 ein gemeinsamer Teiler von a^m - 1 und aⁿ - 1.

Problem/Ansatz:

Ich wollte zuerst zeigen, dass a^d - 1 ein Teiler von a^m - 1 ist. Das habe ich bisher, da ein x existiert mit m = x*d:
a^m - 1 = a^xd - 1 = (a^d)^x - 1 = (a^d)^(x-1) * (a^d ) - 1

Nur weiß ich nicht was ich mit dieser -1 anstellen soll. Ich hoffe jemand kann mir helfen. Danke im Voraus :D

Answer 1

(a^d)^x - 1 ist durch a^d - 1 teilbar. Allerdings kommt da eine unschöne Summe heraus. Das braucht uns aber nicht stören. Wichtig ist ja nur, dass es teilbar ist.

((a^d)^x - 1) / (a^d - 1) = 1 + a^d + a^(2·d) + a^(3·d) + ... + a^((x - 1)·d)

Comments

Woher wissen wir dass das gilt? :D Ich verstehe nicht ganz wie du darauf kommst.

---

(a - 1) * (1 + a + a^2 + a^3 + ... + a^x)

= (a + a^2 + a^3 + ... + a^(x + 1)) - (1 + a + a^2 + ... + a^x)

= a^(x + 1) - 1

---

Ah perfekt. Jetzt verstehe ich es. Danke :D