Carmichael-Zahlen

Neue Frage »

Bjoern1982 Auf diesen Beitrag antworten »
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
AD 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 mit der Menge der Primteiler ist genau dann eine Carmichael-Zahl, wenn für jedes gilt:

teilt .


Im vorliegenden Fall wären das die drei Bedingungen

, offenbar erfüllt, sofern





Auch wenn ich das noch nicht durchgerechnet habe - es sieht m.E. vielversprechend aus.
 
 
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.
AD Auf diesen Beitrag antworten »

Die erste Bedingung ist schon mal für alle ungeraden automatisch erfüllt. Da ich annehme, dass die drei Primzahlen verschieden sein sollen, kann man o.B.d.A. annehmen.

Dann ist das Diophantische Gleichungssystem



zu lösen. Aus folgt sofort

Nun kann man z.B. eliminieren: Zweite Gleichung mit 3 multiplizieren und erste Gleichung einsetzen ergibt



Wegen folgt unmittelbar . Andererseits folgt aus und auch

,

was dann zu führt. (*) kann man nun nach Multiplikation mit noch mal etwas umschreiben:




Bleiben also nur die Fälle für (**) zu untersuchen:


1.Fall : (**) ergibt .

In Primzahlen gibt das nur die Möglichkeiten , die beide zu nichtganzzahligem führen.


2.Fall : (**) ergibt , also .

In Primzahlen gibt das nur die Möglichkeiten . Ersteres führt wieder zu nichtganzzahligem , letzteres aber zur Lösung .


3.Fall : (**) ergibt , also .

Hier gibt es gar keine Primzahl als Lösungskandidaten.

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

Summa summarum gibt es also tatsächlich nur die eine Lösung .


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.
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
Bjoern1982 Auf diesen Beitrag antworten »

Für Interessierte noch eine alternative Lösung:

--> 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:

Weiter gilt 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

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
AD Auf diesen Beitrag antworten »

Zitat:
Original von Bjoern1982
--> 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:

in die andere Gleichung (ich nenne sie mal ) eingesetzt ergibt , wieder umgestellt der besseren Faktorisierung wegen zu

.

Hier ist sofort sichtbar, dass als Primzahl für nur in Frage kommt.
Bjoern1982 Auf diesen Beitrag antworten »

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



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »