Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:01 Fr 08.06.2012 | | Autor: | ella87 |
| Aufgabe | 1.Teil:
finde acht aufeinanderfolgende Zahlen, die keine Primzahlen sind! (analog zu einer zuvor beschiebenen Aufgabe.
2.Teil:
Überlegen Sie sich, was eine solchen Aufgabenstellung mit dem Chinesischen Restsatz zu tun haben könnte. |
Den ersten Teil habe ich gelöst (das war leicht ;) )
[mm]2*3*4*5*6*7*8*9+2=362882[/mm]
[mm]2*3*4*5*6*7*8*9+3=362883[/mm]
[mm]2*3*4*5*6*7*8*9+4=362884[/mm]
[mm]2*3*4*5*6*7*8*9+5=362885[/mm]
[mm]2*3*4*5*6*7*8*9+6=362886[/mm]
[mm]2*3*4*5*6*7*8*9+7=362887[/mm]
[mm]2*3*4*5*6*7*8*9+8=362888[/mm]
[mm]2*3*4*5*6*7*8*9+9=362889[/mm]
aber ich verstehe nicht, was eine solche Aufgabenstellung mit dem Chinesischen Restsatz zu tun haben könnte.
Der Chinesische Restsatz besagt, dass folgendes System von linearen Kongruenzen
[mm]x \equiv c_1 (mod \; m_1 )[/mm]
[mm]x \equiv c_2 (mod \; m_2 )[/mm]
[mm]\vdots[/mm]
[mm]x \equiv c_k (mod \; m_k )[/mm]
mit [mm] m_1,...,m_k[/mm] paarweise teilerfremd und [mm]\in \IN[/mm] und [mm]c_1,...c_k[/mm] [mm] \in \IZ[/mm] genau eine Lösung [mm](mod \; m) [/mm] mit [mm]m=m_1 *...*m_k[/mm].
Das Problem: ich sehe hier keine paarweise teilerfremden [mm]m_i[/mm] und erkenne daher den Zusammenhang nicht.
Kann mir das jemand näher erläutern?
|
|
| |
|
Hallo ella,
> 1.Teil:
> finde acht aufeinanderfolgende Zahlen, die keine
> Primzahlen sind! (analog zu einer zuvor beschiebenen
> Aufgabe.
>
> 2.Teil:
> Überlegen Sie sich, was eine solchen Aufgabenstellung mit
> dem Chinesischen Restsatz zu tun haben könnte.
> Den ersten Teil habe ich gelöst (das war leicht ;) )
>
> [mm]2*3*4*5*6*7*8*9+2=362882[/mm]
> [mm]2*3*4*5*6*7*8*9+3=362883[/mm]
> [mm]2*3*4*5*6*7*8*9+4=362884[/mm]
> [mm]2*3*4*5*6*7*8*9+5=362885[/mm]
> [mm]2*3*4*5*6*7*8*9+6=362886[/mm]
> [mm]2*3*4*5*6*7*8*9+7=362887[/mm]
> [mm]2*3*4*5*6*7*8*9+8=362888[/mm]
> [mm]2*3*4*5*6*7*8*9+9=362889[/mm]
>
> aber ich verstehe nicht, was eine solche Aufgabenstellung
> mit dem Chinesischen Restsatz zu tun haben könnte.
Das liegt vielleicht an deiner Lösung...
[mm] 2^3*3^2*5*7+m [/mm] mit 1<m<10 hätte es ja auch getan, also 2522,2523,...,2529. Natürlich ist auch 2530 nicht prim, aber 2521 und 2531 sind es sogar.
Jetzt könntest Du für den chin. Restsatz ja die Module 5,7,8,9 nehmen, die sind untereinander teilerfremd.
Verstehst Du, was die Aufgabe dann mit dem Satz zu tun hat?
Ansonsten geht es aber auch mit Deinem größeren Modul. Nur musst Du dann tatsächlich mal überlegen, wie das bei nicht-teilerfremden Moduln ist. Auch da kann man mit dem Restsatz zu einer Aussage gelangen.
a ist ja gerade dann keine Primzahl, wenn in [mm] a\equiv b\mod{c} [/mm] der ggT(b,c)>1 ist.
> Der Chinesische Restsatz besagt, dass folgendes System von
> linearen Kongruenzen
> [mm]x \equiv c_1 (mod \; m_1 )[/mm]
> [mm]x \equiv c_2 (mod \; m_2 )[/mm]
>
> [mm]\vdots[/mm]
> [mm]x \equiv c_k (mod \; m_k )[/mm]
>
> mit [mm]m_1,...,m_k[/mm] paarweise teilerfremd und [mm]\in \IN[/mm] und
> [mm]c_1,...c_k[/mm] [mm]\in \IZ[/mm] genau eine Lösung [mm](mod \; m)[/mm] mit [mm]m=m_1 *...*m_k[/mm].
>
> Das Problem: ich sehe hier keine paarweise teilerfremden
> [mm]m_i[/mm] und erkenne daher den Zusammenhang nicht.
> Kann mir das jemand näher erläutern?
Das erstmal als Denkanstoß. Kommst Du damit weiter?
Übrigens sind die Zahlen 114 bis 126 auch alle nicht prim, aber um das zu finden, braucht man entweder eine Primzahltabelle oder einen anderen Ansatz, z.B. sei [mm] a\equiv 0\mod{8},\ a\equiv 4\mod{9},\ a\equiv 2\mod{5},\ a\equiv 0\mod{7} [/mm] und [mm] a\equiv 2\mod{11} [/mm] dann ist [mm] a\equiv 112\mod{27720} [/mm] und a+2,a+3,a+4,a+5,a+6,a+7,a+8,a+9,a+10,a+11,a+12,a+13,a+14 sind alle nicht prim.
Grüße
reverend
|
|
|
| |
|
Ich habe einmal mit einem kleinen Programm die erste Gruppe von genau 8 aufeinanderfolgenden zerlegbaren natürlichen Zahlen gesucht. Da kam gar nichts heraus. Inzwischen ist mir auch klar, warum.
Nehmen wir an, wir hätten 8 aufeinanderfolgende zerlegbare Zahlen. Wenn die erste dieser Zahlen durch 2 teilbar ist, dann ist es auch die Zahl, die auf die 8 Zahlen unmittelbar folgt. Wenn dagegen die zweite der 8 Zahlen durch zwei teilbar ist, dann ist es auch die den 8 Zahlen vorangehende Zahl. Die Aufgabe ist daher nicht lösbar. Und die Argumentation geht mit jeder beliebigen geradzahligen Anzahl analog.
Immerhin, bei ungeradzahligen Anzahlen funktioniert mein Programm. Die erste Primlücke mit 99 Zahlen befindet sich bei den Zahlen von 396734 bis 396832.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:32 So 10.06.2012 | | Autor: | felixf |
Moin!
> Ich habe einmal mit einem kleinen Programm die erste Gruppe
> von genau 8 aufeinanderfolgenden zerlegbaren natürlichen
> Zahlen gesucht. Da kam gar nichts heraus. Inzwischen ist
> mir auch klar, warum.
> Nehmen wir an, wir hätten 8 aufeinanderfolgende
> zerlegbare Zahlen. Wenn die erste dieser Zahlen durch 2
> teilbar ist, dann ist es auch die Zahl, die auf die 8
> Zahlen unmittelbar folgt. Wenn dagegen die zweite der 8
> Zahlen durch zwei teilbar ist, dann ist es auch die den 8
> Zahlen vorangehende Zahl. Die Aufgabe ist daher nicht
> lösbar.
Doch, die Aufgabe ist loesbar. Es wurde naemlich nicht nach 8 Nicht-Primzahlen gefragt, so dass die Zahlen direkt davor und direkt danach prim sind, sondern einfach nur nach 8 Nicht-Primzahlen.
Man kann's auch so argumentieren: ist [mm] $p_n$ [/mm] die $n$-te Primzahl, so ist [mm] $p_n$ [/mm] ungerade fuer $n > 1$. Die Anzahl der Nicht-Primzahlen zwischen [mm] $p_n$ [/mm] und [mm] $p_{n+1}$ [/mm] ist [mm] $p_{n+1} [/mm] - [mm] p_n [/mm] - 1$. Da fuer $n > 1$ sowohl [mm] $p_{n+1}$ [/mm] wie auch [mm] $p_n$ [/mm] ungerade sind, ist deren Differenz gerade, womit [mm] $p_{n+1} [/mm] - [mm] p_n [/mm] - 1$ ungerade ist. Die Luecken zwischen zwei Primzahlen enthalten also immer eine ungerade Anzahl von Primzahlen, ausser wenn $n = 1$ ist, also [mm] $p_1 [/mm] = 2$, [mm] $p_3 [/mm] = 3$, da sind genau 0 Nicht-Primzahlen dazwischen.
LG Felix
|
|
|
| |
|
Schon klar. Ich wollte ja nur erklären, warum ich mit der abgeänderten Bedingung "genau 8" scheitern mußte. Zunächst hatte ich das nämlich leichtsinnigerweise für möglich gehalten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:28 So 10.06.2012 | | Autor: | felixf |
Moin reverend,
> > 1.Teil:
> > finde acht aufeinanderfolgende Zahlen, die keine
> > Primzahlen sind! (analog zu einer zuvor beschiebenen
> > Aufgabe.
> >
> > 2.Teil:
> > Überlegen Sie sich, was eine solchen Aufgabenstellung
> mit
> > dem Chinesischen Restsatz zu tun haben könnte.
> > Den ersten Teil habe ich gelöst (das war leicht ;) )
> >
> > [mm]2*3*4*5*6*7*8*9+2=362882[/mm]
> > [mm]2*3*4*5*6*7*8*9+3=362883[/mm]
> > [mm]2*3*4*5*6*7*8*9+4=362884[/mm]
> > [mm]2*3*4*5*6*7*8*9+5=362885[/mm]
> > [mm]2*3*4*5*6*7*8*9+6=362886[/mm]
> > [mm]2*3*4*5*6*7*8*9+7=362887[/mm]
> > [mm]2*3*4*5*6*7*8*9+8=362888[/mm]
> > [mm]2*3*4*5*6*7*8*9+9=362889[/mm]
> >
> > aber ich verstehe nicht, was eine solche Aufgabenstellung
> > mit dem Chinesischen Restsatz zu tun haben könnte.
>
> Das liegt vielleicht an deiner Lösung...
> [mm]2^3*3^2*5*7+m[/mm] mit 1<m<10 hätte es ja auch getan, also
> 2522,2523,...,2529. Natürlich ist auch 2530 nicht prim,
> aber 2521 und 2531 sind es sogar.
Man haette auch genauso $2 [mm] \cdot [/mm] 3 [mm] \cdot [/mm] 5 [mm] \cdot [/mm] 7 + m$ mit $1 < m < 10$ nehmen koennen :) Das waer dann noch kleiner.
> Jetzt könntest Du für den chin. Restsatz ja die Module
> 5,7,8,9 nehmen, die sind untereinander teilerfremd.
Oder 2, 3, 5, 7 
> Verstehst Du, was die Aufgabe dann mit dem Satz zu tun
> hat?
>
> Ansonsten geht es aber auch mit Deinem größeren Modul.
> Nur musst Du dann tatsächlich mal überlegen, wie das bei
> nicht-teilerfremden Moduln ist. Auch da kann man mit dem
> Restsatz zu einer Aussage gelangen.
>
> a ist ja gerade dann keine Primzahl, wenn in [mm]a\equiv b\mod{c}[/mm]
> der ggT(b,c)>1 ist.
Das stimmt so nicht ganz: fuer $a = b = c = 2$ gilt $a [mm] \equiv [/mm] b [mm] \pmod{c}$, [/mm] und $ggT(b, c) = 2 > 1$, jedoch ist $a$ trotzdem eine Primzahl.
Wenn jedoch $a > [mm] \min\{ b, c \}$ [/mm] gilt, dann stimmt die Aussage.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:00 So 10.06.2012 | | Autor: | reverend |
Moin Felix,
erstmal danke fürs Drüberlesen.
> > > 1.Teil:
> > > finde acht aufeinanderfolgende Zahlen, die keine
> > > Primzahlen sind! (analog zu einer zuvor beschiebenen
> > > Aufgabe.
> > >
> > > 2.Teil:
> > > Überlegen Sie sich, was eine solchen
> Aufgabenstellung
> > mit
> > > dem Chinesischen Restsatz zu tun haben könnte.
> > > Den ersten Teil habe ich gelöst (das war leicht ;)
> )
> > >
> > > [mm]2*3*4*5*6*7*8*9+2=362882[/mm]
> > > [mm]2*3*4*5*6*7*8*9+3=362883[/mm]
> > > [mm]2*3*4*5*6*7*8*9+4=362884[/mm]
> > > [mm]2*3*4*5*6*7*8*9+5=362885[/mm]
> > > [mm]2*3*4*5*6*7*8*9+6=362886[/mm]
> > > [mm]2*3*4*5*6*7*8*9+7=362887[/mm]
> > > [mm]2*3*4*5*6*7*8*9+8=362888[/mm]
> > > [mm]2*3*4*5*6*7*8*9+9=362889[/mm]
> > >
> > > aber ich verstehe nicht, was eine solche Aufgabenstellung
> > > mit dem Chinesischen Restsatz zu tun haben könnte.
> >
> > Das liegt vielleicht an deiner Lösung...
> > [mm]2^3*3^2*5*7+m[/mm] mit 1<m<10 hätte="" es="" ja="" auch="" getan,="" also="" <br="">> > 2522,2523,...,2529. Natürlich ist auch 2530 nicht prim,
> > aber 2521 und 2531 sind es sogar.
>
> Man haette auch genauso [mm]2 \cdot 3 \cdot 5 \cdot 7 + m[/mm] mit [mm]1 < m < 10[/mm]
> nehmen koennen :) Das waer dann noch kleiner.
Stimmt.
> > Jetzt könntest Du für den chin. Restsatz ja die Module
> > 5,7,8,9 nehmen, die sind untereinander teilerfremd.
>
> Oder 2, 3, 5, 7
>
> > Verstehst Du, was die Aufgabe dann mit dem Satz zu tun
> > hat?
> >
> > Ansonsten geht es aber auch mit Deinem größeren Modul.
> > Nur musst Du dann tatsächlich mal überlegen, wie das bei
> > nicht-teilerfremden Moduln ist. Auch da kann man mit dem
> > Restsatz zu einer Aussage gelangen.
> >
> > a ist ja gerade dann keine Primzahl, wenn in [mm]a\equiv b\mod{c}[/mm]
> > der ggT(b,c)>1 ist.
>
> Das stimmt so nicht ganz: fuer [mm]a = b = c = 2[/mm] gilt [mm]a \equiv b \pmod{c}[/mm],
> und [mm]ggT(b, c) = 2 > 1[/mm], jedoch ist [mm]a[/mm] trotzdem eine
> Primzahl.
Ich ging von minimalen Restklassenvertretern aus, also [mm] 0\le b\le{c-1}, [/mm] dann stimmts.
> Wenn jedoch [mm]a > \min\{ b, c \}[/mm] gilt, dann stimmt die
> Aussage.
...was die geschicktere Formulierung ist.
lg
rev
</m<10>
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:18 So 10.06.2012 | | Autor: | ella87 |
oh, so viele Mitteilungen, aber ich kann den Zusammenhang leider immer noch nicht erkennen.
Die großen Zahlen muss ich bei der Aufgabe zu wählen, weil die 8 aufeinander folgenden Nicht-Primzahlen "analog zu" einer anderen Aufgabe gefunden werden sollen. Also muss ich diese nehmen.
Ich verstehe aber nicht, wie ich die in ein System linearen Kongruenze packen soll und vor allem nicht, welche Aussage ich dann aus dem Chinesischen Restsatz folgern kann.
Ich hab die Zahlen man in ihre Primfaktoren zerlegt (bzw. zerlegen lassen):
[mm]362882^{}=2*13*17*821[/mm]
[mm]362883^{}=3*73*1657[/mm]
[mm]362884=2^2 *257*353[/mm]
[mm]362885^{}=2*3*31*1951[/mm]
[mm]362887^{}=7*47*1103[/mm]
[mm]362888=2^3 *45361[/mm]
[mm]362889=3^2 *61*611[/mm]
Immerhin hab ich jetzt die Erkenntnis, dass ich so (eventuell?) paarweise teilerfremde [mm]m_i \in \IN[/mm] finde, nämlich die Primzahlen, die nur in einer Primfaktorzerlegung vorkommen. Instinktiv würde ich jetzt die jeweils kleinste nehmen, also 13, 73, 257, 5, 31, 7, 45361, 61.
ABER: was sind denn die [mm]c_i[/mm] ?
UND: was ist mein [mm]x[/mm] aus dem System der linearen Kongruenzen des Satzes?
Mir ist nicht klar, auf welche Aussage ich hinaus möchte!
Kann mir da noch jemand weiter helfen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Mi 13.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
