Kongruenz

26.07.2006, 12:24

landy

Kongruenz

Hi@all
ich möchte hier gerne eine kleine konguzenzrechnung lösen aber ich weis nicht mehr weiter
gegeben:
beweise mithilfe der konguzenzrechnung, dass 2^512-1 durch 4147 teilbar ist
ich habs mal mit modulo angeschrieben:
$\begin{eqnarray*} 2^{512}-1 \equiv 0 mod 4147 \end{eqnarray*}$
so
nun hab ich 2^512 umgeschrieben auf (2^2)^9
und die primfaktoren von 4147=11*13*29
nun komme ich nicht weiter
(bin grad dabei mir die kongurenztheorie beizubringen aber das beispiel versteh ich nicht ganz)
wär toll wenn mir da wer helven könnte

26.07.2006, 12:59

Auf diesen Beitrag antworten »

Blöd nur, dass es nicht stimmt. Es ist nämlich

$\begin{eqnarray*} 2^{512}-1 \equiv 1763 \mod 4147 \end{eqnarray*}$ . Teufel

26.07.2006, 14:32

klarsoweit

Auf diesen Beitrag antworten »

RE: kongurenz

Zitat:

Original von landy
nun hab ich 2^512 umgeschrieben auf (2^2)^9

Du meintest vermutlich: 2^(2^9) Augenzwinkern

Helfen tut die Folge:
a_1 = 2, $\begin{eqnarray*} a_{n+1} = a_n^2 \mod 4147 \end{eqnarray*}$

26.07.2006, 15:09

mYthos

Auf diesen Beitrag antworten »

BTW: Es heisst Kongruenz, nicht Kongurenz!

Gr
mYthos

edit 20: und deshalb Titel geändert.

27.07.2006, 08:42

landy

Auf diesen Beitrag antworten »

@mYthos: danke! ich habs wohl immer flasch gelesen Hammer

@Arthur Dent+klarsoweit: kannst du mir deinen rechenweg erklären ? Ich hab das Beispiel aus dem Buch: "Zahlentheorie für Einsteiger" und die Aufgabenstellung lautete in etwa "Zeige dass 2^512-1 ohne rest durch 4147 teilbar ist". Aber da ich kein studierter Mathematiker bin versteh ich einiges noch nicht ganz. Ich finde es aber hochintressant wie man so mit riesigen Zahlen sehr einfach herumhantieren kann.

mod rules Freude

27.07.2006, 08:57

Auf diesen Beitrag antworten »

Zitat:

Original von landy
@Arthur Dent+klarsoweit: kannst du mir deinen rechenweg erklären ?

Steht doch alles da:

Zitat:

Original von klarsoweit
$\begin{eqnarray*} a_1 = 2,\quad a_{n+1} = a_n^2 \mod 4147 \end{eqnarray*}$

Dieses Verfahren liefert $\begin{eqnarray*} a_n = 2^{2^{n-1}} \mod 4147 \end{eqnarray*}$ .

Du brauchst $\begin{eqnarray*} a_{10} \end{eqnarray*}$ , führst also die Iteration genau 9-mal aus.

27.07.2006, 09:34

landy

Auf diesen Beitrag antworten »

@Atrtur Dent: Was bedeutet Iteration ?
und gibt es nicht einen einfacheren weg um den Rest zu berechnen ?
Mit dieser Methode entstehen ja doch wieder große Zahlen!

27.07.2006, 09:42

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von landy
Mit dieser Methode entstehen ja doch wieder große Zahlen!

Nein, wieso?
Du fängst mit a_1 = 2 an und bildest den Rest bei Division durch 4147. Das ist natürlich 2. Dann quadrierst du das Ergebnis und bildest wieder den Rest, usw. Das machst du 9-mal und bist beim Rest für $\begin{eqnarray*} 2^{2^{n-1}} \end{eqnarray*}$ angekommen.

27.07.2006, 10:11

Lazarus

Auf diesen Beitrag antworten »

Zitat:

Original von klarsoweit
[...]Das machst du 9-mal und bist beim Rest für $\begin{eqnarray*} 2^{2^{n-1}} \end{eqnarray*}$ angekommen.

Denn dann bist du beim Rest für $\begin{eqnarray*} 2^{2^{8}} \end{eqnarray*}$ angekommen, nicht bei $\begin{eqnarray*} n-1 \end{eqnarray*}$ und auch noch nicht bei $\begin{eqnarray*} 9 \end{eqnarray*}$ . Dazu musst dus nochmal machen.

27.07.2006, 11:07

klarsoweit

Auf diesen Beitrag antworten »

Lazarus: möglicherweise hast du mich mißverstanden.

Man fängt mit a_1 an und macht den Rekursionsschritt einmal, dann ist man bei a_2 angekommen.
Macht man den Rekursionsschritt 9-mal, dann ist man logischerweise bei a_10 angekommen. Und das ist eben der Rest von $\begin{eqnarray*} 2^{2^9} = 2^{512} \end{eqnarray*}$ .

27.07.2006, 13:41

landy

Auf diesen Beitrag antworten »

@klarsoweit danke ich hab das kapietel jetzt nocheinmal durchgearbeitet und habs jez kapiert!
ich habs mal in excel ausprobiert und als bild eingefügt

edit: -1 hab ich vergessen ! Hammer

27.07.2006, 13:52

Auf diesen Beitrag antworten »

Richtig. Und falls der Exponent mal keine Zweierpotenz ist, kann man das Verfahren modifiziert dennoch nutzen, siehe hier.

27.07.2006, 13:59

landy

Auf diesen Beitrag antworten »