Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Satz von Euler Fermat

Satz von Euler Fermat

Universität / Fachhochschule

Primzahlen

Tags: euler, Fermat, Phi, Potenzen, Primzahl

nati001 aktiv_icon

22:27 Uhr, 29.04.2010

Hallo ich habe eine Frage zur Anwendung von Euler Fermat.

Wie wende ich den Satz bei 2^(2^32) mod 11 an?

könnte mir jemand viell helfen!?

mfg

natalie

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

Hierzu passend bei OnlineMathe:
Potenzregeln (Mathematischer Grundbegriff)
Rechnen mit Potenzen

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Teilbarkeit natürlicher Zahlen

el holgazán aktiv_icon

22:44 Uhr, 29.04.2010

Euler Fermat sagt ja, dass:

a^{10} \equiv 1

mod 11
für alle a

Also z.B.:

2^{23} = 2^{10 + 10 + 3} = 2^{10} \cdot 2^{10} \cdot 2^{3} \equiv 1 \cdot 1 \cdot 2^{3} = 2^{3}

mod 11

Also musst du den Exponenten nur Modulo 10 betrachten.

nati001 aktiv_icon

23:34 Uhr, 29.04.2010

ok und wie kann ich das jetz auf mein beispiel anwenden?

el holgazán aktiv_icon

01:23 Uhr, 30.04.2010

Naja, berechne eben

2^{32}

mod 10
Das kannst du einfach machen, weil mod 10 ja einfach die letzte Stelle in der normalen Zahlendarstellung ist.
Dann musst du dir eben überlegen, welche letzte Zahl

2^{n}

hat für beliebiges n.

Wenn du das dann weisst, sagen wir

2^{32} \equiv 8

(mod 10) - (das hab ich nicht nachgeprüft; das kann stimmen, muss aber nicht).
Dann ist deine Lösung:

2^{2^{32}} \equiv 2^{8} \equiv 256 \equiv 36 \equiv 3

mod 11

Wenn du oben einen anderen Exponenten bekommst, ist das Resulat natürlich auch anders.

nati001 aktiv_icon

18:40 Uhr, 30.04.2010

danke, das mit mod 10 hab ich nicht gewusst..

aber wenn ich 2³² mod 10 habe ist ja ggT(2,10) nicht 1, also ich würde ja 10 in seine Primfaktoren zerlegen, also 5 und 2, aber was dann?

el holgazán aktiv_icon

19:03 Uhr, 30.04.2010

Du kannst das zwar so machen wie du meinst (mit Zerlegung der 10);
aber du kannst auch einfach so überlegen:

23 \equiv 3

mod 10

125124236 \equiv 6

mod 10

12343 \equiv 3

mod 10

231242 \equiv 2

mod 10

Also ist, wie gesagt, mod 10 einfach die letzte Zahl.

Nun beobachten wir:

2^{2} = 2 \equiv 2

mod 10

2^{2} = 4 \equiv 4

mod 10

2^{3} = 8 \equiv 8

mod 10

2^{4} = 16 \equiv 6

mod 10

2^{5} = 32 \equiv 2

mod 10

2^{6} = 64 \equiv 4

mod 10

2^{7} = . . . 8 \equiv 8

mod 10

2^{8} = 6

mod 10

2^{9} = 2

mod 10

u.s.w.

nati001 aktiv_icon

20:28 Uhr, 30.04.2010

danke, hat geklappt ich bekomm das richitge raus :-)

754742

754455

	Status: nicht eingeloggt	Noch nicht registriert?