Beweis zur Teilbarkeit von Potenzen.

Question

Aufgabe:

Wir haben m,n∈ℕ und a∈ℕ\{1}. Nun soll ich zeigen, wenn m > n und r den Rest der Division von m durch n bezeichnet. Ist d ∈ ℕ ein gemeinsamer Teiler von a^m - 1 und aⁿ - 1, dann teilt d auch a^r - 1.

Problem/Ansatz:

Ich habe versucht a^r - 1 so umzuformen, dass es ein Vielfaches von d ist mit der Gleichung m = qn + r, jedoch komme ich nicht weit. Hoffe ihr könnt mir helfen. Vielen Dank im Voraus!

Answer 1

Auf geht's:

$$\begin{array}{rcl} a^m - 1 & \stackrel{m=nq+r}{=} & a^r\left(a^{n}\right)^q-1 \\ & = & a^r\left(a^{n}\right)^q - a^r + a^r -1  \\ & = & a^r\left( \left(a^{n}\right)^q - 1 \right) + a^r-1 \\ &  \stackrel{\frac{x^q-1}{x-1}=x^{q-1} + \cdots +q + 1}{=}  & a^r \left(a^{n}-1\right)\left( \left(a^{n}\right)^{q-1} + \cdots + a^n + 1 \right) + a^r-1  \end{array}$$
Jetzt folgt sofort die Behauptung.