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

Carmichael Zahlen

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Zahlentheorie » Carmichael Zahlen « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 38
Registriert: 10-2003
Veröffentlicht am Samstag, den 06. November, 2004 - 18:29:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1733
Registriert: 07-2000
Veröffentlicht am Samstag, den 06. November, 2004 - 23:12:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 40
Registriert: 10-2003
Veröffentlicht am Sonntag, den 07. November, 2004 - 12:41:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1737
Registriert: 07-2000
Veröffentlicht am Sonntag, den 07. November, 2004 - 13:03:   Beitrag drucken

Hm, ich sehe da eigentlich keinen Unterschied zur ersten Version ...

Z.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 971
Registriert: 05-2002
Veröffentlicht am Sonntag, den 07. November, 2004 - 14:08:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 972
Registriert: 05-2002
Veröffentlicht am Sonntag, den 07. November, 2004 - 14:26:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 41
Registriert: 10-2003
Veröffentlicht am Sonntag, den 07. November, 2004 - 20:20:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 46
Registriert: 10-2003
Veröffentlicht am Dienstag, den 09. November, 2004 - 15:08:   Beitrag drucken

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!
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1744
Registriert: 07-2000
Veröffentlicht am Dienstag, den 09. November, 2004 - 22:25:   Beitrag drucken

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 ...
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 978
Registriert: 05-2002
Veröffentlicht am Dienstag, den 09. November, 2004 - 23:20:   Beitrag drucken

@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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1745
Registriert: 07-2000
Veröffentlicht am Dienstag, den 09. November, 2004 - 23:28:   Beitrag drucken

@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).
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Mainziman (Mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 979
Registriert: 05-2002
Veröffentlicht am Dienstag, den 09. November, 2004 - 23:50:   Beitrag drucken

@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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1746
Registriert: 07-2000
Veröffentlicht am Mittwoch, den 10. November, 2004 - 00:09:   Beitrag drucken

sorry, ich meinte doch "muss N-1 doch noch nicht" ...
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1747
Registriert: 07-2000
Veröffentlicht am Mittwoch, den 10. November, 2004 - 12:37:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 47
Registriert: 10-2003
Veröffentlicht am Mittwoch, den 10. November, 2004 - 20:29:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1748
Registriert: 07-2000
Veröffentlicht am Mittwoch, den 10. November, 2004 - 22:37:   Beitrag drucken

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.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Emrepb (Emrepb)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: Emrepb

Nummer des Beitrags: 49
Registriert: 10-2003
Veröffentlicht am Donnerstag, den 11. November, 2004 - 00:57:   Beitrag drucken

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

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