| Autor |
Beitrag |
    
Miriam (mmemim)
Junior Mitglied
Benutzername: mmemim
Nummer des Beitrags: 71
Registriert: 05-2001
| | Veröffentlicht am Dienstag, den 30. April, 2002 - 17:54: | 
|
HI Ihr!
Ich hoffe, ihr könnt wenigstens einer der mitgeschickten Aufgaben, denn ich kann diesmal gar nichts! THX
Miriam |
Judith
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 30. April, 2002 - 21:25: |
|
Hallo Miriam,
Die Antwort ist vielleicht schon hier:
http://www.mathehotline.de/mathe4u/hausaufgaben/messages/4244/74616.html?1020179051 |
Nadine (anja)
Mitglied
Benutzername: anja
Nummer des Beitrags: 39
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 01. Mai, 2002 - 11:50: |
|
Hallo Judith. Dein angegebener Link funktioniert leider nicht. Könntst du ihn bitte noch einmal überprüfen Danke NAdine |
Carmichael
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 13:51: |
|
zu 12)
M := {a E Z/nZ* | a^(n-1) = 1 (mod n)};
Es ist M eine Untergruppe von Z/nZ*, weil gilt:
a^(n-1) = b^(n-1) = 1 mod n => (a*b^-1)^(n-1) = 1 mod n; (Untergruppenkriterium)
außerdem gilt: |M| < |Z/nZ*|, weil n keine Carmichael noch Primzahl ist.
Da |M| mit M Untergruppe ein Teiler von |Z/nZ*| sein muss, folgt sofort: |M| <= 1/2*|Z/nZ*| = 1/2*Phi(n);
Test: Gilt für eine der r Zahlen r^(n-1) != 1 (mod n) kann n keine Primzahl sein.
Ist n keine Primzahl (und nicht CarmichaelZahl), gibt es höchstens phi(n)/2 Zahlen a kleiner n, sodass a^(n-1) = 1 mod n. Der Test ist erfolglos, wenn alle r Zahlen aus diesen sind. Die Wahrscheinlichkeit dafür ist: p = (phi(n)/2 über r)/(n-1 über r) für r kleinergleich phi(n)/2 und p = 0 für r größer phi(n)/2.
zu 13)
Primfaktorzerlegung von m sei p1^k1*p2^k2*...*pn^kn.
p1^k1,p2^k2,...,pn^kn sind Primzahlpotenzen mit unterschiedlicher Primzahl als Basis und damit paarweise teilerfremd.
=> phi(m) = phi(p1^k1*p2^k2*...*pn^kn) = phi(p1^k1)*phi(p2^k2)*...*phi(pn^kn) = p1^k1*(1-1/p1)*p2^k2*(1-1/p2)*...*pn^kn*(1-1/pn) = m*(1-1/p1)*(1-1/p2)*...**(1-1/pn).
zu 14) (3*5)*1 = 1 (mod 7);
(3*7)*1 = 1 (mod 5);
(5*7)*2 = 1 (mod 3);
Sei nun x = [(5*7)*2]*2 + [(3*7)*1]*3 + [(3*5)*1]*2;
Dann erfüllt x offensichtlich das geforderte Kongruenzsystem.
zu 15) Da m_1,m_2,...,m_n paarweise teilerfremd, gibt es für jedes m_i ein k, so dass: m_i*k = 1 (mod m_1*m_2*,...*m_n/m_i).
Dann Konstruktion von x wie bei 14 ....
MfG Carmichael |
Miriam (mmemim)
Fortgeschrittenes Mitglied
Benutzername: mmemim
Nummer des Beitrags: 73
Registriert: 05-2001
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 16:48: |
|
Hi Carmichael!
Das war ja dann offensichtlich Dein Fachgebiet! :o)
Ich hab aber noch eine Frage zur Lösung von Aufgabe 14! Wie kommst DU darauf, daß x =[(5*7)*2]*2 + [(3*7)*1]*3 + [(3*5)*1]*2 ist!
Vielen DAnk für die GROSSE Hilfe!
Miriam
|
Carmichael
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 21:10: |
|
Bitte Bitte 
Ja, das ist nur eine Lösung bei Aufgabe 14 für x.
Es gibt unendlich viele und man kann sie auch charakterisieren und zwar mit dem chinesischen Restsatz.
Der besagt:
Sind m1,m2,...mn paarweise teilerfremd und seien r1,r2,...,rn beliebig aus n, dann gibt es genau ein x0 kleiner m1*m2*...*mn, so dass x0 = r1 (mod m1), x0 = r2 (mod m2) ... x = rn (mod mn). Für alle anderen x, die dieses Kongruenzsystem erfüllen, gilt m1*m2*...*mn teilt x-x0.
Das heißt für Aufgabe 14:
Alle x lassen sich mit [(5*7)*2]*2 + [(3*7)*1]*3 + [(3*5)*1]*2 + k*3*5*7 mit k E Z beschreiben.
[
Betrachte x =[(5*7)*2]*2 + [(3*7)*1]*3 + [(3*5)*1]*2 modulo 3. zweiter und dritter Summand sind 0 (durch 3 teilbar). Erster Summand ist wegen (5*7)*2 = 1 (mod 3); kongruent 2 modulo 3. also x=2 (mod 3).
usw.
]
MfG |
Miriam (mmemim)
Fortgeschrittenes Mitglied
Benutzername: mmemim
Nummer des Beitrags: 74
Registriert: 05-2001
| | Veröffentlicht am Freitag, den 03. Mai, 2002 - 15:27: |
|
Super, jetzt hab ich es verstanden! DANKE!  |
|
