Kongruenz mit Induktion

13.06.2018, 09:29

line32

Kongruenz mit Induktion

Meine Frage:
Zeige 3^2^n = 1+ 2^(n+2) (mod 2^(n+3))

Meine Ideen:
IA ist klar.
Beim Induktionsschritt ändert sich jetzt aber die modulo - klasse also zu 2^(n+4) und dann ist die Onduktionsvoraussetzung doch nicht mehr gegeben, wie geht das?

13.06.2018, 10:03

HAL 9000

Auf diesen Beitrag antworten »

Schreiben wir es erstmal in besser lesbarer Form auf: $\begin{eqnarray*} 3^{2^n}\equiv 1+2^{n+2}\bmod 2^{n+3} \end{eqnarray*}$ , und das gilt auch erst für $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ (d.h. für $\begin{eqnarray*} n=0 \end{eqnarray*}$ gilt es nicht).

Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ willst du ja gewiss $\begin{eqnarray*} 3^{2^{n+1}} = 3^{2^n\cdot 2} = \left(3^{2^n}\right)^2 \end{eqnarray*}$ nutzen, oder?

Die Induktionsvoraussetzung kann man auch so schreiben: Es gibt eine ganze Zahl $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 3^{2^n} = 1+2^{n+2} + k\cdot 2^{n+3} = 1+(2k+1)\cdot 2^{n+2} \end{eqnarray*}$ . Nun quadriere das mal...

13.06.2018, 10:58

line32

Auf diesen Beitrag antworten »

$\begin{eqnarray*} (3^{2^{n }})^2= 1+2^{n+3} +k*2^{n+4}+(2k+1)^2 * 2^{n+4} *2^n=1+2^n [2^3 +(2k+1)^2 *2 ^{n+4}] + k*2^{n+4} \equiv 1+2^{n+3} mod 2^{n+4} \end{eqnarray*}$

geht das so?

13.06.2018, 11:22

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von line32
$\begin{eqnarray*} (3^{2^{n }})^2= 1+2^{n+3} +k*2^{n+4}+(2k+1)^2 * 2^{n+4} *2^n=1+2^n [2^3 +(2k+1)^2 *2 ^{n+4}] + k*2^{n+4} \end{eqnarray*}$

Die letzte Umformung verkompliziert die Lage eigentlich nur. Ich hätte so umgeformt:

$\begin{eqnarray*} (3^{2^{n }})^2= 1+2^{n+3} + k \cdot 2^{n+4} + (2k+1)^2 \cdot 2^{n+4} \cdot 2^n = 1+2^{n+3} + (k + (2k+1)^2 \cdot 2^n) \cdot 2^{n+4} \end{eqnarray*}$ smile

13.06.2018, 11:31

line32

Auf diesen Beitrag antworten »

Okay danke.
noch eine frage, wenn ich $\begin{eqnarray*} ord_{2n} (3)=2^{n-2} \end{eqnarray*}$ zeigen soll (für alle n größer gleich 3) kann ich das ja auch mit Induktion machen, aber ich muss ja auch irgendwie immer zeigen, dass die 2^(n-2) der kleinste Exponent ist für den die Kongruenz gilt verwirrt

13.06.2018, 12:53

HAL 9000

Auf diesen Beitrag antworten »

Wozu brauchst du dazu noch Induktion? Nutze doch direkt die eben bewiesene Aussage!

$\begin{eqnarray*} \operatorname{ord}_{2^n}(3) \end{eqnarray*}$ ist ein Teiler der Gruppenordnung $\begin{eqnarray*} \varphi(2^n) = 2^{n-1} \end{eqnarray*}$ , also auf jeden Fall irgendeine Zweierpotenz. Die obige Aussage um 3 Positionen verschoben lautet nun

$\begin{eqnarray*} 3^{2^{n-3}} \equiv 1+2^{n-1}\not\equiv 1\bmod 2^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ ,

d.h. es ist auf jeden Fall $\begin{eqnarray*} \operatorname{ord}_{2^n}(3)>2^{n-3} \end{eqnarray*}$ . Andererseits haben wir bei Verschiebung um 2

$\begin{eqnarray*} 3^{2^{n-2}} \equiv 1+2^n\bmod 2^{n+1} \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ ,

woraus $\begin{eqnarray*} 3^{2^{n-2}} \equiv 1\bmod 2^n \end{eqnarray*}$ folgt. Damit haben wir sofort $\begin{eqnarray*} \operatorname{ord}_{2^n}(3)=2^{n-2} \end{eqnarray*}$ zumindest für alle $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ . Für $\begin{eqnarray*} n=3 \end{eqnarray*}$ kann man es aber auch noch per Einzelfallbetrachtung nachweisen.

Neue Frage »

Antworten »

Kongruenz mit Induktion

Verwandte Themen