Modulo n rechnen

07.06.2008, 21:55

mathe760

Modulo n rechnen

Hallo,

ich würde gerne wissen wie ich hier $\begin{eqnarray*} 23^5\cdot 89^{367}\cdot 113 (mod 5)\equiv 3^5\cdot (-1)^{367}\cdot 3 (mod 5) \end{eqnarray*}$

auf die Rechte Seite komme.

und wie ich von hier $\begin{eqnarray*} 23^5\cdot 89^{367}\cdot 113 (mod 7)\equiv 2^5\cdot (-2)^{367}\cdot 1 (mod 7) \end{eqnarray*}$

auf die Rechte Seite komme.

Ausserdem würde ich gerne wissen, wie ich folgendes noch weiter vereinfachen kann:

$\begin{eqnarray*} 2004^7-6722^{87}\cdot 549\equiv 4^7-2^{87}\cdot 9\equiv 2^{14}+2^{87} (mod10) \end{eqnarray*}$

Bis denn mathe760 Wink

07.06.2008, 22:44

Auf diesen Beitrag antworten »

Die Regel

$\begin{eqnarray*} a\equiv b \mod m \quad\Longrightarrow\quad a^n\equiv b^n \mod m \end{eqnarray*}$

für alle positiven ganzen Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ kennst du doch wohl? Nichts anderes wird da oben bei den Potenzbasen mehrfach angewandt.

Zitat:

Original von mathe760
Ausserdem würde ich gerne wissen, wie ich folgendes noch weiter vereinfachen kann:

$\begin{eqnarray*} 2004^7-6722^{87}\cdot 549\equiv 4^7-2^{87}\cdot 9\equiv 2^{14}+2^{87} (mod10) \end{eqnarray*}$

Es ist $\begin{eqnarray*} 6^n \equiv 6\mod 10 \end{eqnarray*}$ , das kann man wegen $\begin{eqnarray*} 2^4 \equiv 6\mod 10 \end{eqnarray*}$ vorteilhaft nutzen, um die Exponenten 14 und 87 drastisch zu reduzieren.

Zitat:

Signaturvon mathe760
Der Wille ist eine notwendige, aber nicht hinreichende Bedingung für den Erfolg!

Wie sieht denn dein Wille aus, einmal angefangene und dann doch nicht beendete Problemlösungen durchzuziehen? verwirrt

07.06.2008, 22:44

tmo

Auf diesen Beitrag antworten »

Aus $\begin{eqnarray*} a \equiv b \pmod m \end{eqnarray*}$ folgt $\begin{eqnarray*} a^n \equiv b^n \pmod m \end{eqnarray*}$ .

Dann zur letzten Frage: Du könntest z.b. $\begin{eqnarray*} 2^{4n+1} \equiv 2 \pmod {10} \end{eqnarray*}$ benutzen.

07.06.2008, 22:51

Nubler

Auf diesen Beitrag antworten »

erst wurde jedes element modulo n genommen und dann verknüpft.
paar anmerkungen:

$\begin{eqnarray*} a~mod\,n\,=\,m \end{eqnarray*}$

$\begin{eqnarray*} m:\{m\in\mathbb N_0|0\leq m\leq n-1\} \end{eqnarray*}$

in deinen fall ist -1=4 und -2=5

zur letzten: errechne erst das ergebnis von $\begin{eqnarray*} 2^5\,mod\,10 \end{eqnarray*}$ und spalte entsprechende faktoren ab, am schluss ist das solltest du dass zu einer einzigen zahl zusammenziehen können, die mod10 und dann sollt ne einzelne ziffer dastehen

adid: die ersten zwei kann man auch noch ausrechnen

07.06.2008, 22:53

mYthos

Auf diesen Beitrag antworten »

Einfach, weil 23 (mod5) = 3 mod 5 ist, so gilt dies auch für die Potenz.
89 = (-1) mod 5, denn 90 ist ja durch 5 teilbar.
Desgleichen 113 = 110 (mod 5).

Nun ist das Zweite auch klar, denn 23 = 2 (mod 7), 89 = (-2) mod 7, weil 91 durch 7 teilbar ist, usw.

Zum Dritten:

Du kannst die Potenzen geeignet zerlegen und die Restklasse von den Faktoren bestimmen:

Wir verwenden: $\begin{eqnarray*} 2^5 = 32 = 2 (mod \ 10) \end{eqnarray*}$

$\begin{eqnarray*} 2^{14} = 2^5 \cdot 2^5 \cdot 2^4 = 32 \cdot 32 \cdot 16 \end{eqnarray*}$
daher
$\begin{eqnarray*} 2^{14} = 2 \cdot 2 \cdot 6 \ (mod \ 10) = 24 (mod \ 10) = 4 (mod \ 10) \end{eqnarray*}$

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

$\begin{eqnarray*} 2^{87} = (2^5)^{17} \cdot 4 = 2^{17} \cdot 4 \ (mod \ 10) = (2^5)^3 \cdot 4 \cdot 4 \ (mod \ 10) = 8 \cdot 4 \cdot 4 \ (mod \ 10) = 128 (mod \ 10) = 8 (mod \ 10) \end{eqnarray*}$

Das Ganze dann noch zusammenzählen ...

mY+

mY+

08.06.2008, 15:47

mathe760

Auf diesen Beitrag antworten »

Hallo,

ihr habt euch ja alle förmlich auf die Aufgaben gestürzt was smile

.
Es ist schön zu wissen, dass es so viele hilfsbereite Mitglieder hier im Board gibt. Freude

Dennoch bin ich gestern abend selbst nochmal darauf gekommen. Ich habe einfach nicht an die Rechenregeln für Kongruenzen gedacht... Hammer

Nunja ich denke bei der 1. kommt 1 raus, bei der 2. kommt 6 raus und bei der letzten kommt 2 raus stimmt das so?

Nun habe ich mich auch noch mit der Zahl 100! beschäftigt und wollte berechnen, wie die letzten drei Ziffern lauten, dabei bin ich auf folgendes gestoßen:

100! mod 10 ist ja 0, da 10|100
100! mod 100 ist ja 0, da 100|1000
100! mod 1000 ist ja 0, da 1000|100*5*2=1000

Nun habe ich mir überlegt auf wie vielen verschiedenen Arten man mit 100 (n) verschiedenen Faktoren durch herausgreifen von k Faktoren das Produkt 10(100, 1000, 10000,....) erhält. Die restlichen Faktoren die "unbenutzt" bleiben sind dann ja egal, da das ganze dann ja eh Null wird.
Ich hoffe ihr versteht was ich meine verwirrt

!)

Könnt ihr mir diese Frage beantworten?

Bis denn mathe760 Wink

08.06.2008, 16:32

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Nun habe ich mir überlegt auf wie vielen verschiedenen Arten man mit 100 (n) verschiedenen Faktoren durch herausgreifen von k Faktoren das Produkt 10(100, 1000, 10000,....) erhält.

Für festes oder variables k? Mit der originalen Aufgabenstellung hat diese Frage übrigens nicht mehr viel zu tun, auch mit der erweiterten Fragestellung "auf wieviel Nullen endet 100!" nicht.

Zitat:

Original von mathe760
Die restlichen Faktoren die "unbenutzt" bleiben sind dann ja egal, da das ganze dann ja eh Null wird.

Verstehe ich nicht, was du damit meinst - was wird eh Null?

09.06.2008, 17:39

mathe760

Auf diesen Beitrag antworten »

Die Kongruenz wird Null.

Nun mal zu einer anderen Aufgabe im Rahmen meiner Vorbereitungen:

In einem rechtwinkligen Dreieck, wo alle Seitenlängen ganzzahlig sind, hat die eine Kathete die Länge 1994 .
Bestimmen Sie die Länge der Hypothenuse.

Meine Ansätze:

Ich habe erstmal die Gleichung des Pythagoras, die ja gilt, da das Dreieck rechtwinklig ist, aufgestellt

$\begin{eqnarray*} 1994^2+a^2=c^2 \end{eqnarray*}$

Dies wird umgeschrieben in

$\begin{eqnarray*} c^2-a^2=(c+a)\cdot (c-a)=1994^2 \end{eqnarray*}$

Nun habe ich mir überlegt das 1994^2 modulo 8 den Rest 4 gibt, kann man das nicht irgendwie auch für die Linke Seite der oberen Gleichung ausnutzen?

Ich glaube aber nicht, das dies der Sinn der Aufgabe ist, da dies mit einem Beispiel das fast genau diese Struktur hat, ausser das die ganze Zahl auf der rechten Seite eine Primzahl ist, eingeleitet wird. Dort war die Lösung ja sehr einfach zu finden, da die Zahl 389 eben nur die Teiler +-1 und +-389 hat. Wie aber kann ich so vorgehen wenn die Zahl keine Primzahl ist und so viele Teiler hat wie z.B die 1994^2 ?

Bis denn mathe760 Wink

09.06.2008, 17:49

Auf diesen Beitrag antworten »

Im Produkt $\begin{eqnarray*} (c+a)\cdot (c-a) \end{eqnarray*}$ muss sich die Primfaktorzerlegung von

$\begin{eqnarray*} 1994^2 = 2^2 \cdot 997^2 \end{eqnarray*}$

widerspiegeln. Außerdem weiß man noch $\begin{eqnarray*} c+a>c-a>0 \end{eqnarray*}$ . Mit einer kleinen Zusatzüberlegung sollte auch noch klar sein, dass beide Zahlen $\begin{eqnarray*} c+a \end{eqnarray*}$ und $\begin{eqnarray*} c-a \end{eqnarray*}$ gerade sein müssen. Da bleiben dann nicht mehr viele Möglichkeiten der Aufteilung.

09.06.2008, 17:59

mathe760

Auf diesen Beitrag antworten »

Gut vielen Dank Arthur (Ich denke übrigens immernoch über die "Mengen Aufgabe nach und schreibe bald meine Lösung rein).

Was ist mit der "100!-Aufgabe", hast du da einen Gedanken zu wie man das Problem lösen könnte?

Bis denn mathe760 Wink

09.06.2008, 18:11

Auf diesen Beitrag antworten »

Ich erkenne da kein klar umrissenes Problem, darauf hatte ich bereits hingewiesen. Augenzwinkern

09.06.2008, 18:40

mathe760

Auf diesen Beitrag antworten »

Erstmal zu der "1994-Aufgabe" nochmal:

Kannst du mal kommentieren wie du das bei einer Olympiade aufgeschrieben hättest? Ich schreibe es erstmal so wie ich es tun würde:

Da das Dreieck rechtwinklig ist, gilt der Satz des Pythagoras:

$\begin{eqnarray*} 1994^2+a^2=c^2 \end{eqnarray*}$

Dies formt man um zu:

$\begin{eqnarray*} c^2-a^2=(c+a)\cdot (c-a)=1994^2 \end{eqnarray*}$ (1)

Da $\begin{eqnarray*} 1994^2 \end{eqnarray*}$ eine gerade Zahl ist, müssen nach (1) und (c+a)-(c-a)=2a auch (c+a) und (c-a) gerade Zahlen sein.

Mit der Primfaktorzerlegung $\begin{eqnarray*} 1994^2=2^2\cdot 997^2 \end{eqnarray*}$ und c+a>c-a>0 folgt nun $\begin{eqnarray*} c+a=2\cdot 997^2\Rightarrow c=2\cdot 997^2-a \end{eqnarray*}$ und $\begin{eqnarray*} c-a=2\Rightarrow c=2+a \end{eqnarray*}$ .

Zusammen erhält man also:

$\begin{eqnarray*} 2+a=2\cdot 997^2-a \end{eqnarray*}$

und daraus $\begin{eqnarray*} a=994008 \end{eqnarray*}$ und $\begin{eqnarray*} c=994010 \end{eqnarray*}$

Bis denn mathe760 Wink

09.06.2008, 19:21

Auf diesen Beitrag antworten »

Ja so ungefähr. Das hier

Zitat:

Original von mathe760
Da $\begin{eqnarray*} 1994^2 \end{eqnarray*}$ eine gerade Zahl ist, müssen nach (1) und (c+a)-(c-a)=2a auch (c+a) und (c-a) gerade Zahlen sein.

hätte ich zur Sicherheit noch etwas genauer aufgeschlüsselt:

Zitat:

Da $\begin{eqnarray*} 1994^2 \end{eqnarray*}$ eine gerade Zahl ist, muss mindestens einer der beiden Faktoren (c+a) oder (c-a) gerade sein. Da aber auch ihre Differenz (c+a)-(c-a)=2a gerade ist, muss auch die andere der beiden Zahlen ebenfalls gerade sein.

So sollte es wasserdicht sein - man kann nie wissen bei den Korrektoren.

Meine Erfahrung ist: Je niedriger die Stufe, desto pingeliger die Korrektoren. Bei der IMO kann man dann richtig schlampen, solange nur die Idee hinhaut und zur Lösung führt. Big Laugh

10.06.2008, 09:22

mathe760

Auf diesen Beitrag antworten »

Sollte man denn im allgemeinen immer in der 3.Person bei Wettbewerbsaufgaben schreiben?
Und ist das in Ordung mit der Formulierung und den Folge Pfeilen? Müssen das nicht Âquivalenz Pfeile sein?

off topic: Was würdest du mir empfehlen womit ich mich als erstes beschäftigen sollte? Ich habe noch eine ganze Menge Aufgaben Typen vor mir und noch knapp 4 Monate Zeit zum Ûben.

Bis denn mathe760 Wink

10.06.2008, 09:52

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Sollte man denn im allgemeinen immer in der 3.Person bei Wettbewerbsaufgaben schreiben?

Natürlich ist es eine Frage guten Stils, nicht mittendrin immer mal zwischen erster und dritter Person zu wechseln. Solange aber alles nur logisch einwand- und auch zweifelsfrei formuliert ist, wird dir kein Korrektor wegen solcher Ausdrucksfragen einen Strick drehen. Augenzwinkern

Neue Frage »

Antworten »

Modulo n rechnen

Verwandte Themen