Autor |
Beitrag |
sol@ti
Unregistrierter Gast
| Veröffentlicht am Montag, den 29. Juli, 2002 - 19:33: |
|
Holger hatte in der Schule wieder mal zu wenig aufgepasst und bei der Schularbeit den "kleinen Fermat" falsch hingeschrieben: Für jede natürliche Zahl n gilt: a^n = 1 (mod n) , für alle a mit ggT(a,n)=1 "Ganz falsch!!!", schrieb der Lehrer mit roter Tinte darunter. Doch dann dachte er bei sich: "Klingt eigentlich gar nicht so schlecht, ob das wohl für einige n tatsächlich gilt?" Ja, das ist die Frage: Für welche natürlichen Zahlen n gilt: a^n = 1 (mod n) , für alle a mit ggT(a,n)=1 ?
|
Walter H. (mainziman)
Fortgeschrittenes Mitglied Benutzername: mainziman
Nummer des Beitrags: 89 Registriert: 05-2002
| Veröffentlicht am Montag, den 29. Juli, 2002 - 21:17: |
|
Hi, Für a element IP und n = a + 1 gilt des sicher Gruß, Walter Mainzi Man, ein Mainzelmännchen, das gerne weiterhilft oder auch verwirrt *ggg*
|
Walter H. (mainziman)
Fortgeschrittenes Mitglied Benutzername: mainziman
Nummer des Beitrags: 90 Registriert: 05-2002
| Veröffentlicht am Montag, den 29. Juli, 2002 - 21:21: |
|
pardon umgekehrt n element P und a = n + 1 jetzt stimmts. Mainzi Man, ein Mainzelmännchen, das gerne weiterhilft oder auch verwirrt *ggg*
|
sol@ti
Unregistrierter Gast
| Veröffentlicht am Montag, den 29. Juli, 2002 - 21:59: |
|
Hallo Walter, das stimmt schon, aber es sollte für alle a mit ggT(a,n)=1 gelten, nicht nur für eines! sol@ti |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 542 Registriert: 05-2000
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 04:10: |
|
Endlich Zahlentheorie, die ich verstehe) Die Menge der a<n mit ggT(a,n)=1 ist eine zyklische Gruppe der Ordnung j(n). Die Behauptung gilt also gdw j(n)|n. Sei n=Pi=1mpiki mit p1<...<pm Primzahlen. Dann gilt j(n)=Pi=1m(pi-1)piki-1 | Pi=1mpiki. Kürzen gleicher Terme auf beiden Seiten folgt Pi=1m(pi-1)|Pi=1mpi. Es folgt pm|Pi=1mpi. Da pm prim ist, folgt pm|pj für ein j. Daraus folgt aber schon pm=2, und m=1. Ist andererseits n=2k, so folgt j(n)=2k-1|2k=n, also die Behauptung. Die Menge aller n, die die Behauptung erfüllen, ist also genau die Menge der Zweierpotenzen. viele Grüße SpockGeiger |
Küken
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 06:30: |
|
Hallo Walter, hast Du die Frage nicht verstanden? |
Walter H. (mainziman)
Fortgeschrittenes Mitglied Benutzername: mainziman
Nummer des Beitrags: 91 Registriert: 05-2002
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 06:41: |
|
Hi sol@ti, na die Menge P is aber a bissi mehr als nur ein Element, jede Menge is da drin (alle Primzahlen) Gruß, Walter p.s. scheint so, daß des a andere Lösung ist als die von SpockGeiger; stellt aber keinen Wiederspruch dar; @Küken: Hä? Mainzi Man, ein Mainzelmännchen, das gerne weiterhilft oder auch verwirrt *ggg*
|
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 109 Registriert: 10-2001
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 09:43: |
|
So wie ich das sehe ist 4³ == 1 mod 3 (nach Walter) und damit kann Spockgeiger nicht sagen "Die Menge aller n, die die Behauptung erfüllen, ist also genau die Menge der Zweierpotenzen". Mir scheint die Lösung von Spockgeiger ist nur ein Teil des Ganzen. Murray |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 543 Registriert: 05-2000
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 10:25: |
|
Hi Murray Natürlich ist 43=1 mod 3, da 4=1 mod 3. Aber es soll doch für alle a mit ggT(a,n)=1 gelten! Und 23=8=2¹1 mod 3. Also erfüllt 3 die Bedingung nicht. viele Grüße SpockGeiger PS: Jetzt bin ich schon Senior-Mitglied!! *grummel* Jetzt bindet mir sogar dieses komische Board auf die Nase, dass ich alt bin... (Beitrag nachträglich am 30., Juli. 2002 von SpockGeiger editiert) |
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 110 Registriert: 10-2001
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 11:01: |
|
Na warte mal, habe ich da was falsch verstanden? Ich dachte immer ggT(a,b) = 1 ist nur ein Ausdruck für "a und b sind teilerfremd". Wenn b aber Prim ist und a = b+1, dann sind sie in jedem Falle teilerfremd. SpockGeiger und Sol@ti ihr seit sicherlich die besseren Mathematiker, also erklärt mir mal bitte was ich verkehrt verstanden habe. Murray |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 544 Registriert: 05-2000
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 11:52: |
|
Hi Murray Ich kann es gern versuchen. Den Teil mit dem ggT hast Du richtig verstanden. Allerdings gibt es da wohl zunächst noch Probleme mit Kongruenzrechnen. Es ist eigentlich etwas umständlich a=n+1 zu betrachten, denn uns interressiert ja nur das Ergebnis modulo n. Und das tolle an Kongruenzen ist ja, dass man sie jederzeit bilden kann, also kann ich auch rechnen (n+1)n mod n = 1n mod, indem ich n+1=1 mod n ausnutze. Und dass das letztere 1 ist, dürfte klar sein. Jetzt zu dem (wahrscheinlich) eigentlichen Problem: Wir suchen diejenigen Zahlen n, zu denen alle teilerfremden a die Gleichung an=1 mod n erfüllen. Bei Deinem Beispiel n=3 hast Du nur das eine a=n+1=3+1 (=1, siehe oben) erfüllen können. Aber a=2 ist auch gültig, denn 2 und 3 sind teilerfremd, und a=2 erfüllt die Gleichung nicht, also gilt für n=3 nicht, dass alle zu n=3 teilerfremden Zahlen a die Gleichung a3=1 mod 3 erfüllen (denn a=2 ist ein "Ausreißer"). viele Grüße SpockGeiger |
sol@ti
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:12: |
|
Hallo SpockGeiger, das ist ein sehr eleganter Ansatz und die Zweierpotenzen erfüllen tatsächlich die Bedingung. Aber Murray hat den Nagel auf den Kopf getroffen wenn er sagt das sei "nur ein Teil des Ganzen". Die Sache ist doch komplizierter: 1) Außer den Zweierpotenzen gibt es noch andere n mit f(n)|n . 2) f(n)|n ist keine notwendige Bedingung dafür, dass für n der "falsche Fermat" gilt. Hallo Walter & Murray! Vielleicht habe ich die Frage missverständlich formuliert. SpockGeiger hat es dankenswerter Weise bereits erklärt, ein ausführliches Beispiel kann sicher nicht schaden: Annahme: n=10 erfüllt die Bedingung (hat niemand von euch behauptet, ist nur ein Beispiel!). 1.) Finde alle Zahlen a<10 mit ggT(a,10)=1: a=1,3,7,9. Bem.: Die Euler'sche f-Funktion ist ja gerade die Anzahl dieser teilerfremden Zahlen, also f(10)=4. 2.) Überprüfe, ob für alle diese a gilt: a^n = 1 (mod n). 1^10 = 1 (mod 10) ... stimmt 3^10 = 1 (mod 10) ... falsch, 3^10 = 59049 = 9 (mod 10) Damit haben wir ein a=3 gefunden, das die Bedingung nicht erfüllt. Dies ist ein Widerspruch zur Annahme! ==> n=10 ist (erwartungsgemäß) keine Zahl, für die der "falsche Fermat" gilt. Viele Grüße sol@ti
|
Onkel Murray (murray)
Erfahrenes Mitglied Benutzername: murray
Nummer des Beitrags: 111 Registriert: 10-2001
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:13: |
|
Achsoooo, dann habe ich tatsächlich die Aufgabenstellung nicht richtig verstanden. Onkel "Modulo" Murray |
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 545 Registriert: 05-2000
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 13:48: |
|
Hallo sol@ti Mit 1) hast Du völlig recht. Hab mich mal wieder verhauen. Hab aus pm-1 pm gemacht und dann wieder zurück. Hab nun zumindest als notwendige Bedingung 2kpl mit Primzahl p raus. Dass sie nicht hinreichend ist, sieht man an Deinem Beispiel. 2) Wieso nicht? Die Gruppe G der invertierbaren Elemente modulo n ist zyklisch, also gilt insbesondere für einen Erzeuger e: en=1, also j(n)=ord(G)=ord(e)|n. Wo ist der Fehler? viele Grüße SpockGeiger |
sol@ti
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 16:06: |
|
Hallo SpockGeiger, zu 1) 2kpl ist ein guter Ansatz. zu 2) Die Einheitengruppe modulo n muss nicht zyklisch sein. Viele Grüße sol@ti
|
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 546 Registriert: 05-2000
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 16:48: |
|
Hi sol@ti Oooops, ich dachte, das Ding wäre immer zyklisch, damit ist natürlich der größte Teil meines Beweises für'n . Nur für mein Gewissen, kennst Du ein Beispiel? BTW: Solati kommt mir irgendwie bekannt vor, hast Du den Nick aus nem Film? viele Grüße SpockGeiger
|
sol@ti
Unregistrierter Gast
| Veröffentlicht am Dienstag, den 30. Juli, 2002 - 17:40: |
|
Hallo SpockGeiger, es gibt da einen Satz von Gauss: Die Einheitengruppe modulo n ist zyklisch, wenn n=2, n=4, n=pk oder n=2pk, (k eine natürliche Zahl und p>2 prim). Zum Beispiel für n=12 ist sie nicht zyklisch. BTW: sol@ti ist nicht aus nem Film sondern aus ner Tüte: Soletti Salzstangen (ich knabber gerade wieder eine) Viele Grüße sol@ti
|
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 547 Registriert: 05-2000
| Veröffentlicht am Freitag, den 02. August, 2002 - 02:35: |
|
Hi sol@ti Danke für die Erläuterungen. Ich hab mir mal einige Beispiele angeschaut, aber ich kann kein System entdecken (außer dass die gesuchten Zahlen gerade sind;). Es gibt nicht zufällig eine komplette Charakterisierung der Einheitsgruppe? viele Grüße SpockGeiger |
sol@ti
Unregistrierter Gast
| Veröffentlicht am Freitag, den 02. August, 2002 - 16:01: |
|
Hallo SpockGeiger, du warst schon sehr nah dran, bravo! Nach dem Satz von Euler ist a^f(n) = 1 (mod n) und damit (deine Idee!) ist f(n)|n hinreicheind für a^n = 1 (mod n). Das sind die Zahlen der Form n = 2k3l , k>=1, l>=0. Nun gibt es eine Verschärfung dieses Satzes und darauf wollte ich eigentlich hinaus: Nach dem Satz von Carmichael ist bereits l(n)|n hinreichend für a^n = 1 (mod n). Wie du bemerkt hast gibt es scheinbar kein System, um die Menge der n mit l(n)|n vollständig zu beschreiben. Mir ist aber folgendes aufgefallen: die gesuchte Zahlenfolge ist 2,4,6,8,12,16,18,20,24,32,36,40,42,48,54,60,64,72,80,84,96,100,... Natürlich liegt eine Suche in der Sloane-Datenbank nahe, und tatsächlich: A068563: n such that 2^n (mod n) = 4^n (mod n) aber kein Wort von Carmichael! Daher hab ich noch etwas weiter gesucht und siehe da, 136 gehört zu A068563 aber l(136)=16 ist kein Teiler von 136 (die folgenden 144,156,160,... passen wieder). Ich glaube unsere Lösungsfolge ist eine Teilfolge von A068563. Und für die (wenigen) "falschen" Zahlen in A068563 vermute ich einen Zusammenhang mit Vielfachen von Fermatzahlen Fm=2^(2^m)+1. Wer mit f(n) und der Carmichael-Funktion l(n) experimentieren will, findet hier ein praktisches Applet. Wem es gelingt den genauen Zusammenhang zwischen A068563 und l(n)|n aufzudecken, ist zumindest ein Eintrag in Sloane's Datenbank sicher! Noch eine letzte Bemerkung: Für die Carmichael-Zahlen gilt bekanntlich l(n)|n-1 Viele Grüße sol@ti
|
SpockGeiger (spockgeiger)
Senior Mitglied Benutzername: spockgeiger
Nummer des Beitrags: 548 Registriert: 05-2000
| Veröffentlicht am Samstag, den 03. August, 2002 - 02:03: |
|
Hi sol@ti Wie Du sicherlich schon bemerkt hast, bin ich in Zahlentheorie bei weitem nicht so bewandert wie Du. Die Bezeichnung l(n) ist mir unbekannt. Und was sagt der Satz von Charmichael aus? viele Grüße SpockGeiger |
Carmichael (carmichael)
Mitglied Benutzername: carmichael
Nummer des Beitrags: 24 Registriert: 02-2001
| Veröffentlicht am Samstag, den 03. August, 2002 - 14:27: |
|
Hi sol@ti, ich dachte schon fast, du hättest eine 'Formel' gefunden, die die gesuchten Zahlen beschreibt. ;) ich schreibe die Bedingung nochmal hin (sei n = 2^k*p_1^i_1*...*p_m^i_m die Primfaktorzerlegung von n): kgV(2^(k-2),(p_1-1)*p_1^(i_1-1),...,(p_m-1)*p_m^(i_m-1)) teilt 2^k*p_1^i_1*...*p_m^i_m; (k>=3) gdw. (*) kgV(p_1-1,...,p_m-1) teilt 2^k*p_1^i_1*...*p_m^i_m; (Bedingung für die Folge für alle k) Ordnet man nun o.B.d.A. die Primzahlen an p_1<p_2<...<p_m dann lässt sich ein bisschen was über n aussagen: p_1-1 besitzt nur Teiler <p_1. => p_1-1 | 2^k; => p_1 = 2^l+1 mit l<=k; p_1 muss also Fematprimzahl sein. für p_2 analog: p_2-1 teilt 2^k*p_1^i_1. also: p_2 = 2^u*p_1^v mit u <=k und v <=i_1; usw. Aus (*) ergibt sich auch noch sofort: erfüllt n die Bedingung, dann auch n*p mit p Primfaktor von n zu 4^n = 2^n (mod n): umgeformt: n | 2^n(2^n-1); (**) Sei n wieder in Primfaktoren zerlegt =2^k*p_1^i_1*...*p_m^i_m: dann gilt: (**) gdw. p_1^i_1*...*p_m^i_m | 2^n-1; gdw. 2^(2^k*p_1^i_1*...*p_m^i_m) = 1 (mod p_1^i_1*...*p_m^i_m); Diese Bedinung ist auf jeden Fall erfüllt, wenn (*) erfüllt ist. => Unserer Folge ist eine Teilfolge von n mit 4^n = 2^n (mod n). MfG Carmichael
|
sol@ti
Unregistrierter Gast
| Veröffentlicht am Samstag, den 03. August, 2002 - 18:39: |
|
Hallo Carmichael, wenn einer diese 'Formel' findet, dann bist es du ;-) Sehr interessant sind deine Bedingung (*) und die Folgerungen daraus. Insbesondere beweist das auch SpockGeigers Beobachung, dass in unserer Folge nur gerade Zahlen vorkommen. Außerdem müssen alle Folgenglieder n>2 durch 3 oder 4 teilbar sein. Vielen Dank auch für den Beweis der Teilfolgen-Vermutung. Aber welche Zahlen aus A068563 nun genau wegfallen wird wohl ein Rätsel bleiben? Hallo SpockGeiger, ich habe nur bemerkt, dass du sehr fundierte Kenntnisse in Zahlentheorie hast! Kurz gesagt ist die Carmichael-Funktion l(n) der Exponent der Einheitengruppe modulo n. Die Ordnung ist ja f(n). l(n)=max(ord(a)) für alle a mit ggT(a,n)=1. Damit ist l(n) ein echter Teiler von f(n), wenn die Einheitengruppe nicht zyklisch ist. Im Satz von Carmichael wird gezeigt, dass l(n)=kgV(2^j,(p1-1)*p1^(i1-1),...,(pm-1)*pm^(im-1)) wenn n die Primfaktorzerlegung 2^k*p1^i1*...*pm^im hat (mit j=0,1,1 für k=0,1,2 und j=k-2 für k>2). Und der Bezug zum Rätsel: l(n) ist die kleinste natürliche Zahl, sodass a^l(n) = 1 (mod n) für alle a mit ggT(a,n)=1. viele Grüße sol@ti
|
|