Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Der kleine Satz von Fermat

Der kleine Satz von Fermat

Universität / Fachhochschule

Gruppen

Tags: Anwendung des FERMATschen Satzes, Gruppen

Katrinee aktiv_icon

20:37 Uhr, 19.03.2009

Hej,

leider komme ich mit einer Aufgabe zur Anwendung des kleinen FERMATschen Satzes nicht weiter. Oder eher, ich habe diesen Satz nicht wirklich begriffen...
Die Aufgabe:
Man ermittle eine Lösung von

17^{97} = x mod 7

(das "=" soll eigentlich drei Striche haben)
Die Lösung ist auch angegeben. Sie lautet: 17^97=3(7)(wieder drei Striche beim Gleichzeichen!)

Kann mir jemand erklären, wie man auf diese Lösung kommt? Ich sitz da jetzt echt schon ne Ewigkeit dran und komm einfach nicht drauf.
Vielen lieben Dank für eure Hilfe!

Grüße Ka

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

adrilleros aktiv_icon

01:05 Uhr, 21.03.2009

Hallo,

also es geht hier um Kongruenzrelationen.
Zur Lösung Deiner Aufgabe brauchst Du den Fermat'schen Satz nicht.
Du musst jedoch folgende Regeln kennen:
Falls

a = b [n]

ist dann auch:

1) a^{m} = b^{m} [n]

für

m

ℕ

2) k \cdot a = k \cdot b [n]

für

k

ℤ

3)

Falls

a = b [n]

und

b = c [n]

sind dann gilt

a = c [n]

{

Transitivität}

Du suchst den Rest der euklidischen Division von

17^{97}

durch 7
Wenn Du jetzt

a = r [n]

hast, so ist

r

der Rest der euklidischen Division von a durch

n

falls

0 \leq r < n

gilt.
Der Trick bei solchen Aufgaben ist es eine Potenz deiner zu teildenden Zahl zu finden, die kongruent zu

- 1, 0

oder 1 modulo

n

ist.

Hier mal ein konkretes Beispiel:

Was ist der Rest der euklidischen Division von

32^{45}

durch 7?
Mit anderen Worten:

32^{45} = x [7] \to x =

32^{1} = 4 [7]

denn es ist

32^{1} = 7 \cdot 4 + 4 \to

der Rest ist also 4

32^{2} = 4 \cdot 32 = 128 = 2 [7]

denn es ist

128 = 7 \cdot 18 + 2

{

wir multiplizieren

32

einfach mit 4 da

32^{1} = 4 [7]

ist, das erspart viel Rechnerei anstatt

32^{2} = 1024

dann dieses modulo 7 zu rechnen, das Ergebnis ist in beiden Fällen daselbe

}

Also haben wir

: 32^{2} = 2 [7]

32^{3} = 2 \cdot 32 = 64 = 1 [7]

denn es ist

64 = 7 \cdot 9 + 1

Also gilt

32^{3} = 1 [7]

:-D)
Wir haben in unserer Aufgabe aber

32^{45}

also was jetzt?
Wir teilen

45

durch 3 und erhalten:

45 = 3 \cdot 15

jetzt wenden wir Regel

(1)

an:

32^{3} = 1 [7]

\Leftrightarrow {(32^{3})}^{15} = 1^{15} [7]

\Leftrightarrow 32^{45} = 1 [7]

\Rightarrow

Der Rest der euklidischen Division von

32^{45}

durch 7 ist 1

- - - - - - - - - - - - - - - - - -

In Deinem Beispiel gehst Du genau so vor

{

Du wirst jedoch auch noch von Regel

(2)

und

(3)

Gebrauch machen müssen, ist aber machbar

}

Gruß

adi

QPhma aktiv_icon

01:15 Uhr, 21.03.2009

Die Aufgabe ist ein bischen was zum Knobeln. Wenn du nicht auf die Lösung kommst, hat das wahrscheinlich nichts damit zu tun, ob du den kleinen Fermat verstanden hast oder nicht.

Es fällt auf, dass die Potenz nicht mit der Modulo-Zahl übereinstimmt wie im Satz des Fermat $a^{p} \equiv a (p)$ . Und es stimmt auch nicht, wenn man die andere Schreibweise des Fermat nimmt $a^{p - 1} \equiv 1 (p)$ . Das heißt, du mußt versuchen, den Exponenten in eine Summe aus Sechsen und Siebenen zu aufzuteilen, also 97 = n*6 + m*7. Damit kannst du dann die Potenz zerlegen und auf jeden Faktor einzeln den Satz des Fermat anwenden.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

590339

589875

	Status: nicht eingeloggt	Noch nicht registriert?