Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Der falsche Fermat

ZahlReich - Mathematik Hausaufgabenhilfe » Denksport » Zahlenrätsel » Der falsche Fermat « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Montag, den 29. Juli, 2002 - 19:33:   Beitrag drucken

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 ?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Walter H. (mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Fortgeschrittenes Mitglied
Benutzername: mainziman

Nummer des Beitrags: 89
Registriert: 05-2002
Veröffentlicht am Montag, den 29. Juli, 2002 - 21:17:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Walter H. (mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Fortgeschrittenes Mitglied
Benutzername: mainziman

Nummer des Beitrags: 90
Registriert: 05-2002
Veröffentlicht am Montag, den 29. Juli, 2002 - 21:21:   Beitrag drucken

pardon umgekehrt n element P und a = n + 1
jetzt stimmts.
Mainzi Man,
ein Mainzelmännchen,
das gerne weiterhilft
oder auch verwirrt *ggg*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Montag, den 29. Juli, 2002 - 21:59:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 542
Registriert: 05-2000
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 04:10:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Küken
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 06:30:   Beitrag drucken

Hallo Walter,
hast Du die Frage nicht verstanden?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Walter H. (mainziman)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Fortgeschrittenes Mitglied
Benutzername: mainziman

Nummer des Beitrags: 91
Registriert: 05-2002
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 06:41:   Beitrag drucken

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*
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 109
Registriert: 10-2001
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 09:43:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 543
Registriert: 05-2000
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 10:25:   Beitrag drucken

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)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 110
Registriert: 10-2001
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 11:01:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 544
Registriert: 05-2000
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 11:52:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:12:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Onkel Murray (murray)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: murray

Nummer des Beitrags: 111
Registriert: 10-2001
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:13:   Beitrag drucken

Achsoooo, dann habe ich tatsächlich die Aufgabenstellung nicht richtig verstanden.

Onkel "Modulo" Murray
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 545
Registriert: 05-2000
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 13:48:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 16:06:   Beitrag drucken

Hallo SpockGeiger,

zu 1) 2kpl ist ein guter Ansatz.
zu 2) Die Einheitengruppe modulo n muss nicht zyklisch sein.

Viele Grüße
sol@ti
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 546
Registriert: 05-2000
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 16:48:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Dienstag, den 30. Juli, 2002 - 17:40:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 547
Registriert: 05-2000
Veröffentlicht am Freitag, den 02. August, 2002 - 02:35:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Freitag, den 02. August, 2002 - 16:01:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

SpockGeiger (spockgeiger)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: spockgeiger

Nummer des Beitrags: 548
Registriert: 05-2000
Veröffentlicht am Samstag, den 03. August, 2002 - 02:03:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Carmichael (carmichael)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Mitglied
Benutzername: carmichael

Nummer des Beitrags: 24
Registriert: 02-2001
Veröffentlicht am Samstag, den 03. August, 2002 - 14:27:   Beitrag drucken

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

Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

sol@ti
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Samstag, den 03. August, 2002 - 18:39:   Beitrag drucken

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

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page