Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Modulo Rechnen mit hohen Exponenten

Modulo Rechnen mit hohen Exponenten

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

anonymous

14:47 Uhr, 09.07.2019

Ich habe mal ne alte Frage bezüglich modulo rechnen

Die Aufgabe lautet:

a)

Auf welchen Rest führt die Division von

143^{1000}

durch

12

b)

Zeigen Sie:

{(a + b)}^{14} = a^{14} + 2 a^{7} b^{7} + b^{14} mod 7 (a, b

ganze Zahlen)

Ich weiß, wie die Rechnung bei

a)

gemeint ist; aber gibt es irgendwelche allgemeinen Tipps, wie man schnell und einfach bei unterschiedlichen Basen und Exponenten zur Lösung kommt?

Bezüglich Aufgabe

b)

wie kann man da vorgehen?

Danke

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:
Exponentialfunktion (Mathematischer Grundbegriff)
Potenzregeln (Mathematischer Grundbegriff)

supporter aktiv_icon

15:07 Uhr, 09.07.2019

a)

Spontan fällt mir dazu ein:

143 = 144 - 1 = 12^{12} - 1

Vlt. hilft das weiter.
Modulo ist nicht so mein Ding. :-)

ermanus aktiv_icon

15:14 Uhr, 09.07.2019

Hallo,
supporter hat schon gut vorgearbeitet:
er hat sich nur verschrieben: nicht

1 2^{12} - 1

, sondern nur

1 2^{2} - 1

Nun musst du nur noch

12 \equiv 0

mod

12

nutzen.
Gruß ermanus

ermanus aktiv_icon

15:21 Uhr, 09.07.2019

zu b):
für jede Primzahl

p

und beliebige ganze

a, b

gilt

(a + b)^{p} \equiv a^{p} + b^{p}

mod

p

.
Das habt ihr sicher schon irgendwo nachgewiesen.

anonymous

15:26 Uhr, 09.07.2019

Aber wieso kann man einfach sagen, dass

143^{1000}

den selben Rest wie

12^{2} - 1

hat?
Weil ich meine, geht das mit jedem Exponenten? Denn

143^{999}

hat doch beispielsweise nen anderen Rest oder?

Blicke da nicht ganz so durch, wieso man das so einfach sagen kann.

Und was ist denn dann eurer Ansicht nach der Rest? die 1 die übrig bleibt, oder? Denn

12^{2} mod 12

geht ja auf. Das verstehe ich schon, aber geht das immer?

143^{8476543456765432}

also auch? (Mal so wild gesagt)
Welche Gesetze gibt es denn da?

pivot aktiv_icon

15:28 Uhr, 09.07.2019

Bei der a) hilft der Binomische Lehrsatz:

14 3^{1000} = (144 - 1)^{1000} = \sum_{k = 0}^{1000} (\binom{1000}{k}) \cdot 14 4^{k} \cdot (- 1)^{1000 - k}

Alle Summanden, bis auf den mit dem Index

k = 0

, sind durch 12 teilbar. Das wäre jetzt mein (verspäteter) Vorschlag gewesen.

Gruß

pivot

Edddi aktiv_icon

15:31 Uhr, 09.07.2019

. .

. oder so:

143^{1} mod 12 = 11

143^{2} mod 12 = 11^{2} mod 12 = 1

143^{3} mod 12 = 11^{2} mod 12 \cdot 11^{1} mod 12 = 1 \cdot 11 = 1

143^{4} mod 12 = 11^{2} mod 12 \cdot 11^{2} mod 12 = 1 \cdot 1 = 1

Somit

143^{2 n} mod 12 = 1

und

143^{2 n + 1} mod 12 = 11

;-)

abakus

15:32 Uhr, 09.07.2019

Bekannterweise ist

(a + b)^{14} = (\binom{14}{0}) a^{14} + (\binom{14}{1}) a^{13} b^{1} + (\binom{14}{2}) a^{12} b^{2} + (\binom{14}{3}) a^{11} b^{3} + \dots + (\binom{14}{1}) a^{1} b^{13} + (\binom{14}{14}) a^{0} b^{14}

.
Wenn sich das nun mod 7 so wie in der Aufgabe b) vereinfachen sollte, sind die meisten verwendeten Binomialkoeffizienten wohl durch 7 teilbar.
Einzige Ausnahme:

(\binom{14}{7})

abakus

15:36 Uhr, 09.07.2019

@Edddi
Bei der dritten Potenz hast du 1 statt 11 geschrieben.

(Ich finde dein Vorgehen sowieso unästhetisch.
Warum verwendest du 11, wo doch -1 viel schöner ist?)

abakus

15:39 Uhr, 09.07.2019

@ermanus:
Das erklärt nicht das Auftreten von

2 a^{7} b^{7}

ermanus aktiv_icon

15:48 Uhr, 09.07.2019

(a + b)^{14} = ((a + b)^{7})^{2} \equiv (a^{7} + b^{7})^{2} = (a^{7})^{2} + 2 a^{7} b^{7} + (b^{7})^{2} = a^{14} + 2 a^{7} b^{7} + b^{14}

abakus

15:51 Uhr, 09.07.2019

Das erklärt es dann doch.
;-)

Ohne diese Idee hätte man zeigen müssen, dass

(\binom{14}{7}) \equiv 2 m o d 7

gilt.

ermanus aktiv_icon

15:53 Uhr, 09.07.2019

Zu a):

14 3^{1000} = (1 2^{2} - 1)^{1000} \equiv (- 1)^{1000} = 1

mod

12

.
Bei der Addition und bei der Multiplikation geht doch Kongruentes in
Kongruentes über. Das ist doch gerade der SINN der ganzen Kongruenzrechnung.

anonymous

16:27 Uhr, 09.07.2019

Schön und gut, dass ihr mir hier die Aufgaben vorrechnet. Aber die Lösungen brauche ich nicht, viel mehr geht es mir um Gesetze, Regeln und so weiter. Eben die Intention hinter der Modulrechnung.

wie kann man das verallgemeinern.

Ihr sagt jetzt, dass

143^{1000}

den selben Rest hat wie

{(144 - 1)}^{1000}

und das den selben Rest wie

{(12^{2} - 1)}^{1000}

bei Teilung durch

12

.

Kann man dann einfach

{(12^{2})}^{1000} mod 12

als Rest 0 "ausklammern"? Dann bleibt ja

{(- 1)}^{1000}

übrig, welches den Rest 1 bei Teilung durch

12

hat.

Also ist zurückzuführen, dass

143^{1000}

den Rest 1 hat.

Aber wie wäre es, wenn ich jetzt beispielsweise

143^{1000} mod 13

habe und den Rest bestimmen soll?
Die

144

hat sich mit der

12

ja angeboten, die

13

beispielsweise nicht direkt.

Dann hätte ich - nach dem oben von euch geschriebenen Weg - ja:

{(143)}^{1000}

hat den selben Rest wie

{(169 - 26)}^{1000}

und das den selben Rest wie

{(13^{2} - 26)}^{1000}

bei Teilung durch

13

. Dann kann ich die Klammer einfach auseinanderziehen und sagen, dass

{(13^{2})}^{1000}

keinen Rest hat und

26

bei Teilung durch

13

ebenfalls keinen Rest?

Bräuchte mal ne Erklärung, keine Rechnung. Eine verständliche Erklärung dazu, weil sich das Modulthema einfach nicht schön ansehen lässt.

ermanus aktiv_icon

16:34 Uhr, 09.07.2019

Du hast bei der

13

jetzt doch folgende Situation:

143 = 11 \cdot 13

, also durch

13

teilbar, dann ist natürlich
erst recht

14 3^{1000}

durch 13 teilbar, ergibt also den Rest

0

.
Formal:

14 3^{1000} = (11 \cdot 13)^{1000} \equiv 0^{1000} = 0

mod

13

anonymous

16:37 Uhr, 09.07.2019

Hab ich nicht dran gedacht :-D)

nehmen wir die

144^{1000} mod 13

Ich verstehe halt nicht, wie man einfach so die hoch tausend weglassen kann...

Wie sieht es mit nicht so schönen Exponenten aus:

144^{738} mod 13

ermanus aktiv_icon

16:38 Uhr, 09.07.2019

Zu deinem

1 3^{2} - 26

:
Das mit dem einfach die Klammer auseinander ziehen, ist im Allgemeinen
sicher keine gute Idee, aber folgendes

1 3^{2} - 26 \equiv 0 - 0 = 0

mod

13

ermanus aktiv_icon

16:47 Uhr, 09.07.2019

OK. Nehmen wir das Beispiel:
es ist

144 \equiv 1

mod

13

,
also:

14 4^{738} \equiv 1^{738} = 1

mod

13

.
Ich nehme mal einen kleineren Exponenten
und eine andere Basis, so dass man mehr erkennen kann:

14 7^{3} = 147 \cdot 147 \cdot 147 (*)

Nun ist aber

147 \equiv 4

mod

13

.
Das Produkt auf der rechten Seite von

(*)

ist (da bei Produkten Kongruentes
in Kongruentes übergeht) dann

\equiv 4 \cdot 4 \cdot 4 = 16 \cdot 4 \equiv 3 \cdot 4 = 12 \equiv - 1

mod

13

.

P.S.: es wird nicht einfach "hoch

1000

" weggelassen,
sondern

(- 1)^{1000}

ausgerechnet, was ja aber wohl sofort

1

ergibt.

anonymous

17:05 Uhr, 09.07.2019

144^{738} mod 13

\Rightarrow 144^{738}

≡

1^{738} = 1 mod 13

.
1 hat offensichtlich den selben Rest wie

144

bei Teilung durch

13

. Kann daraus dann automatisch geschlussfolgert werden, dass

144

mit einem beliebigen Exponenten ebenfalls den selben Rest bei Teilung durch

13

hat wie 1 mit dem selben beliebigen Exponenten?

Also kann man sagen, dass wir die erste Basis (aus der Aufgabe) uns anschauen und den Exponenten erstmal nicht und dann eine möglichst kleine Zahl

(\in

diesem Fall die 1 suchen), die bei Teilung durch die selbe Zahl den Rest hat?

Also

122 mod 11

hat sozusagen den selben Rest wie

1 mod 11

. Stimmt ja dann erstmal.

Dann schauen wir uns die kleinere Zahl an und rechnen da den Rest aus, richtig? Bei der 1 ist es ja dann

= 1

.
Wenn das so ist, hätte ich den Teil auf jeden Fall schon verstanden.

(Gilt das immer? also egal welchen Exponenten wir haben, der Rest würde sich nie verändern?) (Hoffe du verstehst die Aussage)

147^{3} =

147⋅147⋅147

(\cdot)

Nun ist aber

147

≡

4 mod 13

.
Hier schauen wir uns also erstmal nur den Rest von der

147

an, also die 4. Ich weiß, da steht eigentlich nicht der Rest, aber 4 durch

13

geteilt hat den selben Rest)

Das Produkt auf der rechten Seite von (∗) ist
≡

4 \cdot 4 \cdot 4 = 16 \cdot 4

≡

3 \cdot 4 = 12

≡ −1

mod 13

\to

Diesen Schritt verstehe ich noch nicht.. wie kommst du auf

4 \cdot 4 \cdot 4

etc.?

Wie macht man eigentlich das kogurentzeichen?

ermanus aktiv_icon

17:15 Uhr, 09.07.2019

ich habe in

147 \cdot 147 \cdot 147

jeden Faktor

147

durch die zu

147

kongruente Zahl

4

ersetzt
und bekomme so

4 \cdot 4 \cdot 4

pivot aktiv_icon

20:43 Uhr, 09.07.2019

@Looris96

Hast du dir mal meine Erklärung mit dem Binomischen Lehrsatz angeschaut?

anonymous

20:49 Uhr, 09.07.2019

@pivot

Ja, nur soll die Aufgabe mit der modulo und Kongruenz Rechnung absolviert werden, aber dennoch danke! :-)
Werde sie mir morgen mal genauer anschauen und ggfs nochmal was fragen

Schönen Abend noch! :-)

Edddi aktiv_icon

22:45 Uhr, 09.07.2019

. .

. am ästhetischsten finde ich:

143^{1000} mod 12 = {({({({({({(143 mod 12)}^{2})}^{2})}^{2})}^{5})}^{5})}^{5} = {({({({({(1)}^{2})}^{2})}^{5})}^{5})}^{5} = 1

P . S . :

habe die ganzen anderen "mods" mal weggelassen.

;-)

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

1475569

1475508

	Status: nicht eingeloggt	Noch nicht registriert?