Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Aufgabe zur modularen Arithmetik

Aufgabe zur modularen Arithmetik

Universität / Fachhochschule

Tags: Exponent, Modulare Arithmetik

Sllash aktiv_icon

11:25 Uhr, 02.12.2022

Hallo!

Ich musste folgende Aufgabe berechnen:

(2^{50} + 38) mod 7

Und habe dazu anfangs folgenden (falschen) Lösungsweg gewählt:

Es gilt

2^{50} = {(2^{3})}^{\frac{50}{3}}

\Rightarrow ({(2^{3})}^{\frac{50}{3}} + 38) mod 7

= (8^{\frac{50}{3}} + 3) mod 7

Regel:

(a^{b}) mod c = ({(a mod c)}^{b}) mod c

\Rightarrow (1^{\frac{50}{3}} + 3) mod 7

= (1 + 3) mod 7 = 4 mod 7 = 4

Ich frage mich nun, wo liegt hier der Fehler?
Ich habe einen anderen, in meinen Augen auch ähnlichen Lösungsweg, welcher mir das richtige Ergebnis liefert:

(2^{50} + 38) mod 7

= ({(2^{3})}^{16} \cdot 2^{2} + 38) mod 7

= ({(8)}^{16} \cdot 2^{2} + 3) mod 7

= (1^{16} \cdot 2^{2} + 3) mod 7

= (4 + 3) mod 7 = 7 mod 7 = 0

Ich hoffe hier kann mir jemand helfen und ich bedanke mich bereits im Voraus!

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:

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

Potenzfunktionen - Einführung

HAL9000

12:40 Uhr, 02.12.2022

Der Fehler ist, dass du aus

a \equiv b mod m

die Kongruenz

a^{k} \equiv b^{k} mod m

nur für GANZZAHLIGE (!) Exponenten

k

folgern darfst!!! Eigentlich erschreckend, dass du dies ignorierend rumrechnest:

Denn dann könnte man ja einfach folgerdermaßen rechnen: Für alle Primzahlen

p

und alle nicht durch

p

teilbaren Zahlen

a

sowie ALLE (!) ganzzahligen Exponenten

k

gilt

a^{k} = {(a^{p - 1})}^{\frac{k}{p - 1}} \overset{?}{\equiv} 1^{\frac{k}{p - 1}} = 1 mod p

Offensichtlich ziemlicher Humbug.

Richtig ist selbstverständlich die Hilfsrechnung

2^{50} = 2^{3 \cdot 16 + 2} = 8^{16} \cdot 2^{2} \equiv 4 mod 7

michaL aktiv_icon

12:43 Uhr, 02.12.2022

Hallo,

mit gebrochenen Exponenten kannst du hier nicht viel anfangen (sofern du nicht weißt, was du tust).

Du könntest deine Idee wie folgt verarbeiten:

2^{50} = 2^{2 + 3 \cdot 16} = 2 \cdot {(2^{3})}^{16} \equiv 2

mod 7.

> Ich frage mich nun, wo liegt hier der Fehler?

Darin, dass du eben nicht weißt, was du tust.
Gebrochene Exponenten verhalten sich hier anders als bei den reellen Zahlen. So ist etwa eine(!) Lösung der Gleichung

x^{3} \equiv 1

mod 7 die Zahl

x = 2

. Die anderen beiden sind

x = 1

und

x = 4

. Daran erkennst du, dass die "Wurzeln" hier schwieriger sind.

Mfg Michael

PS: Uups, bitte posting ignorieren

Sllash aktiv_icon

13:11 Uhr, 02.12.2022

Vielen Dank HAL9000 und michaL!

Mir war tatsächlich nicht bewusst, dass ich die Kongruenz

a^{k} \equiv b^{k} mod m

nur für ganzzahlige Exponenten

k

folgern darf. Vielen Dank für eure Erklärungen und die Beispiele, die haben mich wirklich sehr weiter gebracht! :-)
So ein Fehler wird mir in Zukunft hoffentlich nicht mehr unterlaufen.

1564357

1564345

	Status: nicht eingeloggt	Noch nicht registriert?