Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Große Potenzen Modulo große Primzahlen

Große Potenzen Modulo große Primzahlen

Universität / Fachhochschule

Teilbarkeit

Tags: Teilbarkeit

Timmyboy2411 aktiv_icon

20:43 Uhr, 04.08.2018

Hallo.

Wie ich große Potenzen modulo kleinen Primzahlen oder großen Zahlen mit kleinen Primfaktoren berechnen kann, weiß ich.

Ich verzweifle aber gerade an der Aufgabe

57^{50}

modulo

101

(Ist für das Legendre-Symbol

(\frac{57}{101}))

.

Ich komme auf keine einfache Darstellung und weiß nicht weiter.

Für Hilfe wäre ich sehr Dankbar!

Lieben Gruß,
Tim.

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

abakus

21:31 Uhr, 04.08.2018

Hallo,
nach dem kleinen Satz von Fermat gilt

5 7^{100} \equiv 1 m o d 101

.
Ich habe (u.a. deshalb) die ganz starke Vermutung, dass

5 7^{50} \equiv - 1 m o d 101

gilt.

Timmyboy2411 aktiv_icon

22:08 Uhr, 04.08.2018

Ah, ich habe auch noch was gefunden:

Euler hat gefolgert:

a^{\frac{p - 1}{2}} = \pm 1 mod p

.

Damit ist

57^{50} = 57^{\frac{101 - 1}{2}} = \pm 1 mod 101

. Nur weiß ich nicht wie ich jetzt herausbekomme, ob es

+ 1

oder

- 1

ist?

Ich hab mir dazu überlegt, dass ja, wie du gesagt hast, nach Fermat gilt, dass

a^{φ (n)} = 1 mod n

ist.

wenn ich jetzt nutze, dass

57^{100} = 57^{50} \cdot 57^{50}

ist, und

a \cdot b mod c = (a mod c) \cdot (b mod c),

dann kann ich ja sagen, dass

57^{100} = 57^{50} mod 101

ist. Und da ja

57^{100} = 1 mod 101

ist, muss das auch für

57^{50}

gelten.
Richtig?

Edit:
Okay ne,

- 1 \cdot - 1

ist ja auch 1. Wie komme ich denn an das Vorzeichen?

Lieben Gruß und danke für die Hilfe!
Tim.

ermanus aktiv_icon

10:21 Uhr, 05.08.2018

Hallo,
wenn du das quadratische Reziprozitätsgesetz benutzen darfst,
ist ja alles "verhältnismäßig" einfach.
Ich gehe hier aber mal den "elementaren Weg" und berechne

5 7^{50}

mod

101

direkt.
Also ich fange mal an:

5 7^{50} \equiv (- 57)^{50} \equiv 4 4^{50}

, da

50

gerade ist.
Das ist

\equiv 4^{50} \cdot 1 1^{50} \equiv 1 1^{50}

, da

4

ein Quadrat ist.

1 1^{50} \equiv (- 11)^{50} \equiv 9 0^{50} \equiv 9^{50} \cdot 1 0^{50} \equiv 1 0^{50}

,
da

9

ein Quadrat ist. Ab hier geht es ganz schnell ;-)

Gruß ermanus

Timmyboy2411 aktiv_icon

10:04 Uhr, 06.08.2018

Wenn ich dieses Gesetz richtig verstehe, dann kann man ja jetzt

10^{50} \cdot 1 = 100^{25} \cdot 1 = 1 (mod 101),

100

ein Quadrat ist?

Aber in unserem Skript ist dieses Gesetz nicht aufgeführt

\frac{:}{}

ermanus aktiv_icon

10:32 Uhr, 06.08.2018

Nein, so ist das nicht.

10 0^{50}

wäre

\equiv 1

mod

101

, weil 100 ein
Quadrat ist. Es ist aber

10 0^{25} \equiv (- 1)^{25} = - 1

, also

(\frac{57}{101}) = - 1

, d.h.

57

ist kein Quadrat mod 101.

Melde mich gleich wieder ...

ermanus aktiv_icon

13:13 Uhr, 06.08.2018

Das Argument mit den Quadraten, die man ignorieren kann,
ergibt sich aus dem, was du offiziell weißt.

Die Kongruenz

a^{\frac{p - 1}{2}} \equiv (\frac{a}{p})

ist dir mittlerweile bestimmt bekannt. Und das Legendre-Symbol sagt
bei Wert +1

a

ist Quadrat und bei -1

a

ist Nichtquadrat modulo

p

.
Ist nun

a = b^{2} c

, so folgt

(\frac{b^{2} c}{p}) \equiv (b^{2} c)^{\frac{p - 1}{2}} \equiv b^{p - 1} c^{\frac{p - 1}{2}} \equiv 1 \cdot c^{\frac{p - 1}{2}} \equiv c^{\frac{p - 1}{2}} \equiv (\frac{c}{p}) .

Das ist kein neues oder unbekanntes "Gesetz" und deswegen steht es
auch nicht explizit in deinen Unterlagen.

P.S.: ich warte auf eine Reaktion ...

Timmyboy2411 aktiv_icon

14:59 Uhr, 09.08.2018

Hallo.

Tut mir leid, ich habe die Aufgabe verstanden und vergessen, das mitzuteilen.

Danke!

ermanus aktiv_icon

15:04 Uhr, 09.08.2018

Alles klar !

Gruß ermanus

1435804

1435440

	Status: nicht eingeloggt	Noch nicht registriert?