ggT mit einer variablen Potenz

08.09.2022, 09:58	_Bastii	Auf diesen Beitrag antworten »
ggT mit einer variablen Potenz Guten Morgen, ich soll für alle $\begin{eqnarray} a \in \mathbb{N} \end{eqnarray}$ den größten gemeinsamen Teiler $\begin{eqnarray} g \end{eqnarray}$ berechnen und dann für jedes gefundene $\begin{eqnarray} g \end{eqnarray}$ angeben, welche $\begin{eqnarray} a \end{eqnarray}$ zu dem jeweiligen g gehören. $\begin{eqnarray} g = ggT(7^{a}-1, 48) \end{eqnarray}$ Mir ist natürlich direkt durch ausprobieren aufgefallen, dass $\begin{eqnarray} g=6 \end{eqnarray}$ bei ungeraden $\begin{eqnarray} a \end{eqnarray}$ und $\begin{eqnarray} g=48 \end{eqnarray}$ bei geraden $\begin{eqnarray} a \end{eqnarray}$ . Mir fällt nur keine Möglichkeit ein, dass für alle $\begin{eqnarray} a \end{eqnarray}$ zu zeigen. Habt ihr einen Tipp für mich?
08.09.2022, 10:12	HAL 9000	Auf diesen Beitrag antworten »
Berechne doch einfach $\begin{eqnarray} 7^a-1\bmod 48 \end{eqnarray}$ einmal für gerade $\begin{eqnarray} a=2k \end{eqnarray}$ und dann für ungerade $\begin{eqnarray} a=2k+1 \end{eqnarray}$ .
08.09.2022, 10:13	Leopold	Auf diesen Beitrag antworten »
Auf die Schnelle fällt mir die geometrische Summe ein: $\begin{align} 7^0 + 7^1 + 7^2 + \ldots + 7^{a-1} \end{align}$ Wenn $\begin{align} a \end{align}$ gerade ist, ist die Anzahl der Summanden gerade, so daß man Paare bilden kann: $\begin{align} (1+7) + 7^2 \cdot (1+7) + 7^4 \cdot (1+7) + \ldots \end{align}$
08.09.2022, 18:35	_Bastii	Auf diesen Beitrag antworten »
Danke für die Tipps. Ich denke mal, dass $\begin{eqnarray} 7^{2k}-1 \bmod 48 \end{eqnarray}$ mir wegen der Regel $\begin{eqnarray} ggT(a, b \bmod a)= ggT(a, b) \end{eqnarray}$ weiterhelfen wird aber ich weiß nicht wie ich $\begin{eqnarray} 7^{2k}-1 \bmod 48 \end{eqnarray}$ berechnen kann.
08.09.2022, 18:42	HAL 9000	Auf diesen Beitrag antworten »
$\begin{eqnarray} 7^{2k} = \left(7^2\right)^k = 49^k\equiv 1^k = 1\bmod 48 \end{eqnarray}$
09.09.2022, 08:34	_Bastii	Auf diesen Beitrag antworten »
Vielen Dank! Dann habe ich es jetzt. $\begin{eqnarray} g = ggT(7^{a}-1, 48) \end{eqnarray}$ Setze $\begin{eqnarray} a = 2k \end{eqnarray}$ (für a gerade): $\begin{eqnarray} ggT(7^{2k}-1, 48) = ggT((7^{2k}-1) \bmod 48, 48) = ggT(((7^2)^k-1) \bmod 48, 48) = ggT(((49 \bmod 48)^k -1) \bmod 48, 48) = ggT((1^k - 1) \bmod 48, 48) = ggT(0, 48) = 48 \end{eqnarray}$ Setze $\begin{eqnarray} a = 2k+1 \end{eqnarray}$ (für a ungerade): $\begin{eqnarray} ggT(7^{2k+1}-1, 48) = ggT((7^{2k+1}-1) \bmod 48, 48) = ggT(((7^2)^k \cdot 7 - 1) \bmod 48, 48) = ggT(((49 \bmod 48)^k \cdot 7 - 1) \bmod 48, 48) = ggT((1^k \cdot 7 - 1) \bmod 48, 48) = ggT(6, 48) = 6 \end{eqnarray}$ $\begin{eqnarray} \implies g = 48\; \forall a = 2k \land g = 6\; \forall a = 2k+1, k \in \mathbb{N}^{>0} \end{eqnarray}$
Anzeige

09.09.2022, 08:37	HAL 9000	Auf diesen Beitrag antworten »
So ist es.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »