Hilfe beim berechnen vom Divisionsrest

Neue Frage »

21.04.2005, 17:54	Tinje	Auf diesen Beitrag antworten »
Hilfe beim berechnen vom Divisionsrest Hallo, ich hab Aufgaben gestellt bekommen mit denen ich überhaupt nichts anfangen kann. Ich würde mich freuen wenn sich jemad findet, der mir das anhand folgendem Beispiels mal erklärt. Die anderen löse ich dann lieber selber. Die Aufgabe: Man berechne den Divisionsrest von: $\begin{eqnarray} 7^{2000} \end{eqnarray}$ bei Division durch 13. Vor der 2000 steht noch das griechische Zeichen für das kleine Phi. Grüße, Tina
21.04.2005, 18:00	Egal	Auf diesen Beitrag antworten »
Ist das möglicherweise die phi funktion Edit: hab das nachgeguckt Phi Funktion ist die Anzahl der teilefremden Zahlen. Edit2: Wesentlich vereinfachen lässt sich das Problem auf jedenfall wenn man den kleinen Fermatschen Satz anwendet.
21.04.2005, 19:26	Tinje	Auf diesen Beitrag antworten »
wie bitte??? ich möchte doch nur gezeigt bekommen an dem beispiel wie das funktioniert mit dem divisionsrest. eine andere aufgabe lautete: Man berechne den Divisionsrest von $\begin{eqnarray} 3^{2000} \end{eqnarray}$ bei Division durch 13. Ich wollte es halt erklärt bekommen an der anderen aufgabe weil ich mit dem hoch phi vor der klammer 2000 (aber neben dem phi auf gleicher höhe) nicht zurechtkomme. Ich weiß nix von Funktionen oder so.. mehr steht hier auch nicht.
21.04.2005, 19:50	Egal	Auf diesen Beitrag antworten »
Also das war ne Vermutung von mir weils halt in den Kontext passt. Eulersche Phi-Funktion kannst du hier nachlesen: http://de.wikipedia.org/wiki/Eulersche_%CF%86-Funktion Informationen zum kleinen Fermatschen Satz mit dessen Hilfe ich das Problem vereinfachen würde: http://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz Wenn du dann noch nicht weiter kommst wäre es hübsch wenn du einfach mal sagst wodran es hängt und was genau die Aufgabe war.
21.04.2005, 20:27	Tinje	Auf diesen Beitrag antworten »
Okay dann ganz genau.. das große Thema ist im Moment Zahlentheorie. Und auf meinem Aufgabenzettel steht folgende Aufgabe: Man berechne den Divisonsrest von: (a) 7 hoch [kleines Zeichen für Phi (2000)] bei Division von 13, (b) $\begin{eqnarray} 3^{2000} \end{eqnarray}$ bei Division durch 13, (c) a $\begin{eqnarray} \in \end{eqnarray}$ $\begin{eqnarray} \mathbb N \end{eqnarray}$ bei der Division durch 73 unter Beachtung der beiden Eigenschaften, daß $\begin{eqnarray} a^{100} - 2 \end{eqnarray}$ sowie $\begin{eqnarray} a^{101} \end{eqnarray}$ - 69 durch 73 teilbar sind. So nun hab ich die ganze Aufgabe abgeschrieben. Und ich möchte lediglich an (a) erklärt haben was ich zu tun habe. wie ich vorgehe und vor allem was ich mit dem phi anfange. Im Moment weiß ich einfach nicht wie ich anfangen soll.
21.04.2005, 20:32	Calvin	Auf diesen Beitrag antworten »
Ich kann dir bei der Aufgabe leider nicht helfen. Aber bei LaTeX kann ich dir helfen Ein $\begin{eqnarray} \phi \end{eqnarray}$ wird mit \phi gemacht. Also sieht die Aufgabe a) so aus: Man berechne den Divisonsrest von: (a) $\begin{eqnarray} 7^{\phi(2000)} \end{eqnarray}$ bei Division von 13 Ich vermute mal, dass das phi für eine Funktion steht, die ihr behandelt habt bzw. die allgemein mit dem Buchstaben phi bezeichnet wird. Genug von mir. Jetzt überlasse ich den Thread denen, die Ahnung haben
Anzeige

21.04.2005, 20:38	Egal	Auf diesen Beitrag antworten »
Ich habs ja schonmal angedeutet. die Phi Funktion ist die oben verlinkte eulersche Phi Funktion wobei gilt $\begin{eqnarray} \varphi(n)=\sum_{k\nmid n}1 \end{eqnarray}$ die anzahl der zu n teilerfremden Zahlen ist. Wobei das für Primzahlen besonders einfach ist. Für allgemeine n nutzt man die Multiplikativität der Funktion aus um auf einfache Art einen Wert zu bekommen. Aber in dem Wikipedia Link den du von mir bekommen hast steht das eigentlich zwar knapp aber mathematisch nicht falsch erklärt. Vielleicht fängst du einfach mal damit an $\begin{eqnarray} \varphi(2000) \end{eqnarray}$ zu bestimmen und danach gehen wir zum nächsten Schritt und überlegen wie man den kleinen Fermat anwenden kann um die Berechnung des Rests zu vereinfachen.
21.04.2005, 21:10	Tinje	Auf diesen Beitrag antworten »
okay ich hab nun versucht das phi so auszurechnen wie es in dem link stand..und da 2000 keine Primzajl ist musste ich einen etwas längeren weg wählen und da habe ich dann einfach gerechnet: $\begin{eqnarray} \phi \end{eqnarray}$ (2000) = $\begin{eqnarray} 2^{1} \cdot 10^{3} \end{eqnarray}$ = $\begin{eqnarray} 2^{1-1} (2-1) \cdot 10^{3-1} (10-1) \end{eqnarray}$ = $\begin{eqnarray} 1 \cdot 1\cdot 10^{2} \cdot 9 = 900 \end{eqnarray}$ richtig?
21.04.2005, 21:15	AD	Auf diesen Beitrag antworten »
Falsch, denn 10 ist keine Primzahl. Du musst also so starten $\begin{eqnarray} \varphi(2000)=\varphi(2^4\cdot 5^3)=\ldots \end{eqnarray}$
21.04.2005, 21:16	Egal	Auf diesen Beitrag antworten »
Du musst das komplett in Primfaktoren mit Vielfachheit zerlegen dann kannst du die Formel so verwenden wie du das hier gemacht hast.
21.04.2005, 21:38	Tinje	Auf diesen Beitrag antworten »
$\begin{eqnarray} 2^{4-1} (2-1) \cdot 5^{3-1} (5-1) = 8\cdot 1\cdot 25\cdot 4 = 800 \end{eqnarray}$ ahja..hab ich vergessen mit den primzahlen..so ists nun aber richtig?
21.04.2005, 21:40	Egal	Auf diesen Beitrag antworten »
Jawohl. Jetzt guck dir das andere an zum Thema Fermatscher Satz und überleg wie du das zu deinem Vorteil nutzen kannst.
21.04.2005, 21:51	Tinje	Auf diesen Beitrag antworten »
das versteh ich nun nicht. Was hatd as mit meienr Aufgabe zu tun? und was bedeutet dort dieses mod ständig?
21.04.2005, 21:54	Egal	Auf diesen Beitrag antworten »
Ich dachte du hörst Zahlentheorie na wie auch immer mod ist Der divisions rest als 7mod3=1 zb manchmal schreibt man das auch als 7=1(3) dann aber mit dem 3-Strich =
21.04.2005, 22:09	Tinje	Auf diesen Beitrag antworten »
das $\begin{eqnarray} \equiv \end{eqnarray}$ kenne ich. Also könnte ich das jetzt so machen dass ich die 900 durch die 7 dividiere und was übrigbleibt ist dann der divisionsrest? ne das geht nicht weil ich es ja durch 13 teilen soll..
21.04.2005, 22:12	Egal	Auf diesen Beitrag antworten »
Satz nochmal kurz $\begin{eqnarray} a^p=a~mod~p \end{eqnarray}$ jetzt musst du mal gedankliche die 800 so aufteilen das du das als $\begin{eqnarray} a^{p-1}\cdot ... \cdot a^{p-1} \end{eqnarray}$ schreiben kannst weil die sollten wenn da gibts noch ne einschränkende Bedingung an a und p jeweils 1 ergeben.
22.04.2005, 12:30	Tinje	Auf diesen Beitrag antworten »
Guten Morgen, also da ich mit der obigen Aufgabe überhaupt nicht wieter komme, hab ich mich nun erstmal mit eienr neuen Beschäftigt zum Thema Divisionsrest. Die Aufgabe heißt: Man löse in $\begin{eqnarray} \mathbb Z \end{eqnarray}$ : (a) 33x $\begin{eqnarray} \equiv \end{eqnarray}$ 398 (691) durch Zufall also durch probieren bin ich draufgekommen dass $\begin{eqnarray} 33 \cdot 33 \end{eqnarray}$ = 1089 ergibt und 1089 : 691 = 1 Rest 398 aber bei (b) schaffe ich es noch nicht einmal durch probieren und auch mit den erweiteren euklidischen Algorithmus komme ich nicht weiter... (b) 527x $\begin{eqnarray} \equiv \end{eqnarray}$ 51 (1309)

Neue Frage »

Antworten »

Hilfe beim berechnen vom Divisionsrest

Verwandte Themen