Carmichael-Zahlen

11.11.2008, 01:27

Bjoern1982

Carmichael-Zahlen

Hallo,

wie bestimme ich alle Carmichael-Zahlen der Form 3pq mit p,q prim ?
Als Hinweis ist noch gegeben, dass es nur endlich viele gibt.

Gruß Björn

11.11.2008, 09:08

Auf diesen Beitrag antworten »

Zuerst mal sollte man nach leichter überprüfbaren Kriterien für eine Carmichael-Zahl suchen. Laut Wikipedia gilt etwa

Zitat:

Eine Zahl $\begin{eqnarray*} n \end{eqnarray*}$ mit der Menge der Primteiler $\begin{eqnarray*} P \end{eqnarray*}$ ist genau dann eine Carmichael-Zahl, wenn für jedes $\begin{eqnarray*} p\in P \end{eqnarray*}$ gilt:

$\begin{eqnarray*} p - 1 \end{eqnarray*}$ teilt $\begin{eqnarray*} \frac{n}{p}-1 \end{eqnarray*}$ .

Im vorliegenden Fall wären das die drei Bedingungen

$\begin{eqnarray*} 2 | (pq-1) \end{eqnarray*}$ , offenbar erfüllt, sofern $\begin{eqnarray*} p,q>2 \end{eqnarray*}$

$\begin{eqnarray*} (p-1) | (3q-1) \end{eqnarray*}$

$\begin{eqnarray*} (q-1) | (3p-1) \end{eqnarray*}$

Auch wenn ich das noch nicht durchgerechnet habe - es sieht m.E. vielversprechend aus.

13.11.2008, 02:47

Bjoern1982

Auf diesen Beitrag antworten »

Ich habs versucht, aber bei 3 Gleichungen mit 5 Unbekannten wird das sehr unschön.

Oder wolltest du gar nicht auf das Lösen eines Gleichungssystem hinaus ?

Btw nach Betrachtung einiger Carmichael Zahlen Tabellen wird es wohl nur genau eine Lösung mit 3*11*17=561 als gleichzeitig kleinste Carmichael Zahl geben.

13.11.2008, 10:21

Auf diesen Beitrag antworten »

Die erste Bedingung $\begin{eqnarray*} 2|(pq-1) \end{eqnarray*}$ ist schon mal für alle ungeraden $\begin{eqnarray*} p,q \end{eqnarray*}$ automatisch erfüllt. Da ich annehme, dass die drei Primzahlen $\begin{eqnarray*} 3,p,q \end{eqnarray*}$ verschieden sein sollen, kann man o.B.d.A. $\begin{eqnarray*} p>q\geq 5 \end{eqnarray*}$ annehmen.

Dann ist das Diophantische Gleichungssystem

$\begin{eqnarray*} 3q-1 &=& u(p-1)\\ 3p-1 &=& v(q-1) \end{eqnarray*}$

zu lösen. Aus $\begin{eqnarray*} p>q\geq 5 \end{eqnarray*}$ folgt sofort $\begin{eqnarray*} 1\leq u<v \end{eqnarray*}$

Nun kann man z.B. $\begin{eqnarray*} q \end{eqnarray*}$ eliminieren: Zweite Gleichung mit 3 multiplizieren und erste Gleichung einsetzen ergibt

$\begin{eqnarray*} 9p-3 = v(3q-3) = v(u(p-1)-2) = uv(p-1)-2v \quad\Rightarrow\quad 2v+6 = (uv-9)(p-1)\qquad (*) \end{eqnarray*}$

Wegen $\begin{eqnarray*} p-1>0 \end{eqnarray*}$ folgt unmittelbar $\begin{eqnarray*} uv>9 \end{eqnarray*}$ . Andererseits folgt aus $\begin{eqnarray*} p\geq 7 \end{eqnarray*}$ und $\begin{eqnarray*} v>u \end{eqnarray*}$ auch

$\begin{eqnarray*} 2v+6 \geq 6(uv-9)\quad\Rightarrow\quad 60\geq 6uv-2v = 2(3u-1)v > 2(3u-1)u \end{eqnarray*}$ ,

was dann zu $\begin{eqnarray*} u\leq 3 \end{eqnarray*}$ führt. (*) kann man nun nach Multiplikation mit $\begin{eqnarray*} u \end{eqnarray*}$ noch mal etwas umschreiben:

$\begin{eqnarray*} 6u+18 = (uv-9)(up-u-2)\qquad (**) \end{eqnarray*}$

Bleiben also nur die Fälle $\begin{eqnarray*} u=1,2,3 \end{eqnarray*}$ für (**) zu untersuchen:

1.Fall $\begin{eqnarray*} u=1 \end{eqnarray*}$ : (**) ergibt $\begin{eqnarray*} 24 = (v-9)(p-3) \end{eqnarray*}$ .

In Primzahlen gibt das nur die Möglichkeiten $\begin{eqnarray*} p=7,11 \end{eqnarray*}$ , die beide zu nichtganzzahligem $\begin{eqnarray*} q \end{eqnarray*}$ führen.

2.Fall $\begin{eqnarray*} u=2 \end{eqnarray*}$ : (**) ergibt $\begin{eqnarray*} 30 = (2v-9)(2p-4) \end{eqnarray*}$ , also $\begin{eqnarray*} 15 = (2v-9)(p-2) \end{eqnarray*}$ .

In Primzahlen gibt das nur die Möglichkeiten $\begin{eqnarray*} p=7,17 \end{eqnarray*}$ . Ersteres führt wieder zu nichtganzzahligem $\begin{eqnarray*} q \end{eqnarray*}$ , letzteres aber zur Lösung $\begin{eqnarray*} q=11 \end{eqnarray*}$ .

3.Fall $\begin{eqnarray*} u=3 \end{eqnarray*}$ : (**) ergibt $\begin{eqnarray*} 36 = (3v-9)(3p-5) \end{eqnarray*}$ , also $\begin{eqnarray*} 12 = (v-3)(3p-5) \end{eqnarray*}$ .

Hier gibt es gar keine Primzahl $\begin{eqnarray*} p\geq 7 \end{eqnarray*}$ als Lösungskandidaten.

----------------------------------------

Summa summarum gibt es also tatsächlich nur die eine Lösung $\begin{eqnarray*} p=17,q=11 \end{eqnarray*}$ .

Ich will nicht behaupten, dass das eben der Königweg zur Lösung dieses Diophantischen Gleichungssystems ist: Es geht vielleicht hier und da etwas kürzer bzw. einfacher, aber es funktioniert. Augenzwinkern

Leitgedanke hinter all den Umformungen ist das Erreichen dieser Produktstruktur.

13.11.2008, 10:44

Bjoern1982

Auf diesen Beitrag antworten »

Was soll ich sagen...Gott sei Dank musste ich gerade nochmal umkehren um den Autoschlüssel zu holen weil die Bahnen hier nicht kamen und habe dann jetzt zufällig deinen Beitrag noch gesehen, den ich mir dann gleich in der Uni noch genauer anschauen werde und das passt dann auch noch prima bis 14 Uhr zur Abgabe Tanzen

Ein herzliches Dankeschön smile

14.11.2008, 19:40

Bjoern1982

Auf diesen Beitrag antworten »

Für Interessierte noch eine alternative Lösung:

$\begin{eqnarray*} 3p-1 &=& b(q-1) \end{eqnarray*}$ --> o.B.d.A. p<q

=> b=1 oder b=2

b=1: q-1=3p-1 <=> q=3p --> kann nicht sein da CM quadratfrei is

b=2: $\begin{eqnarray*} q=\frac{3p+1}{2} \end{eqnarray*}$

Weiter gilt $\begin{eqnarray*} 3q \equiv 1\ mod\ (p-1) \end{eqnarray*}$ mit 3q=0,5(9p+3)=0,5(9(p-1)+12)=0,5(8(p-1)+p+11)=4(p-1)+0,5(p+11)

Also gilt $\begin{eqnarray*} 1 \equiv 3q \equiv 0,5(p+11)\ mod\ (p-1) \end{eqnarray*}$

für p>11 folgt p+11<2p => 0,5(p+11)<p>1 => 0,5(p+11) nicht kongruent 1 mod (p-1)

=> p muss kleiner oder gleich 11 sein, also muss man nur noch den Test für p=5,7 oder 11 machen und nur mit p=11 funktioniert es

=> q=0,5(3*11+1)=0,5*34=17

14.11.2008, 22:07

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
$\begin{eqnarray*} 3p-1 &=& b(q-1) \end{eqnarray*}$ --> o.B.d.A. p<q

=> b=1 oder b=2

Oh ja, na klar. Hammer

Manchmal bin ich wirklich etwas umständlich. Big Laugh

Bei der Behandlung des Falles b=2 gefällt mir meine Variante oben dann aber besser, weil viel kürzer. Eine Kombination beider Lösungen wäre also die übersichtlichste Variante:

$\begin{eqnarray*} q=\frac{3p+1}{2} \end{eqnarray*}$ in die andere Gleichung (ich nenne sie mal $\begin{eqnarray*} 3q-1 = c(p-1) \end{eqnarray*}$ ) eingesetzt ergibt $\begin{eqnarray*} 9p+1 = 2c(p-1) \end{eqnarray*}$ , wieder umgestellt der besseren Faktorisierung wegen zu

$\begin{eqnarray*} 10 = (2c-9)(p-1) \end{eqnarray*}$ .

Hier ist sofort sichtbar, dass als Primzahl für $\begin{eqnarray*} p \end{eqnarray*}$ nur $\begin{eqnarray*} p=11 \end{eqnarray*}$ in Frage kommt.

14.11.2008, 23:00

Bjoern1982

Auf diesen Beitrag antworten »

So, damit haben wir dann die auch die eleganteste Lösung wie ich finde smile

Neue Frage »

Antworten »

Carmichael-Zahlen

Verwandte Themen