Carmichael-Zahlen

17.12.2005, 15:56

irre.flexiv

Auf diesen Beitrag antworten »

Carmichael-Zahlen

Hallo, hat jemand eine Idee wie man das beweisen kann bzw. wie der Hinweis mir helfen soll? Thx

Zeigen Sie, dass es für jede Primzahl r nur endlich viel Carmichael-Zahlen der Form $\begin{eqnarray*} r\cdot p \cdot q \end{eqnarray*}$ mit $\begin{eqnarray*} p,q \in \mathbb P \end{eqnarray*}$ gibt.
"möglicher" Hinweis: Zeigen Sie, $\begin{eqnarray*} \exists \lambda \leq r-1 : (q-1) | (r-1)\cdot(r+\lambda) \end{eqnarray*}$

17.12.2005, 16:19

AD

Auf diesen Beitrag antworten »

Wenn diese Teilbarkeitseigenschaft im Hinweis wirklich stimmt, dann ist es ein Hinweis, und nicht nur ein "möglicher" Hinweis:

Denn es gibt nur endlich viele solche positiven Zahlen $\begin{eqnarray*} (r-1)\cdot(r+\lambda) \end{eqnarray*}$ , die dann natürlich auch nur endlich viele Teiler haben können, was dann nur endlich viele $\begin{eqnarray*} q \end{eqnarray*}$ (und analog $\begin{eqnarray*} p \end{eqnarray*}$ ) zur Folge hat.

Aber wie man diese Eigenschaft im Hinweis nachweist - keine Ahnung. Da weißt du sicher mehr als ich, der gerade erstmal in der Wikipedia gelesen hat, was Carmichael-Zahlen überhaupt sind. Augenzwinkern

Augenzwinkern

17.12.2005, 16:26

irre.flexiv

Auf diesen Beitrag antworten »

Och man darauf hätt ich auch kommen können.
Danke für den Hinweis smile

smile

18.12.2005, 01:42

irre.flexiv

Auf diesen Beitrag antworten »

Hm, ich bin verwirrt.

Wenn man z.B. die erste Carmichael-Zahl 3*11*17 nimmt gibt es kein lambda<3 so dass (17-1)|(3-1)(3+lambda).

verwirrt

18.12.2005, 11:01

AD

Auf diesen Beitrag antworten »

Das hätte ich wiederum sehen können. Hmm, da kann man bedauerlicherweise den Hinweis wohl nur in die Tonne treten...

10.01.2006, 18:43

irre.flexiv

Auf diesen Beitrag antworten »

Falls es jemanden interessiert, hier ist der Beweis:

Zunächst gilt:
Sei n eine Carmichael-Zahl. Dann ist n quadratfrei, hat 3 oder mehr Primteiler und für jeden Primteiler p gilt $\begin{eqnarray*} p-1 | n-1 \end{eqnarray*}$ .
(für Beweis einmal googlen)

Ist jetzt $\begin{eqnarray*} n=rpq \end{eqnarray*}$ so folgt:
$\begin{eqnarray*} q-1|n-1 \quad\Rightarrow\quad q-1| \frac{n}{q}-1 +(q-1)\cdot\frac{n}{q}\quad\Rightarrow\quad q-1|\frac{n}{q}-1 = r\cdot p -1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad\exists\lambda >0: \lambda\cdot (q-1)= rp-1 \quad\Leftrightarrow\quad \lambda\cdot q = rp -1 +\lambda \quad (*) \end{eqnarray*}$

$\begin{eqnarray*} (\lambda=1 \quad\Rightarrow\quad q=rp \not\in \mathbb P \quad\Rightarrow\quad \lambda >1) \end{eqnarray*}$

Damit folgt jetzt:
$\begin{eqnarray*} p-1|rq-1 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad p-1|\lambda\cdot(rq-1) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad p-1|r\cdot(\lambda q)-\lambda \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow_{(*)} p-1|r\cdot(rp-1+\lambda)-\lambda \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad p-1|r\cdot (rp-1)+\lambda\cdot (r-1) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad p-1|r^2-r+\lambda\cdot (r-1) \quad\quad\quad (r\cdot(rp-1)\equiv r^2-r\mod p-1) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow\quad p-1|(r+\lambda)\cdot (r-1) \end{eqnarray*}$

Fehlt nur noch die Beschränktheit von $\begin{eqnarray*} \lambda \end{eqnarray*}$ :
o.B.d.A sei p < q $\begin{eqnarray*} \Rightarrow\quad p\leq q-1 \quad\Rightarrow\quad rp\leq r\cdot(q-1) \quad\Rightarrow\quad rp-1 < r\cdot(q-1) \quad\Rightarrow\quad r>\frac{rp-1}{q-1}=\lambda \end{eqnarray*}$

Gruss irre

Edit: Fehler korrigiert

Anzeige

10.01.2006, 18:49

AD

Auf diesen Beitrag antworten »

Zitat:

Original von irre.flexiv
$\begin{eqnarray*} q-1|n-1 \quad\Rightarrow\quad q-1| \frac{n}{q}-1 +(q-1)\cdot\frac{n}{p} \end{eqnarray*}$

Da ist bei mir schon erstmal Ende. Muss es nicht

$\begin{eqnarray*} q-1|n-1 \quad\Rightarrow\quad q-1| \frac{n}{q}-1 +(q-1)\cdot\frac{n}{q} \end{eqnarray*}$

heißen - das würde ich einsehen.

10.01.2006, 18:50

irre.flexiv

Auf diesen Beitrag antworten »

Ja

Big Laugh

blöder Tipfehler.

10.01.2006, 18:58

AD

Auf diesen Beitrag antworten »

Also ehrlich, auch im Rest ist einiges ziemlich schwer lesbar, z.B. Gleichheitszeichen wo vielleicht eher ein $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ stehen sollte, usw. Vor allem solltest du aber sagen, wieso das hier

Zitat:

Original von irre.flexiv
Hm, ich bin verwirrt.

Wenn man z.B. die erste Carmichael-Zahl 3*11*17 nimmt gibt es kein lambda<3 so dass (17-1)|(3-1)(3+lambda).

verwirrt

plötzlich hinfällig sein soll. Das Gegenbeispiel ist nämlich richtig!

Also brauchst du irgendwelche Zusatzannahmen $\begin{eqnarray*} p\leq q\leq r \end{eqnarray*}$ o.ä. ? verwirrt

verwirrt

EDIT: Ok, ich hab's geschnallt:

Zitat:

Original von irre.flexiv
o.B.d.A sei p < q

Das heißt jetzt (ausdrücklich) auf den Anfangsbeitrag des Threads bezogen, zwischendurch hast du jetzt ja die Rollen von $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} q \end{eqnarray*}$ vertauscht:

Von der Produktdarstellung $\begin{eqnarray*} n=pqr \end{eqnarray*}$ der Carmichael-Zahl darf zwar $\begin{eqnarray*} r \end{eqnarray*}$ beliebig unter den drei Primfaktoren gewählt werden, $\begin{eqnarray*} q \end{eqnarray*}$ muss dann aber die kleinere der beiden restlichen Primzahlen sein!

10.01.2006, 19:19

irre.flexiv

Auf diesen Beitrag antworten »

In der Aufgabe was der Hinweis etwas ungüstig formuliert so dass ich angenommen habe jeder Primteiler muss diese Aussage erfüllen.
Das ist aber unnötig. Man prüft einfach nochmal mit allen gefundenen Zahlen die die Aussage erfüllt haben.

n= 3*p*q
Nur p=11 erfüllt die Aussage.

n= 3*11*q
Jetzt alle q finden für die ein lambda existiert mit
(q-1) | (11-1)*(11+lambda)

Das ist nur für q=17 der Fall.

Zitat:

schwer lesbar

das verbesser ich gleich mal, ich war einfach nur etwas schreibfaul

10.01.2006, 19:41

AD

Auf diesen Beitrag antworten »

Zitat:

Original von irre.flexiv
n= 3*p*q
Nur p=11 erfüllt die Aussage.

Unter der Voraussetzung $\begin{eqnarray*} p<q \end{eqnarray*}$ stimme ich da zu.

Zitat:

Original von irre.flexiv
n= 3*11*q
Jetzt alle q finden für die ein lambda existiert mit
(q-1) | (11-1)*(11+lambda)

Das ist nur für q=17 der Fall.

Das musst du mal näher erläutern: Ich wähle $\begin{eqnarray*} \lambda=7 \end{eqnarray*}$ und sage $\begin{eqnarray*} q=19 \end{eqnarray*}$ . Was jetzt?

10.01.2006, 19:51

irre.flexiv

Auf diesen Beitrag antworten »

Ich hatte schon etwas weiter gedacht, ich meinte :
q=17 ist die einzige Wahl so das n Carmichael-Zahl ist.

10.01.2006, 19:57

AD

Auf diesen Beitrag antworten »

Und wie beweist du das? $\begin{eqnarray*} (r-1)(r+\lambda)=10(11+\lambda) \end{eqnarray*}$ hat zwar für $\begin{eqnarray*} \lambda\leq 10 \end{eqnarray*}$ insgesamt nur endlich viele Primteiler, aber das nützt dir nur was für den kleineren der beiden Restprimteiler von $\begin{eqnarray*} n=11\cdot q\cdot s \end{eqnarray*}$ , und wie oben schon festgestellt, soll ja $\begin{eqnarray*} s=3 \end{eqnarray*}$ sein. Für $\begin{eqnarray*} q>3 \end{eqnarray*}$ , und das ist ja letztendlich der interessante Fall, zieht also deine Hilfsaussage nicht!!! Die Argumentation, dass es nur endlich viele $\begin{eqnarray*} q \end{eqnarray*}$ mit Carmichael-Zahlen $\begin{eqnarray*} n=3\cdot 11\cdot q \end{eqnarray*}$ gibt, ist also so noch nicht schlüssig.

Tja, verdammtes "o.B.d.A." - es liegt eben doch eine "B.d.A." vor...

10.01.2006, 20:17

irre.flexiv

Auf diesen Beitrag antworten »

Ich bin nicht sicher ob ich dich verstanden habe.

Zitat:

Und wie beweist du das?

Wäre 3*11*19 Carmichael zahlt, so müsste 19-1 | 3*11-1 gelten, das ist aber nicht der Fall.

Aber eigentlich ist es auch egal ob das eine Carmicheal ist. Wichtig ist das wenn r fix ist es nur endlich viele Paare (p,q) gibt so das die Aussage erfüllbar ist und oben hab ich gezeigt, das jede Carmichael diese Aussage erüllt.

10.01.2006, 20:20

AD

Auf diesen Beitrag antworten »

Du hast meinen Beitrag nicht richtig durchgelesen: Mit deiner bisherigen Argumentation hast du nicht gezeigt, dass nur endlich viele $\begin{eqnarray*} q \end{eqnarray*}$ für eine Carmichael-Zahl $\begin{eqnarray*} n=3\cdot 11\cdot q \end{eqnarray*}$ in Frage kommen.

10.01.2006, 20:31

irre.flexiv

Auf diesen Beitrag antworten »

Achso.
Dafür benutze ich einfach das q-1 | r*p-1.
Da es nur endlich viele mögliche p gibt, gibt es auch nur endlich viele mögliche q.

In diesem Fall: q-1| 3*11 -1
smile

smile

10.01.2006, 20:34

AD

Auf diesen Beitrag antworten »

Das war der Baustein, der mir fehlte, danke. Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »