Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Hilfeee Zahlentheorie

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Klassen 8-10 » Arithmetik » Hilfeee Zahlentheorie « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 07. Mai, 2000 - 10:55:   Beitrag drucken

Ich nehme bald an soeinem Mathewettbewerb teil. Leider habe ich gestern erfahren dass da auch ein Beispiel aus dem Bereich Zahlenbereich kommt. Davon hab ich natürlich noch überhaupt keine Ahnung. Ich weiß nur dass es um Teilbarkeitsregeln usw. Bei der Zahlentheorie kommt immer irgendwas mit modolus oder modi was vor. Ich hab leider null Ahnung davon. Es wäre wirklich nett wenn mir irgend jemand helfen könnte.

Danke!!!!!
Rainer
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Mai, 2000 - 10:28:   Beitrag drucken

Hi Anonym,
Modulo-Rechnen ist Rechnen mit Resten, wobei alles natürliche Zahlen bleiben.
Beispiel: Rechnen modulo 3.
Es ist einleuchtend, daß irgendeine beliebige nat. Zahl, wenn sie durch 3 geteilt wird, entweder den Rest 0 oder den Rest 1 oder den Rest 2 hat.
Ist n ein Vielfaches von 3, also n=3,6,9,12,15,18,..... , so ist der Rest nach Div. durch 3 eben Null (klaro), und für diesen simplen Sachverhalt wird geschrieben:

n mod 3 = 0

Bei den Zahlen 4,7,10,13,16,19,... ist nach Div. durch 3 der Rest stets 1, also ist bei den Zahlen der Form m = 3*irgendwas + 1

m mod 3 = 1

Bleiben noch die Zahlen der Form "p = 3*irgendwas + 2", also 5,8,11,14,...... Hier ist

p mod 3 = 2

Die Reste können nur 0, 1, 2 sein. Den Rest 3 kann es hier nicht geben. Ich kann zwar schreiben "18=5*3 + 3", aber hier ist nicht fertig dividiert worden, richtig ist "18=6*3 + 0", also 18 mod 3 = 0.

Resultat: alle natürlichen Zahlen sind in drei "Kisten" gepackt: die mit Rest 0, Rest 1 bzw. Rest 2. Diese 3 Kisten sind MENGEN. Sie haben nichts gemeinsam (Durchschnitt = leere Menge), zusammengeworfen ergeben sie ALLE natürlichen Zahlen (Vereinigung).

Soweit das Prinzip. Wichtig: vorher muß immer der Teiler festgelegt werden.

Anderes Beispiel: mod 2.

Hier gibt es die Reste 0 und 1 (gerade und ungerade Zahlen)

Unsere Stunden auf der Uhr sind ein Modell für "mod 12", die Minuten für "mod 60". Unsere Wochentage sind ein Beisp. für "mod 7".

Ein Kreis hat einen Mittelpunktswinkel von max. 360 Grad (Vollkreis). Das wäre ein Beispiel für "mod 360".

Noch etwas zur Terminologie, am Beispiel der Zahl 8.

N[0] = {n/ 8 teilt n} = {8, 16, 24, ...}
N[1] = {n/ n:8 hat Rest 1} = {n/ 8 teilt (n-1)} = {9, 17, 25, ...}
N[2] = {n/n:8 hat Rest 2} = {10, 18, 26, ...}

usw. usw. usw. bis

N[7] = {n / n:8 hat Rest 7} = {15, 23, 31, ...}

Die Mengen heißen auch RESTKLASSEN modulo 8.

Du siehst: ist A eine nat. Zahl, so liefert die "mod A" Rechnung die Restklassen
N[0], N[1], N[2], ..., N[A - 1]. Das sind genau A Klassen.

Teilbarkeit behandelt eigentlich immer nur N[0].

Hilfts ein wenig? Ciao.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

franz
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Mai, 2000 - 11:17:   Beitrag drucken

Und eine kurze Liste von Teilbarkeitsregeln? ;-)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 08. Mai, 2000 - 18:08:   Beitrag drucken

Danke das hat mir bereits wirklich geholfen. Doch ich hätte noch eine Frage und eine Bitte:
1) Kann ich das mit dem Ti 92 auch rechnen
2) Ich würde das gerne ausprobieren finde jedoch keine Übungsbeispiele, deswegen wäre ich für ein paar Beispiele sehr dankbar (Ein Musterbeíspiel wäre genial) ES IST ZIEMLICH SEHR DRINGEND

Nochmals Danke
Rainer
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 09. Mai, 2000 - 09:36:   Beitrag drucken

Hi Anonym,
ich bin der mit dem "modulo-Text".

Zu 1: keine Ahnung.

Zu 2: außer den konkreten Beispielen oben (Wochentage, Stunden, ...) fällt mir nix aus der Praxis ein. Aber vielleicht hilft folgendes weiter, ohne daß es Dich zur Verzweiflung bringen soll.

Beispiel: mod 4 Rechnen. Restklassen sind
R[0] = {4,8,12,16,...} (Rest immer 0)
R[1] = {5,9,13,17,...} (Rest immer 1)
R[2] = {6,10,14,18,...} (Rest immer 2)
R[3] = {7,11,15,19,...} (Rest immer 3)

R[5] = R[0] müßte klar sein.

Aus Faulheit schreibe ich ab jetzt
R0 statt R[0]
R1 statt R[1]
R2 statt R[2]
R3 statt R[3]
Du solltest das mit den eckigen Klammern beibehalten - Dein Lehrer wird beeindruckt sein.

Die Mengen R0 ... R3 heißen Äquivalenzklassen, ihre Elemente Repräsentanten. Das deshalb, weil irgendein beliebiges Element einer Klasse alle anderen mit repräsentiert. Ansonsten sind das etwas schwerfällige Namen, mehr nicht, bringen also Lehrer zum Staunen.

Also: 4 ist ein Repräsentant von R0, ebenso 48, aber nicht 9. 9 ist Repräsentant R1. Soweit klar?

"12 ist Repräsentant von R0" ist in der Mengenformulierung dasselbe wie "12 ist Element von R0".

Soweit vorweg. Der CLOU besteht jetzt darin, daß man mit diesen Klassen R0, R1, R2, R3 (modulo 4) RECHNEN kann. Und zwar so:

Was ist z.B. R1+R2? Nehme dazu irgendeinen Repräsentanten aus R1 und R2, also etwa 5 aus R1 und 6 aus R2. Deren ganz normale Summe ist 5+6=11, was, wie zu erwarten war, zu R3 gehört, weil 11=2*4+3 ist. 3 ist der Rest.

Kurz: R1+R2 wird einfach dadurch ermittelt, daß LEDIGLICH DIE RESTE in den beiden Klassen normal addiert werden. R1+R2=R3.

Achtung: links und rechts stehen MENGEN. Die "Addition" R1+R2 ist also, genau gesehen, etwas anderes als unsere Zahlenaddition. Puristen malen um das Pluszeichen einen kleinen Kreis herum, um das anzudeuten.

R1+R3 ist eigentlich R4, aber das ist bei "mod 4 Rechnung" dasselbe wie R0. Kurz: R1+R3=R0. Das muß wirklich klar sein (rechne mit ein paar Repräsentanten aus R1 und R3. Z.B. ist 9+11=20 und 20 ist Element von R0, da Vielfaches von 4.

Resultat: alles, was über R3 hinausgeht, "kippt zurück": R4 = R0, damit R5 = R1, R6 = R2, R7 = R3, R8 = R0, .......

Und damit haben wir eigentlich alles, was wir für eine Additionstabelle brauchen.

Eine Vorüberlegung noch: R0+R0=R0, R1+R0=R1, R2+R0=R2 und R3+R0=R3. Das heißt: eine Addition einer Klasse mit R0 ändert nichts. Das ist genau so wie bei normalen Zahlen: die Addition von Null ändert nichts.

+ | R0 R1 R2 R3
--------------------------
R0 | R0 R1 R2 R3
R1 | R1 R2 R3 R0
R2 | R2 R3 R0 R1
R3 | R3 R0 R1 R2


Es gibt ja Lehrer, die ihre Schüler bereits in der Mittelstufe mit dem Begriff "Gruppe" quälen, wenn Du ihn kennst hilft's, aber es geht auch ohne. Folgendes fällt bei der Additionstabelle auf:

- Ausgang sind die Klassen R0, R1, R2 und R3. Egal, welche Klassen addiert werden, das Ergebnis ist IMMER wieder eine dieser Klassen. Die Addition führt niemals zu irgendwelchen neuen Mengen (das liegt an dem "Zurückkippen"). (Gurus sagen dazu, daß die Addition "abgeschlossen" ist).

- Du kennst Folgendes von den natürlichen / ganzen Zahlen: (a+b)+c = a+(b+c). Nach der regel, daß immer zuerst die Klammer berechnet werden soll, heißt das: die Reihenfolge, in welcher addiert wird, ist egal. Es kommt immer dasselbe heraus. (Diese Eigenschaft der Addition schimpft sich "assoziativ")

- Es gibt eine "Nullklasse", die an dem Ergenis einer Addition nichts ändert. Das ist R0. R0 plus irgendeine Klasse liefert immer diese Klasse. (Gurus: "Nullelement").

- Von den normalen ganzen Zahlen kennst Du, daß es zu JEDER Zahl (etwa 86) IMMER GENAU EINE andere Zahl gibt, die, zu 86 addiert, Null ergibt (das ist hier -86). So etwas gibt es hier auch, und da hilft die Tabelle. Beispiel:
R3 + ??? = R0. Laut Tabelle ist ??? dasselbe wie R1. R1 ist das "Umkehrelement" oder das "Inverse" von R3. Ebenso ist (vgl. Tabelle) R3 das Inverse von R1. ("Invers" klingt gut, gelle? Zeigs dem Lehrer!)

(P.S.: Damit sind die mod-4-Restklassen eine "additive Gruppe").

Eine Eigenschaft noch: die Addition kann vertauscht werden, z.B. ist R1+R3 = R3+R1 (die Addition ist "kommutativ").

In der Hoffnung, daß Du Deinen Monitor noch nicht zertrümmert hast, der zarte Hinweis, daß so etwa Analoges zur Multiplikation hier nicht klappt. Die Analogie wäre so: R1 * R3 wird gebildet, indem ein Element aus R1, eins aus R3 genommen wird und die Reste multipliziert werden. Da 1*3=3 ist, liefert das ein Element aus R3, also R1*R3=R3.
Aber was soll für die Multiplikation das "neutrale Element" sein? Bei den normalen Zahlen und der normalen Multiplikation ist das die 1. Wäre hier also R1. Aber die Inversen?

Zwei Zahlen aus R3 haben jeweils den Rest 3. Wegen 3*3=9 aus R1 ist also R3*R3=R1 (R3 ist sozusagen zu sich selbst invers). Aber R2 hat kein Inverses. Eine Zahl aus R2 hat den Rest 2 und es gibt keine Restklasse, die multipliziert mit R2, die Restklasse R1 liefert. Zu lösen wäre nämlich "2*unbekannt=1".
2*1 = 2 liefert R2 (nicht R1)
2*2 = 4 liefert R0 (nicht R1)
2*3 = 6 liefert R2 (nicht R1)

So, cut. Du kannst dasselbe mal versuchen mit "mod 3" oder "mod 5". Additiv analog gerechnet, liefert das immer die hier bei "mod 4" festgestellten Eigenschaften.

Ciao.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 09. Mai, 2000 - 17:33:   Beitrag drucken

Hallo

Gleich im voraus einmal DANKE für die wirklich ausführliche und großartige Erklärung. Entschuldigung für meine Hartneckigkeit aber eine Frage hätte ich noch und zwar: Das ganze ist zwar schön und gut aber was bringt mir das, welche REchnungen könnten so zu lösen sein und wie kann ich das in einem konkreten Beispiel verwenden?

Ich will wirklich nicht lästig sein, aber es würde mich interessieren

Rainer
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Anonym
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 10. Mai, 2000 - 08:32:   Beitrag drucken

Hi Anonym,
tja, grübel ... ich muß leider passen, was die Beispiele des "Modulo-Rechnens" angeht. Ich denke, daß das bloß Fingerübungen sind, um zu verstehen, was Äquivalenzklassen sind. Und die sind tatsächlich wichtig, allerdings in anderen Mathe-Bereichen.

Ich weiß nicht, ob's Dir weiterhilft, aber ich kanns nur an einem ganz anderen Beispiel von Äqu.klassen erläutern.

Du kennst die natürlichen Zahlen 1, 2, 3, .... Kommt schon mal die (indische) Erfindung der Null hinzu, um in unserem dezimalsystem sowas wie 11 und 101 unterscheiden zu können.

Wenn Du darin addieren willst, geht das zwar, aber Dir fehlen die Umkehrelemente (Inverse). Denn

8 + ??? = 0

ist nur mit -8 zu lösen, was keine natürliche Zahl ist.

Also erweitert man die nat. Zahlen zu den ganzen Zahlen - und jetzt klappt alles mit der Addition.

In diesen ganzen Zahlen Z stößt man aber auf ein ähnliches Problem, wenn man multiplizieren will. Denn z. B.

8 * ??? = 1

liefert 1/8, was keine ganze Zahl, sondern ein Bruch ist. Also braucht man die Brüche, die rationalen Zahlen Q. Soweit klar, aber Puristen sehen das anders.

Denn nimm etwa den Bruch 3/2. Davon gibt es unendlich viele, wie Du durch Erweitern mit 2, 3, 4, 5, ... sofort siehst. 6/4, 9/6, 12/8, 15/10 ... stellen alle denselben Bruch 3/2 dar, obwohl jeweils Zähler für sich und Nenner für sich verschieden sind.

Ausweg: 3/2 wird als Äquivalenklasse gesehen,
[3/2] = {a/b | a=N*3 und b=N*2 mit N nat. Zahl} und dann, hinterher, gesagt, daß es reicht, einen Repräsentanten aus dieser Klasse zu nehmen. Sozusagen durch den Rücken durch die Brust ins Auge.

Das ist dünn als Antwort auf Deine Frage, aber vielleicht weiß einer der geneigten LeserInnen bessere Antworten.

Ciao, Heino Stern
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 10. Mai, 2000 - 18:45:   Beitrag drucken

Hi

Das ganze kannst Du bei Teilbarkeitsregeln und so weiter verwenden, uebrigens, dass Du per Internet geheime Nachrichten verschicken kannst, ist dank der Modulo-Rechnung ueberhaupt moeglich, es hat naemlich das bisher sicherste Verschluesselungsverfahren geliefert

Der Vollstaendigkeit halber muss ich erwaehnen, dass die Multiplikation doch klappt, vorausgesetz, die Modulo-Zahl ist eine Primzahl, ansonsten ist es aber immerhin ein Ring

Gruesse SpockGeiger
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Rainer Ammer (007)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 12. Mai, 2000 - 14:30:   Beitrag drucken

Du meinst wohl wahr das die sicherste Verschlüsselungsmethode. derzeit ist Quantenkryptografie der lezte Schrei. Denn sobald jemand einen Abhörversuch startet ändert sich der Code automatisch. (dadurch allerdings sehr anfällig gegenüber Störungen).
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 12. Mai, 2000 - 22:57:   Beitrag drucken

Eine typische Aufgabe zur Modulo-Rechnung:

Welchen Rest gibt 10001000, wenn man es durch 13 teilt?

(Eine Aufgabe, die erstmal auch mit dem TI 92 nicht zu bewerkstelligen ist, aber mit etwas Übung sogar mit Bleistift und Papier lösbar.)

So geht's:

Gesucht: 10001000 mod 13.

Hilfssatz:
(a mod n) * (b mod n) = ab mod n.

Also
10001000 mod 13
= 121000 mod 13 [da 1000/13 den Rest 12 lässt]
= 144500 mod 13
= 1500 mod 13 [da 144/13 den Rest 1 lässt]
= 1.

10001000 ist also irgendwas mal 13 plus 1.

Ein weiteres wichtiges Werkzeug ist der folgende Satz:
(a mod n) + (b mod n) = a+b mod n.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

ZahlReich-Technik
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 19. September, 2000 - 22:06:   Beitrag drucken

Der Downloadbereich (um aktuelle Themen aus dem Archiv offline zu speichern und zu verwenden), den wir in Kürze implementieren, wird auch zugriffsgeschützt sein. Der Wächter ist ein Javascript, das mithilfe der oben geschilderten Modulo-Rechnung verschlüsselt.

Das nur zum Thema "praktische Anwendung".

ZahlReich-Technik
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

paul
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 06. November, 2000 - 12:29:   Beitrag drucken

Hallo an Alle.

Ich sitze vor einer Hausaufgabe, die ich nicht gelöst bekomme.
Aufgabe:
Zeige: In der Primfaktorzerlegung von 100! kommt die Primzahl 3 mit dem Exponenten 48 vor.
Kann mir jemand helfen?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Andre
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 06. November, 2000 - 13:02:   Beitrag drucken

Nun, jede 3. Zahl ist durch 3 Teilbar
(erste ist 3, letzte ist 99)
Damit kommen in 100! = 1*2*3*4*5*6*...*100
schonmal 3^33 in der Faktorzerlegung vor.
Nun haben einige Zahlen 3^2 in ihrer Zerlegung,
daher muessen noch Teiler von 9 beruecksichtigt
werden, also 9 bis 99 sind noch mal 11 Faktoren.
(Damit sind wir bei 3^44)
Nun kann auch noch 3^3 in den Zahlen vorkommen,
also von 27 bis 81, also noch 3 Faktoren.
(3^47)
Schliesslich kommt noch 1 mal ein 3^4=81 vor,
daher kommen wir schliesslich zu 3^48...

Andre
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

paul
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 07. November, 2000 - 07:08:   Beitrag drucken

Danke Andre.
Ist ja eigentlich ganz einfach.
Habe noch zwei ziemlich blöde Aufgaben, wie ich finde.
a) p sei eine Primzahl.
Beweise: In Z/(p) hat jedes von Null verschiedene Element ein multiplikatives Inverses.

b) p1 und p2 seien verschiedene Primzahlen, und es sei m=p1*p2.
Beweise oder widerlege: In Z/(m) gilt die Kürzungsregel.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

paul
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 15. November, 2000 - 06:39:   Beitrag drucken

Hilfeeee.
Kann mir denn keiner bei der vorab genannten Aufgabe helfen?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

thomas
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Donnerstag, den 16. November, 2000 - 21:14:   Beitrag drucken

Hallo paul,
wenn Du vielleicht genauer definieren könntest, was Z ist (Die Mengen der ganzen Zahlen vielleicht?),
ansonsten schaue doch mal im Archiv nach unter Primzahlen....
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 18. November, 2000 - 15:14:   Beitrag drucken

Hallo Paul, etwas spät, aber wieso schreibst du die Aufgabe auch unter Klasse 8 - 10?

b) In Z/(m) gilt p1 * p2 = 0 * p2 (= 0), aber nicht p1 = 0.

a) Brauchst du das noch? Kennst du den euklidischen Algorithmus?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lisa
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Donnerstag, den 23. November, 2000 - 18:47:   Beitrag drucken

Hallo speziell an Zaph.
Ich beschäftige mich gerade mit Modulo-Rechnung.
Dabei habe ich deine Rechnung entdeckt. "Welchen Rest gibt 1000^1000, wenn man es durch 13 teil.
Ganz wunderbar, konnte ich ohne weiteres nachvollziehen. Aber die Aufgabe ist auch ziemlich gut, denn man erhält den Rest 1.
Nun sitze ich vor der Aufgabe:
"Welchen Rest lässt die Zahl 13^169 bei Division durch 8?
Nach deinem Verfahren löse ich das so:
13^169 mod 8
5^169 mod 8, also Rest 5
Die Lösung stimmt zwar, aber ich bin mir unsicher, ob ich es dadurch überhaupt richtig gezeigt habe. Bei deiner Aufgabe ging es halt nicht weiter, da man den Rest 1 ermittelt hat. Wenn ich aber noch eine so große Zahl wie 5^169 stehen habe, verstehe ich noch nicht ganz, das ich dadurch die Lösung ermittelt habe. Vielleicht bin ich blöd oder blockiert. kannst du einer doofen Frau weiterhelfen?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Donnerstag, den 23. November, 2000 - 19:26:   Beitrag drucken

Hier gibt es auch einen Trick, der immer funktioniert. Schreibe 169 als Summe von Zweierpotenzen:

169 = 128 + 32 + 8 + 1 = 2^7 + 2^5 + 2^3 + 1

Berechne jetzt nacheinander 5^(2^k) für jede Zweierpotenz.

5^2 mod 8
= 25 mod 8
= 1

5^4 mod 8
= (5^2)^2 mod 8
= 1^2 mod 8
= 1

5^8 mod 8
= (5^4)^2 mod 8
= 1^2 mod 8
= 1

U. s. w.

Allgemein:

5^(2^(k+1)) mod 8
= (5^(2^k))^2 mod 8

Hier ist es wieder besonders einfach, denn 5^(2^k) = 1 mod 8 für jedes k > 0.

Jetzt kommt der letzte Schritt:

5^169 mod 8
= 5^(2^7 + 2^5 + 2^3 + 1) mod 8
= 5^(2^7) * 5^(2^5) * 5^(2^3) * 5^1 mod 8
= 1 * 1 * 1 * 5 mod 8
= 5.

Dieses Verfahren nennt man "Square and Multiply" ("quadriere und multipliziere").
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

lisa
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 24. November, 2000 - 06:49:   Beitrag drucken

Danke Zaph.
Habe ich verstanden.
Lisa
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

meike
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 08. Dezember, 2000 - 08:35:   Beitrag drucken

Hallo Zusammen.

Ich muss mich wohl oder übel mit Zahlentheorie beschäftigen. Also, ich muss im Unterricht mündlich den Euklidischen Algorithmus und die Neunerprobe erklären und erläutern können, warum diese Verfahren funktionieren. Außerdem muss ich die Richtigkeit des Systems zur Umwandlung einer nat. Zahl ins Dualsystem begründen. Also, das man eine nat. Zahl halbiert, solange bis sich die Zahl eins ergibt. Dann schreibt man neben die ungeraden Zahlen eine eins und neben die geraden eine o. Das Dualzahlwort kann dann von unten nach oben abgelesen werden.
Ich brauche Hilfe, da mir die korrekten Begründungen und Erläuterungen fehlen. Die Anwendung ist mir klar, doch wie mache ich das den anderen mündlich schlüssig??
Meike
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

doerrby
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 08. Dezember, 2000 - 13:22:   Beitrag drucken

Der Euklidische Algorithmus dient einerseits zur Bestimmung des größten gemeinsamen Teilers und, wenn man das Verfahren danach wieder rückwärts anwendet, zur Darstellung des ggT durch die beiden ursprünglichen Zahlen.
Beispiel:
(320,736) = ?
736 = 2 * 320 + 96
320 = 3 * 96 + 32
96 = 3 * 32
32 ist ein gemeinsamer Teiler. Aus der untersten Zeile folgt, dass 96 durch 32 teilbar ist. Aus der zweiten Zeile folgt, weil 96 und 32 durch 32 teilbar sind, dass auch 320 durch 32 teilbar ist.
Aus der ersten Zeile folgt, weil 320 und 96 durch 32 teilbar sind, dass auch 736 durch 32 teilbar ist.
Frage: Warum ist es der GRÖßTE gemeinsame Teiler?
Das begründet man von oben nach unten: der größte gemeinsame Teiler von 736 und 320 teilt natürlich auch Summen und Differenzen der beiden Zahlen (man kann ihn ausklammern), also auch die 96. Nun könnte 96 der ggT sein; dann müsste aber 320 durch 96 teilbar sein. Da es das nicht ist, setzt man das Verfahren mit diesen beiden Zahlen fort und zieht wieder ein Vielfaches, diesmal der 96, von 320 ab und erhält 32. Diese teilt jetzt die kleinere und die größere Zahl, ist also der ggT. Das kannst Du auch allgemein mit folgenden Formelzeilen machen:
r0 = q0 r1 + r2
r1 = q1 r2 + r3
  :
  :
rn-1 = qn-1 rn
rn ist dann ggT.

Neunerprobe:
Ich vermute Du meinst die Teilbarkeit durch 9, wenn die Quersumme 9 ist. Bei der Teilbarkeit geht es eigentlich nur um die Teilungsreste. Wenn der Rest 0 ist, ist die Zahl teilbar. 10 hat bei der Teilung durch 9 den Rest 1, 100 auch und 1000, ... , weil jede Zahl davor (9,99,999,9999,...) ganz offensichtlich durch 9 teilbar ist. Man guckt also jetzt nicht mehr, ob die Zahl als Ganzes teilbar ist, sondern ob die Reste modulo 9 (falls Dir das was sagt) 0 ergeben.
Beispiel: 675
600 = 6*100, 100 lässt den Rest 1, also lässt 600 den Rest 6
70 = 7*10, 10 lässt den Rest 1, also lässt 70 den Rest 7
5 lässt den Rest 5
Jetzt zählen wir die Reste zusammen und kommen auf 18, d.h. wenn wir die Reste alle zusammenwerfen, gehen diese auch noch auf.

Umwandlung in Dualzahl:
Du hast hier einen wichtigen Punkt vergessen: Wenn Du bei einer ungeraden Zahl ungleich 1 landest, musst Du 1 abziehen und dann weiterrechnen.
Man teilt im Prinzip von hinten immer durch die Basis, bis das nicht mehr geht, z.B. 44 = (101100)2. Teilt man die Zahl durch 2, erhält man (10110)2, und beim nächsten Mal (1011)2. Diese Zahl (11 im Zehnersystem) ist nicht mehr durch 2 teilbar. Jetzt zieht man 1 ab und erhält (1010)2, was wieder durch 2 Teilbar ist und (101)2 ergibt. Hier geht wieder 1 ab und (100)2 ist noch zweimal durch 2 teilbar.
Das geht übrigens auch in anderen Zahlensystemen, man muss eben immer nur durch die Basis teilen und erkennen, ob die übrigbleibende Zahl nochmal teilbar ist, was zugegeben beim Zweiersystem am einfachsten ist. Beispiel im Dreiersystem:
34 = (1021)3 : Man zieht die 1 ab und erhält 33 = (1020)3, diese Zahl ist durch 3 teilbar und es ergibt sich 11 = (102)3 . Hier muss man jetzt 2 abziehen um zur nächstkleineren Zahl zu kommen, die durch 3 teilbar ist, also zu 9 = (100)3 . Die lässt sich noch zweimal durch 3 teilen.
Gruß Dörrby
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin (Megamonsterccol)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 15. Dezember, 2000 - 20:57:   Beitrag drucken

2x * 6*(x+y)
------ ------- = ???
3*(x+g)* x

Wer kann mir erklären wie man auf den nenner kommt
und wie man das ganze dann rechnet bitte ausführlich schritt für schriit erklären !!!!!!!!!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Kai
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 16. Dezember, 2000 - 21:59:   Beitrag drucken

Da fehlt der Zusammenhang.
Bitte erkläre wo und aus welchem Zusammenhang die Frage kommt ...
Aber: Bitte neuen Beitrag aufmachen, nicht hinten dranhängen an andere Aufgaben.

Kai

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page