'schwacher' kleiner Fermat < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:36 Mo 19.08.2013 | | Autor: | wauwau |
| Aufgabe | Bestimme alle Zahlen n, für die für alle $a$ mit $(a,n)=1$
[mm] $a^{2(n-1)} \equiv [/mm] 1 [mm] \mod [/mm] n$ gilt |
Leider stehe ich etwas auf der Leitung
Gibt es ausser den Carmichael Zahlen und Primzahlen sonst noch welche, die dieses schwächere Kriterium erfüllen?
|
|
| |
|
Hallo wauwau,
> Bestimme alle Zahlen n, für die für alle [mm]a[/mm] mit [mm](a,n)=1[/mm]
> [mm]a^{2(n-1)} \equiv 1 \mod n[/mm] gilt
>
>
> Leider stehe ich etwas auf der Leitung
> Gibt es ausser den Carmichael Zahlen und Primzahlen sonst
> noch welche, die dieses schwächere Kriterium erfüllen?
Ja. Wie wärs einfach mit n=15?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Mo 19.08.2013 | | Autor: | wauwau |
Danke - aber das sind ja nicht alle (24,28,66,91,...)
also Primzahlen, Carmichael Zahlen und andere
Für Primzahlen und Carmichael Zahlen gibt es ja Korselts Kriterium.
Gibt es für die in diesem Fall gesuchten ebenfalls ein Kriterium?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:11 Mo 19.08.2013 | | Autor: | felixf |
Moin!
> Danke - aber das sind ja nicht alle (24,28,66,91,...)
> also Primzahlen, Carmichael Zahlen und andere
> Für Primzahlen und Carmichael Zahlen gibt es ja Korselts
> Kriterium.
> Gibt es für die in diesem Fall gesuchten ebenfalls ein
> Kriterium?
Ist $n$ eine Zahl mit [mm] $a^{2 (n-1)} [/mm] = 1$ fuer alle $a [mm] \in (\IZ/n\IZ)^\ast$, [/mm] so muss $n$ quadratfrei sein. Das zeigt man genauso wie bei Carmichael-Zahlen: ist $n = [mm] p^e \cdot [/mm] m$ mit $p [mm] \nmid [/mm] m$ und $e [mm] \ge [/mm] 2$, so kann man in [mm] $(\IZ/n\IZ)^\ast \cong (\IZ/p^e\IZ)^\ast \times (\IZ/m\IZ)^\ast$ [/mm] ein Element der Ordnung [mm] $p^{e - 1}$ [/mm] finden (Sylow-Saetze angewand auf [mm] $(\IZ/p^e\IZ)^\ast$). [/mm] Nun ist jedoch $n - 1$ teilerfremd zu $p$, womit dieses Element hoch $2 (n - 1)$ niemals gleich 1 sein kann.
Edit: Tippfehler korrigiert. Man sieht hier auch: ist $p = 2$, so ist $e = 2$ doch moeglich, jedoch nicht $e [mm] \ge [/mm] 3$. Ist $p > 2$, so muss $e = 1$ sein.
Also ist $n$ quadratfrei. Jetzt kann man wie bei Korselts Kriterium zeigen: eine quadratfreie Zahl $n$ erfuellt [mm] $\forall [/mm] a [mm] \in (\IZ/n\IZ)^\ast [/mm] : [mm] a^{2 (n-1)} [/mm] = 1$ genau dann, wenn $p [mm] \mid [/mm] n$ impliziert $(p - 1) [mm] \mid [/mm] 2 (n - 1)$. Das folgt daraus, dass es zu jedem Primteiler $p$ von $n$ ein Element der Ordnung $p - 1$ in [mm] $(\IZ/n\IZ)^\ast$ [/mm] gibt, und diese Elemente zusammen die Gruppe erzeugen.
Und im Gegensatz zu Carmichael-Zahlen kann man hieraus nicht folgern, dass $n$ ungerade sein muss -- siehe die Beispiele 24, 28 und 66. Dass es mindestens drei Primfaktoren geben muss wenn die Zahl nicht prim ist kann man moeglicherweise genauso - oder zumindest aehnlich - zeigen wie bei Carmichael-Zahlen, das hab ich jetzt nicht probiert.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:32 Di 20.08.2013 | | Autor: | wauwau |
Kann man wirklich auf quadratfrei schließen, denn 28 ist eine Lösung, ist aber nicht quatratfrei ?
Leider kann man in diesem Fall auch nicht auf mind. 3 Primfaktoren schließen,
denn, wenn $ p$ und $q=2p-1$ beides Primzahlen sind, dann erfüllt $n=pq$ das abgeänderte Korselt Kriterium (also z.B. 15(3,5), 91(7,13))
und auch mit jeder Zahl n erfüllen natürlich auch die Zahlen $2^a3^bn$ diese Kriterium...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:09 Di 20.08.2013 | | Autor: | felixf |
Moin,
> Kann man wirklich auf quadratfrei schließen, denn 28 ist
> eine Lösung, ist aber nicht quatratfrei ?
da hast du Recht. Allerdings (siehe Edit): kein Primfaktor ausser 2 kann mehrfach vorkommen. Und der Primfaktor 2 kann hoechstens zweimal vorkommen.
Das Kriterium von Korselt muss man dementsprechend anpassen, ist aber nicht schwer, das kannst du auch selber :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:15 Di 20.08.2013 | | Autor: | wauwau |
Da n= 24 ebenfalls Lösung ist, kann der Primfaktor 2 von n auch mehr als 2 mal vorkommen...
Irgendetwas stimmt noch immer nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:51 Di 20.08.2013 | | Autor: | felixf |
Moin,
> Da n= 24 ebenfalls Lösung ist, kann der Primfaktor 2 von n
> auch mehr als 2 mal vorkommen...
> Irgendetwas stimmt noch immer nicht?
ja, da ist noch ein Fehler drin. Er ist sehr einfach zu finden (hat mich ein paar Sekunden gekostet). Jetzt eine Aufgabe fuer dich: finde ihn selber :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:50 Mi 21.08.2013 | | Autor: | wauwau |
Ich finde den Fehler leider nicht und habe auch einen elementaren "Beweis" warum [mm] $2^3$ [/mm] nicht in n vorkommen darf
sei $n=2^la$ mit $a$ ungerade und $l [mm] \ge [/mm] 3$, dann ist [mm] $(1+2^{l-2}a,n)=1$ [/mm]
es müsste also [mm] $(1+2^{l-2}a)^{2(n-1)} \equiv [/mm] 1 [mm] \mod [/mm] n$ gelten.
Nun ist aber
[mm] $(1+2^{l-2}a)^{2(n-1)} \equiv 1+2^{l-1}a(n-1) \mod 2^l \equiv 1-2^{l-1}a \not \equiv [/mm] 1 [mm] \mod 2^l$
[/mm]
daher auch nicht [mm] $\equiv [/mm] 1 [mm] \mod [/mm] n$
Wo ist mein Fehler, denn 24 ist ja doch eine Lösung.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:00 Mi 21.08.2013 | | Autor: | felixf |
Moin!
> Ich finde den Fehler leider nicht
Tipp: sind alle Sylow-UG zyklisch?
> und habe auch einen elementaren "Beweis" warum [mm]2^3[/mm] nicht in n
> vorkommen darf
>
> sei [mm]n=2^la[/mm] mit [mm]a[/mm] ungerade und [mm]l \ge 3[/mm], dann ist
> [mm](1+2^{l-2}a,n)=1[/mm]
>
> es müsste also [mm](1+2^{l-2}a)^{2(n-1)} \equiv 1 \mod n[/mm]
> gelten.
> Nun ist aber
> [mm](1+2^{l-2}a)^{2(n-1)} \equiv 1+2^{l-1}a(n-1) \mod 2^l \equiv 1-2^{l-1}a \not \equiv 1 \mod 2^l[/mm]
Moment! Es ist doch $(1 + [mm] 2^{l-2} a)^{2 (n-1)} [/mm] = 1 + [mm] \binom{2 (n-1)}{1} 2^{l-2} [/mm] a + [mm] \binom{2 (n-1)}{2} 2^{2 l - 4} a^2 [/mm] + ...$, wobei die letzten Terme kongruent 0 modulo [mm] $2^l$ [/mm] sind. Jedoch muss der Term [mm] $\binom{2(n-1)}{2} 2^{2 l - 4} a^2$ [/mm] nicht kongruent zu 0 modulo [mm] $2^l$ [/mm] sein, denn $2 l - 4$ muss nicht [mm] $\ge [/mm] l$ sein. Das ist erst ab $l = 4$ der Fall.
Wenn also $l [mm] \ge [/mm] 4$ ist, dann funktioniert dein Argument. Ist dagegen $l = 3$, dann hast du noch den Term $(n - 1) (2 n - 3) [mm] 2^{2 l - 4} a^2$, [/mm] der kongruent zu $3 [mm] \cdot a^2 \cdot 2^{2 l - 4}$ [/mm] ist.
Im Fall $l = 3$ haben wir also $(1 + 2 [mm] a)^{2 (n-1)} \equiv [/mm] 1 - 4 a + 4 [mm] \cdot [/mm] 3 [mm] a^2 \equiv [/mm] 1 + 4 + 4 [mm] \equiv [/mm] 1 [mm] \pmod{8}$ [/mm] und alles ist in Ordnung.
Damit hast du nur gezeigt: [mm] $\ell \ge [/mm] 4$ geht nicht.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:45 Mi 21.08.2013 | | Autor: | wauwau |
Groschen ist gefallen.
Damit kann man folgendes geändertes Korselt Kriterium formulieren
Eine Zahl $n$ erfüllt genau dann das "abgeschwächte" Fermat Kriterium [mm] $a^{2(n-1)}\equiv [/mm] 1 [mm] \mod [/mm] n$ für alle $a$ mit $(a,n)$=1 wenn
1. Die Zahl die Form $2^lm$ hat mit $l [mm] \le [/mm] 3$ und $m$ quadratfrei
2. für jeden Primfaktor $p$ von $n$ gilt $p-1|2(n-1)$
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:38 Mi 21.08.2013 | | Autor: | reverend |
Hallo wauwau,
das sieht gut aus, bis auf eine kleine Ungenauigkeit:
> Damit kann man folgendes geändertes Korselt Kriterium
> formulieren
>
> Eine Zahl [mm]n[/mm] erfüllt genau dann das "abgeschwächte" Fermat
> Kriterium [mm]a^{2(n-1)}\equiv 1 \mod n[/mm] für alle [mm]a[/mm] mit [mm](a,n)[/mm]=1
> wenn
> 1. Die Zahl die Form [mm]2^lm[/mm] hat mit [mm]l \le 3[/mm] und [mm]m[/mm]
> quadratfrei
...und ungerade.
> 2. für jeden Primfaktor [mm]p[/mm] von [mm]n[/mm] gilt [mm]p-1|2(n-1)[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:44 Di 20.08.2013 | | Autor: | wauwau |
finde alle n, sodass für alle $a$ mit $(a,6)=1$
[mm] $a^{2.3^n} \equiv [/mm] 1 [mm] \mod 3^n$ [/mm] gilt, oder zeige, dass keine Lösung exisitiert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:26 Di 20.08.2013 | | Autor: | wauwau |
ok wenn nach Fermat
[mm] $(a^3)^2 \equiv [/mm] 1 [mm] \mod [/mm] 3$
dann ist
[mm] $a^{2.3^n}=(a^{2.3})^{3^{n-1}} \equiv [/mm] 1 [mm] \mod 3^n$
[/mm]
ist also für alle n erfüllt.
|
|
|
|
