Autor |
Beitrag |
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 38 Registriert: 10-2003
| Veröffentlicht am Samstag, den 06. November, 2004 - 18:29: |
|
Bitte um Hilfe! Wir kennen folgende Charakterisierung einer Carmichael Zahl: N Carmichael <=> Für Alle p|N: p-1|N-1 Zeige: Jede Carmichael Zahl (i) ist ungerade. ii) hat mindestens 3 Primfaktoren. (Tip: Verwende die Eigenschaft, daß jede Carmichaelzahl quadratfrei ist.) Danke im Voraus |
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1733 Registriert: 07-2000
| Veröffentlicht am Samstag, den 06. November, 2004 - 23:12: |
|
Das kommt mir aber merkwürdig vor! Nach deiner Charakterisierung ist jede Primzahl eine Carmichael-Zahl. Aber es ist weder (i) jede Primzahl ungerade, noch hat (ii) jede Primzahl mindestens 3 Prinmfaktoren ... Bitte gib die Definition einer Carmichael-Zahl an und überdenke noch mal die Charakterisierung! Z. |
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 40 Registriert: 10-2003
| Veröffentlicht am Sonntag, den 07. November, 2004 - 12:41: |
|
Sie Charakterisierung müsste eigentlich so stimmen. Für alle p Element Primzahl gilt: p|n => p-1|n-1 oder ist das auch falsch??? Gruß EmrePB |
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1737 Registriert: 07-2000
| Veröffentlicht am Sonntag, den 07. November, 2004 - 13:03: |
|
Hm, ich sehe da eigentlich keinen Unterschied zur ersten Version ... Z. |
Mainziman (Mainziman)
Senior Mitglied Benutzername: Mainziman
Nummer des Beitrags: 971 Registriert: 05-2002
| Veröffentlicht am Sonntag, den 07. November, 2004 - 14:08: |
|
ich hätte anhand des ersten Postings ein seltsames Beispiel: N = 4 => 1, 2, 4 sind Teiler (also p) davon daher N-1 = 3, und das hat jetzt als Teiler 1 und 3, also (2-1) und (4-1) da jetzt aber p prim sein soll, 2 der einzige Primteiler von 4 ist; N = 4, p = 2 und N-1 = 3, p-1 = 1; wäre daher 4 eine Carmichaelzahl; und das steht aber dann zu den Punkten welche gezeigt werden sollen im Widerspruch Mainzi Man, ein Mainzelmännchen-Export, das gerne weiterhilft oder auch verwirren kann *ggg*
|
Mainziman (Mainziman)
Senior Mitglied Benutzername: Mainziman
Nummer des Beitrags: 972 Registriert: 05-2002
| Veröffentlicht am Sonntag, den 07. November, 2004 - 14:26: |
|
hier http://mathworld.wolfram.com/CarmichaelNumber.html steht die Definition von Carmichaelzahlen Mainzi Man, ein Mainzelmännchen-Export, das gerne weiterhilft oder auch verwirren kann *ggg*
|
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 41 Registriert: 10-2003
| Veröffentlicht am Sonntag, den 07. November, 2004 - 20:20: |
|
vielleicht sollte ja ein wiederspruchsbeweis gezeigt werden???!?!aber die Aufgabenstellung dürfte nicht falsch sein. schaut euch man die datei an. weiter unten steht auch etwas über charmichael zahlen. und da ist auch die charakterisiereng. http://www.math.tu-cottbus.de/INSTITUT/lsgdi/Krypto2004/kapitel6.pdf Gruß EmrePB |
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 46 Registriert: 10-2003
| Veröffentlicht am Dienstag, den 09. November, 2004 - 15:08: |
|
Hallo nochmal, ich habe einen Übungsgruppenleiter gefragt ob die Aufgabe falschgestellt ist. Daraufhin hat er mir so geantwortet: zunächst mal haben wir Carmichaelzahlen als diejenigen kennengelernt, die den Fermat test immer fälschlicherweise bestehen (also zusammengesetzt sind) Der zweite Punkt ist die Äquivalenz. Die gilt nur unter den Bedingungen, die ihr zeigen sollt. (Ich habe daraus mal eine Implikation gemacht.) Sei N eine zusammengesetzte Zahl. Wir kennen folgende Charakterisierung einer Carmichael Zahl N Carmichael => Für Alle p|N: p-1|N-1 Zeige: Jede Carmichael Zahl (i) ist ungerade. ii) hat mindestens 3 Primfaktoren. (Tip: Verwende die Eigenschaft, daß jede Carmichaelzahl quadratfrei ist.) So müsste die Aufgabe Stimmen. Danke im Voraus! |
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1744 Registriert: 07-2000
| Veröffentlicht am Dienstag, den 09. November, 2004 - 22:25: |
|
Na, dass N zusammengesetzt sein soll, hast du uns bisher verschwiegen Sei N > 1. Da 2^(N-1) = 1 mod N gilt (Primzahltest mit 2), folgt, dass N ein Teiler von 2^(N-1) - 1 ist. Da 2^(N-1) - 1 ungerade ist, kann N somit nicht gerade sein. Angenommen, N = pq ist Charmichael für Primzahlen p und q. Dann ist p != q (denn N ist quadratfrei). Es folgt (nach der Charakteristierung), dass p-1 und q-1 Teiler von N-1 sind. Also k(p-1) = m(q-1) = N-1 = pq-1 für gewisse m und k. ... so muss das wohl irgendwie gehen ... vielleicht hat jemand anders eine Idee ... |
Mainziman (Mainziman)
Senior Mitglied Benutzername: Mainziman
Nummer des Beitrags: 978 Registriert: 05-2002
| Veröffentlicht am Dienstag, den 09. November, 2004 - 23:20: |
|
@Zaph, warum nicht gleich k(p-1)(q-1) = N-1 ? das wäre dann kpq - kq - kp + k = N-1 da jetzt gilt N = pq folgt kN - (p+q)k + k + 1 = N - (p+q)k + k + 1 = N - kN (p+q)k - k - 1 = (k-1)N der Fall daß k = 1 ist, kann ausgeschlossen werden, weil (p+q)1 - 1 - 1 = (1-1)N p+q - 2 = 0 und das würde im Widerspruch zu p!=q stehen, daher (p+q)k - k - 1 = (k-1)N (p+q)k/(k-1) - (k+1)/(k-1) = N (p+q)(k-1+1)/(k-1) - (k-1+2)/(k-1) = N (p+q) + (p+q)/(k-1) - 1 - 2/(k-1) = N (p+q-1) + (p+q-2)/(k-1) = N (p-1) + (q-1) + (p+q-2)/(k-1) = N-1 (p-1)(1+1/(k-1)) + (q-1)(1+1/(k-1)) = N-1 wenn k(p-1)(q-1) = N-1, dann gilt p-1 = (N-1)/(k(q-1)) (N-1)/(k(q-1))(1+1/(k-1)) + (q-1)(1+1/(k-1)) = N-1 (N-1)/(k)*(1+1/(k-1)) + (1+1/(k-1)) = (N-1)/(q-1) (N-1)/(k)*(k/(k-1)) + (k/(k-1)) = (N-1)/(q-1) (N-1)/(k-1) + (k/(k-1)) = (N-1)/(q-1) (N-1+k)/(k-1) = (N-1)/(q-1) 1 + N/(k-1) = (N-1)/(q-1) N durch k-1 teilbar? jetzt ist der Widerspruch, daß k-1 nicht Teiler von N ist, zu führen; N-1 ist durch k teilbar daher m * k = N-1 wenn N jetzt auch durch k-1 teilbar sein soll, dann n * (k-1) = N n*k - n - 1 = m * k k( n - m ) = n - m + m + 1 k = 1 + ( m + 1 ) / ( n - m ) da geht nur dann, wenn n = m + 1 gilt was bedeuten würde, daß k = 1 + n = 2 + m gelte damit würde N quadratisch sein; und das ist ein Widerspruch, somit teilt k-1 nicht N, und die Annahme N hat 2 Primteiler ist falsch; Mainzi Man, ein Mainzelmännchen-Export, das gerne weiterhilft oder auch verwirren kann *ggg*
|
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1745 Registriert: 07-2000
| Veröffentlicht am Dienstag, den 09. November, 2004 - 23:28: |
|
@Mainzi: wenn N-1 durch p-1 und q-1 teilbar ist, muss N doch noch nicht durch (p-1)(q-1) teilbar sein, denn p-1 und q-1 sind doch nicht teilerfremd (z. B. ist 2 ein Teiler von beiden). |
Mainziman (Mainziman)
Senior Mitglied Benutzername: Mainziman
Nummer des Beitrags: 979 Registriert: 05-2002
| Veröffentlicht am Dienstag, den 09. November, 2004 - 23:50: |
|
@Zaph: Du verwirrst mich, N ist doch weder durch p-1 noch durch q-1 teilbar; p, q sind prim - die Frage ist dann, welche gemeinsamen Teiler p-1 und q-1 haben; weil dann schafft man es irgendwie, so wie ich oben beide Faktoren zu verwenden k(p-1)(q-1)/h = N-1 mit h teilerfremd zu k wobei aus pq = N folgt daß gilt k > h ich denke des sollte sich reinbasteln lassen, und analog wie oben klappen Mainzi Man, ein Mainzelmännchen-Export, das gerne weiterhilft oder auch verwirren kann *ggg*
|
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1746 Registriert: 07-2000
| Veröffentlicht am Mittwoch, den 10. November, 2004 - 00:09: |
|
sorry, ich meinte doch "muss N-1 doch noch nicht" ... |
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1747 Registriert: 07-2000
| Veröffentlicht am Mittwoch, den 10. November, 2004 - 12:37: |
|
Jetzt aber ... Angenommen, N - 1 = pq - 1 = r(p - 1) und N - 1 = pq - 1 = s(q - 1) Dann folgt (r - q)(p - 1) = q - 1 (*) bzw. (s - p)(q - 1) = p - 1 Aus diesen beiden Gleichungen folgt (r - q)(s - p) = 1 Daher r - q = s - p = 1 oder r - q = s - p = -1 Mit (*) folgt dann aber p = q oder p + q = 2 ... was beides nicht sein kann, da N quadratfrei ist und p, q prim sind. |
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 47 Registriert: 10-2003
| Veröffentlicht am Mittwoch, den 10. November, 2004 - 20:29: |
|
Danke für die Lösungen. habe es grad überflogen und werde es morgen mir genaur anschauen. Es sieht aber sehr übersichtlich aus wie in allen Lösungen Kennst du dich vielleicht auch mit Maple oder Mupad gut aus?????? Ich versuch da eine Aufgabe zu lösen aber irgendwie klappt es nicht mit der notation oder ich mach da wieder etwas nicht so richtig???? Gruß EmrePB |
Zaph (Zaph)
Senior Mitglied Benutzername: Zaph
Nummer des Beitrags: 1748 Registriert: 07-2000
| Veröffentlicht am Mittwoch, den 10. November, 2004 - 22:37: |
|
Hi EmrePB, ich hoffe, du meinst "übersichtlich" jetzt nicht sarkastisch ... die Einzelschritte sind, hoffe ich, wirklich alle sehr einfach nachzuvollziehen. Falls nicht, melde dich! Z. P.S.: Mupad kenne ich praktisch nur vom Namen; mit Maple mache ich hin und wieder was, bin aber kein Experte. |
Emrepb (Emrepb)
Mitglied Benutzername: Emrepb
Nummer des Beitrags: 49 Registriert: 10-2003
| Veröffentlicht am Donnerstag, den 11. November, 2004 - 00:57: |
|
Hi Zaph, mit übersichtlich meinte ich das es leicht nachvollziehbar ist. Habe es acuh gut nachvollziehen können. Aber so langsam bekommt man einen gefühl was das Beweisen angeht ;) Ich hoffe das bei der nächsten aufgabe nicht so viele beweise vorkommen Meld mich wenn ich etwas nicht verstehe oder so. P.S.: Das mit Maple habe ich irgendwie doch noch geschafft...es waren einiege notationfehler...sonst alles bestens. Bis dann Gruß EmrePB |