Carmichael-Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:56 Sa 23.05.2009 | | Autor: | Lati |
| Aufgabe | Zeigen Sie:
Sind für m [mm] \in \IN [/mm] die Zahlen 6m+1,12m+1,18m+1 Primzahlen, so ist:
n=(6m+1)(12m+1)(18m+1)
eine Carmichael-Zahl |
Hallo zusammen,
mir fehlt leider mal wieder der Ansatz zu obiger Aufgabe.
Das einzige was ich weiß ist, dass für eine Carmichael-Zahl folgender Zusammenhang gilt:
Für alle a mit ggT(a,n)=1 gilt [mm] a^{n-1}\equiv [/mm] 1(mod n)
Also gilt es hier vielleicht zu zeigen:
Für alle a mit ggT(a,(6m+1)(12m+1)(18m+1))=1 gilt:
[mm] a^{(6m+1)(12m+1)(18m+1)-1}\equiv [/mm] 1(mod (6m+1)(12m+1)(18m+1))
Aber wie genau zeig ich das jetzt und was muss ich hier überhaupt verwenden?
Vielen Dank für eure Hilfe!
Viele Grüße
|
|
| |
|
Hallo Lati,
ich bin gerade auf Reisen und auf dem Weg ins Bett, daher nur kurz. Je nach Müdigkeit dann Sonntag Abend mehr. 
> Also gilt es hier vielleicht zu zeigen:
>
> Für alle a mit ggT(a,(6m+1)(12m+1)(18m+1))=1 gilt:
>
> [mm]a^{(6m+1)(12m+1)(18m+1)-1}\equiv[/mm] 1(mod
> (6m+1)(12m+1)(18m+1))
So ist es. Das ist die Aufgabe.
> Aber wie genau zeig ich das jetzt und was muss ich hier
> überhaupt verwenden?
Du brauchst den "kleinen Fermat", für den Ansatz auch den chinesischen Restsatz (was sagt die Restklasse 1 bezüglich n über die Kongruenz bezüglich der Faktoren von n aus?), und mehr nicht.
Du solltest dabei versuchen, [mm] \a{}(6m+1)(12m+1)(18m+1)-1 [/mm] in geschickter Weise umzuformen, so dass Du den "kleinen Fermat" überhaupt anwenden kannst.
> Vielen Dank für eure Hilfe!
>
> Viele Grüße
Viel Erfolg!
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:45 So 24.05.2009 | | Autor: | Lati |
Hi Reverend,
Danke, dass du dich trotz der späten Uhrzeit noch meiner angenommen hast!
Ok, ich habe deine Tipps mal aufgenommen, und versucht das ganze auf eine Form zu bringen auf die ich dann den Fermat anwenden kann.
Dazu kann man [mm]a^{(6m+1)(12m+1)(18m+1)-1}\equiv[/mm] 1(mod (6m+1)(12m+1)(18m+1)) ja auch so schreiben:
[mm] a^{(6m+1)(12m+1)(18m+1)-1} [/mm] = [mm] a^{(6m+1)(12m+1)(18m+1)}*a^{-1}
[/mm]
dann folgt:
[mm] a^{(6m+1)(12m+1)(18m+1)}\equiv [/mm] a
Jetzt hat man als Voraussetzung ja schon dass a und n teilerfremd sind.
Bleibt nur noch (6m+1)(12m+1)(18m+1) in eine Primzahl umzuwandeln so dass dann alle Voraussetzungen des Fermats erfüllt sind und dieser angewendet werden kann. Hast du das so gemeint gehabt?
Allerdings weiß ich jetzt nicht genau wie ich den Restsatz hier jetzt anwenden soll?
Also er sagt ja aus, dass [mm] Z_{n}=Z_{6m+1} \times Z_{12m+1} \times Z_{18m+1},wobei [/mm] Z immer die Restklassenabb. darstellen soll. oder?
Jetzt hätte ich ja nach Voraussetzung eine Primzahl als Hochzahl,aber darf ich das so einfach machen?
Oder wie muss ich hier geschickter vorgehen und wie schreib ich das genau auf?
Vielen Dank für deine Hilfe!
Viele Grüße
Lati
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:17 Mo 25.05.2009 | | Autor: | felixf |
Hallo!
> Danke, dass du dich trotz der späten Uhrzeit noch meiner
> angenommen hast!
> Ok, ich habe deine Tipps mal aufgenommen, und versucht das
> ganze auf eine Form zu bringen auf die ich dann den Fermat
> anwenden kann.
>
> Dazu kann man [mm]a^{(6m+1)(12m+1)(18m+1)-1}\equiv[/mm] 1(mod
> (6m+1)(12m+1)(18m+1)) ja auch so schreiben:
>
> [mm]a^{(6m+1)(12m+1)(18m+1)-1}[/mm] =
> [mm]a^{(6m+1)(12m+1)(18m+1)}*a^{-1}[/mm]
>
> dann folgt:
>
> [mm]a^{(6m+1)(12m+1)(18m+1)}\equiv[/mm] a
Genau. Und die Rueckrichtung folgt auch.
> Jetzt hat man als Voraussetzung ja schon dass a und n
> teilerfremd sind.
Die hast du schon benutzt, ansonsten macht das [mm] $a^{-1}$ [/mm] oben keinen Sinn.
> Bleibt nur noch (6m+1)(12m+1)(18m+1) in eine Primzahl
> umzuwandeln so dass dann alle Voraussetzungen des Fermats
> erfüllt sind und dieser angewendet werden kann. Hast du das
> so gemeint gehabt?
Nein, nicht wirklich. Genauer gesagt brauchst du hier was von Euler: ist $n [mm] \in \IN$ [/mm] eine natuerliche Zahl, $a$ teilerfremd zu $n$ und ist [mm] $\phi(n)$ [/mm] die Eulersche [mm] $\phi$-Funktion [/mm] fuer $n$, also [mm] $\phi(n) [/mm] = [mm] |(\IZ/n\IZ)^\ast|$, [/mm] so gilt [mm] $a^{\phi(n)} \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] bzw. [mm] $a^{\phi(n) + 1} \equiv [/mm] a [mm] \pmod{n}$.
[/mm]
(Alternativ kannst du auch den Chinesischen Restsatz zusammen mit dem Satz von Fermat benutzen, um das herauszubekommen.)
Hier hast du $n = (6 m + 1) (12 m + 1) (18 m + 1)$. Kannst du [mm] $\phi(n)$ [/mm] ausrechnen? Du kennst ja die Primfaktorzerlegung von $n$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:14 Mo 25.05.2009 | | Autor: | Lati |
Hi Felix,
auch dir vielen Dank für die Hilfe!
Ich habe [mm] \phi(n) [/mm] jetzt mal ausgerechnet und zwar nach der Formel:
[mm] \phi(n)= [/mm] n* [mm] \produkt_{p/n,p\in \IP } [/mm] (1-1/p) = (6m+1)(12m+1)(18m+1)*(1-1/(6m+1))(1-1/(12m+1))(1-1/(18m+1))=6m*12m*18m= [mm] 1296m^3
[/mm]
soweit richtig?
Und jetzt reicht es zu sagen:
[mm] a^{1296m^3+1}\equiv [/mm] a auf Grund des Satzes von Euler?(den darf ich auf jeden Fall verwenden,hatten wir in der Vorlesung)
Vielen Dank!
Gruß
Lati
>
> > Danke, dass du dich trotz der späten Uhrzeit noch meiner
> > angenommen hast!
> > Ok, ich habe deine Tipps mal aufgenommen, und versucht
> das
> > ganze auf eine Form zu bringen auf die ich dann den Fermat
> > anwenden kann.
> >
> > Dazu kann man [mm]a^{(6m+1)(12m+1)(18m+1)-1}\equiv[/mm] 1(mod
> > (6m+1)(12m+1)(18m+1)) ja auch so schreiben:
> >
> > [mm]a^{(6m+1)(12m+1)(18m+1)-1}[/mm] =
> > [mm]a^{(6m+1)(12m+1)(18m+1)}*a^{-1}[/mm]
> >
> > dann folgt:
> >
> > [mm]a^{(6m+1)(12m+1)(18m+1)}\equiv[/mm] a
>
> Genau. Und die Rueckrichtung folgt auch.
>
> > Jetzt hat man als Voraussetzung ja schon dass a und n
> > teilerfremd sind.
>
> Die hast du schon benutzt, ansonsten macht das [mm]a^{-1}[/mm] oben
> keinen Sinn.
>
> > Bleibt nur noch (6m+1)(12m+1)(18m+1) in eine Primzahl
> > umzuwandeln so dass dann alle Voraussetzungen des Fermats
> > erfüllt sind und dieser angewendet werden kann. Hast du das
> > so gemeint gehabt?
>
> Nein, nicht wirklich. Genauer gesagt brauchst du hier was
> von Euler: ist [mm]n \in \IN[/mm] eine natuerliche Zahl, [mm]a[/mm]
> teilerfremd zu [mm]n[/mm] und ist [mm]\phi(n)[/mm] die Eulersche
> [mm]\phi[/mm]-Funktion fuer [mm]n[/mm], also [mm]\phi(n) = |(\IZ/n\IZ)^\ast|[/mm], so
> gilt [mm]a^{\phi(n)} \equiv 1 \pmod{n}[/mm] bzw. [mm]a^{\phi(n) + 1} \equiv a \pmod{n}[/mm].
>
> (Alternativ kannst du auch den Chinesischen Restsatz
> zusammen mit dem Satz von Fermat benutzen, um das
> herauszubekommen.)
>
> Hier hast du [mm]n = (6 m + 1) (12 m + 1) (18 m + 1)[/mm]. Kannst du
> [mm]\phi(n)[/mm] ausrechnen? Du kennst ja die Primfaktorzerlegung
> von [mm]n[/mm].
>
> LG Felix
>
|
|
|
| |
|
Hallo Lati,
> Ich habe [mm]\phi(n)[/mm] jetzt mal ausgerechnet und zwar nach der
> Formel:
>
> [mm]\phi(n)=[/mm] n* [mm]\produkt_{p/n,p\in \IP }[/mm] (1-1/p) =
> (6m+1)(12m+1)(18m+1)*(1-1/(6m+1))(1-1/(12m+1))(1-1/(18m+1))=6m*12m*18m=
> [mm]1296m^3[/mm]
>
> soweit richtig?
Ja.
> Und jetzt reicht es zu sagen:
>
> [mm]a^{1296m^3+1}\equiv[/mm] a auf Grund des Satzes von Euler? (den
> darf ich auf jeden Fall verwenden,hatten wir in der
> Vorlesung)
Nein, wieso soll das reichen? Du willst ja [mm] a^n\equiv a\mod{n} [/mm] zeigen.
Tipp:
[mm] n=1296m^3+396m^2+36m+1=1296m^3+36m(11m+1)+1
[/mm]
Nun muss Du also noch zeigen: [mm] a^{36m(11m+1)}\equiv 1\mod{n}
[/mm]
Ich sehe übrigens nicht, inwiefern dieser Weg eleganter ist als mein ursprünglich vorgeschlagener, aber wenn Felix (am Wochenende) wieder da ist, kann er das sicher zeigen.
LG,
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:45 Mo 25.05.2009 | | Autor: | Lati |
Hi Reverend,
danke erstmal für die Antwort!
Du meinst doch jetzt schon, dass man jetzt 36m(11m+1) so umformen soll, dass man den Fermat anwenden kann oder? Also muss ich irgendwie eine Primzahl draus machen oder versteh ich gar nichts?
Könntest du mir vielleicht nochmal einen Tipp geben wie ich das genau anstellen muss? Steh irgendwie immer noch aufm Schlauch. Sorry!
LG Lati
|
|
|
| |
|
Hallo lati,
aufgrund der Regeln der Potenzrechnung gilt doch
[mm] a^{36m(11m+1)}=\left(a^{36m}\right)^{11m+1}=\left(\left(a*a^{11m}\right)^{36}\right)^m [/mm] etc.
Da gibt es eine Reihe möglicher Umformungen. Doch worauf willst Du hinaus? Du willst noch zeigen, dass [mm] a^{36m(11m+1)}\equiv 1\mod{n} [/mm] ist. Das wäre gezeigt, wenn Du für irgendein b, das 36m(11m+1) teilt, [mm] a^b\equiv 1\mod{n} [/mm] zeigen kannst.
In Frage kommen damit alle Teiler von 36, m und (11m+1), sowie alle Kombinationen (Produkte) daraus. Dabei springt genau eine Möglichkeit sozusagen ins Auge, da ja (6m+1), (12m+1) und (18m+1) Teiler von n sind, und zwar (außer ihren Produkten) die einzigen.
Kannst Du z.B. diese Frage beantworten: [mm] a^{144m}\equiv ?\mod{n}
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:07 Mo 25.05.2009 | | Autor: | Lati |
Hi Reverend,
danke!
erstmal zu deiner Frage [mm] a^{144m}\equiv [/mm] ? (mod n)
Dazu habe ich verwendet 12*(12m+1)=144m+12
dann folgt:
[mm] a^{144m+12} \equiv a^{12(12m+1)} \equiv a^{(12m+1)^12} \equiv 1^{12} \equiv [/mm] 1 mod n dann gilt: [mm] a^{144m+12} \equiv [/mm] 1 daraus folgt [mm] a^{144m}*a^{12} \equiv [/mm] 1 daraus folgt: [mm] a^{144m} \equiv a^{-12}
[/mm]
Hast du das so gemeint?
Es tut mir schrecklich Leid, aber auf die andere Lösung bin ich immer noch nicht gekommen.
Liege ich wenigstens richtig in der Annahme, dass es sich um ein Vielfaches der Primfaktoren handeln muss?
Und muss ich vorher noch umformen oder ist es eine Kombination zweier Primfaktoren?
Sorry!
Vielen Dank für deine Geduld!
Gruß
|
|
|
| |
|
Hallo Lati,
1) [mm] 144=24*\blue{6}=12*\blue{12}=8*\blue{18}
[/mm]
2) [mm] \a{}144=d*kgV(6m,12m,18m)=36m*d [/mm] mit [mm] \a{}d=4.
[/mm]
3) Nach Euler-Fermat gilt für [mm] cm+1\in\IP \quad a^{cm}\equiv 1\mod{(cm+1)}.
[/mm]
4) Weiter ist nach den gegebenen Voraussetzungen [mm] \a{}kgV(6m+1,12m+1,18m+1)=n
[/mm]
5) Aus 1,2,3) folgt [mm] a^{144m}=\left(a^{36m}\right)^d=...
[/mm]
5a) [mm] ...=\left(a^{6m}\right)^{6d}\equiv 1^{6d}\mod{(6m+1)}
[/mm]
5b) [mm] ...=\left(a^{12m}\right)^{3d}\equiv 1^{3d}\mod{(12m+1)}
[/mm]
5c) [mm] ...=\left(a^{18m}\right)^{2d}\equiv 1^{2d}\mod{(18m+1)}
[/mm]
6) Aus dem chinesischen Restsatz folgt aus 5) [mm] \left(a^{36m}\right)^d\equiv 1\mod{n}
[/mm]
Nun hätten wir uns das d sparen können. Die 144 sollte Dich nur auf die Spur bringen, dass sie ein gemeinsames Vielfaches von 6,12,18 ist, aber eben nicht das kleinste. Für d=1 wäre genauso zu zeigen gewesen, dass [mm] a^{36m}\equiv 1\mod{(6m+1,\ 12m+1,\ 18m+1)} [/mm] ist.
Es ist also [mm] a^{36m}\equiv 1\mod{n} [/mm] und damit [mm] a^{36m(11m+1)}=\left(a^{36m}\right)^{(11m+1)}\equiv 1^{11m+1}=1\mod{n}.
[/mm]
Damit wäre nun die pseudoprime Eigenschaft der untersuchten Zahl n für alle zu n teilerfremden a endlich gezeigt. Ich vermute, dass der Weg, den Felix vorschlug, schneller zum Ziel führt, aber ich finde ihn nicht. Also warte ich mal mit Dir darauf, hier noch etwas zu lernen.
Liebe Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:13 Di 26.05.2009 | | Autor: | Lati |
Hi Reverend,
vielen, vielen Dank für die ausführliche Hilfe!
Bin auch mal gespannt, was er mit dem anderen Weg so vor hatte...
LG Lati
|
|
|
|
