Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:13 Do 16.06.2011 | | Autor: | chesn |
Seien p,q [mm] \in \IN [/mm] verschiedene Primzahlen und a,b [mm] \in \IN_0 [/mm] natürliche Zahlen mit [mm] 0\le [/mm] a [mm] \le [/mm] p bzw. 0 [mm] \le [/mm] b [mm] \le [/mm] q. Begründe ob es eine natürliche Zahl n [mm] \in \IN_0 [/mm] gibt, die bei Division durch p den Rest a und bei Division durch q den Rest b hat.
Siehe meine Mitteilung unten.
Vielen Dank schonmal! :)
Gruß
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:34 Do 16.06.2011 | | Autor: | chesn |
Habe mir überlegt: Wähle ich n=pq, dann ist der Rest beim Teilen von n durch p gleich 0=:a und beim Teilen von n durch q gleich 0=:b.
Ist das mit n=pq und a=b=0 schon gelöst? Widerspricht ja keiner Voraussetzung.
Vielen Dank!!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:43 Do 16.06.2011 | | Autor: | Fulla |
Hallo chesn,
du sollst hier ein n finden, so dass die Voraussetzungen für alle möglichen a,b gelten. (Du hast nur ein n für den Spezialfall a=b=0 gefunden)
Es würde auch helfen, wenn man die Aufgabe noch lesen kann. Schreib sie doch bitte wieder in deine Frage.
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:05 Do 16.06.2011 | | Autor: | chesn |
Danke! Die Aufgabenstellung ist wohl beim Bearbeiten drauf gegangen.
Hat jemand einen Tipp in welche Richtung das Ganze geht, bzw. was ich mir dazu durchlesen könnte? Da ich ja schon den einen Spezialfall gefunden habe, läuft es wohl darauf hinaus, dass es ein solches n [mm] \in \IN_0 [/mm] gibt.
Danke schonmal!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:10 Do 16.06.2011 | | Autor: | felixf |
Moin!
> Seien p,q [mm]\in \IN[/mm] verschiedene Primzahlen und a,b [mm]\in \IN_0[/mm]
> natürliche Zahlen mit [mm]0\le[/mm] a [mm]\le[/mm] p bzw. 0 [mm]\le[/mm] b [mm]\le[/mm] q.
Es soll wohl $0 [mm] \le [/mm] a < p$ und $0 [mm] \le [/mm] b < q$ heissen.
> Begründe ob es eine natürliche Zahl n [mm]\in \IN_0[/mm] gibt, die
> bei Division durch p den Rest a und bei Division durch q
> den Rest b hat.
Mach es in zwei Schritten:
1) Ueberlege dir erstmal, dass es ausreicht den Spezialfall $(a, b) = (0, 1)$ anzuschauen: wenn du diesen loesen kannst, kannst du fuer alle $a, b$ so ein $n$ finden.
2) Ueberlege dir, wie du eine Loesung fuer $(a, b) = (0, 1)$ finden kannst. Das bedeutet ja, dass $n$ durch $p$ teilbar ist (also $n = p [mm] \cdot [/mm] k$ fuer $k [mm] \in \IZ$) [/mm] und dass $n [mm] \equiv [/mm] 1 [mm] \pmod{q}$ [/mm] ist (also $q [mm] \ell [/mm] = p k - 1$ fuer $k, [mm] \ell \in \IZ$).
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:04 Do 16.06.2011 | | Autor: | chesn |
Hallo! Danke für deine Antwort!
Es heisst in der original Aufgabenstellung [mm] \le [/mm] , vielleicht ist das auch ein Tippfehler.
Also für das gesuchte n muss gelten n=pk+a=ql+b . Mein Problem ist jetzt, die Gleichungen in -ein- n zu verpacken, oder muss ich das garnicht?
Vielen Dank! :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:10 Do 16.06.2011 | | Autor: | felixf |
Moin!
> Es heisst in der original Aufgabenstellung [mm]\le[/mm] , vielleicht
> ist das auch ein Tippfehler.
Ich denke das ist ein Tippfehler! Schliesslich sollen $a$ und $b$ als Reste auftreten, und Reste bei Division sind immer (betragsmaessig) kleiner als der Divisor.
> Also für das gesuchte n muss gelten n=pk+a=ql+b . Mein
> Problem ist jetzt, die Gleichungen in -ein- n zu verpacken,
> oder muss ich das garnicht?
Du kannst natuerlich schon versuchen, die Aufgabe gleich in einem Rutsch zu loesen. Da du dazu aber keine gute Idee hast: warum faengst du nicht mit kleineren Schritten an? Ich hab dir doch zwei Schritte gegeben.
Aber wenn du es direkt machen willst: lass das $n$ erstmal weg. Du willst $k, [mm] \ell \in \IZ$ [/mm] finden mit $p k + a = q [mm] \ell [/mm] + b$, also umbeschrieben $p k - q [mm] \ell [/mm] = z$ mit $z := b - a [mm] \in \IZ$. [/mm] Weisst du etwas darueber, wann eine solche Gleichung $p k - q [mm] \ell [/mm] = z$ mit gesuchten $k, [mm] \ell \in \IZ$ [/mm] loesbar ist?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:37 Do 16.06.2011 | | Autor: | chesn |
Hallo!
Sitze jetzt schon eine ganze Weile an der Aufgabe und komme einfach nicht drauf.. :\ Deine Gleichung erinnert mich zum einen an das Lemma von Bezout.
Damit könnte ich sowas basteln wie ggT(p,q)=pk-ql=1, was allerdings eher aus der Verzweiflung heraus entstanden ist..
Kannst du noch etwas über die Lösbarkeit der Gleichung sagen/verlinken?
Wäre nett, bin gerade leider ratlos. :[
Vielen Dank!!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:16 Fr 17.06.2011 | | Autor: | chesn |
Hallo!
Kann jemand evtl noch was dazu sagen? Wäre super! ;)
Dankeschön!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:14 Fr 17.06.2011 | | Autor: | chesn |
Hallo nochmal! Was ich jetzt gefunden habe:
Lineare Diophantische Gleichungen sind lösbar, wenn der ggT der Koeffizienten (hier p und q) ein Teiler der rechten Seite ist (hier z).
Da ggT(p,q)=1 gilt, ist die Gleichung für alle z [mm] \in \IZ [/mm] lösbar, mit z=(b-a) also für alle a,b.
Ein solches n [mm] \in \IN_0 [/mm] gibt es also. Bin ich damit fertig?
Dankeschön! :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:00 Fr 17.06.2011 | | Autor: | felixf |
Moin!
> Hallo nochmal! Was ich jetzt gefunden habe:
>
> Lineare Diophantische Gleichungen sind lösbar, wenn der
> ggT der Koeffizienten (hier p und q) ein Teiler der rechten
> Seite ist (hier z).
> Da ggT(p,q)=1 gilt, ist die Gleichung für alle z [mm]\in \IZ[/mm]
> lösbar, mit z=(b-a) also für alle a,b.
>
> Ein solches n [mm]\in \IN_0[/mm] gibt es also. Bin ich damit fertig?
Ja, wenn du das verwenden darfst, schon.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:01 Fr 17.06.2011 | | Autor: | felixf |
Moin!
> Sitze jetzt schon eine ganze Weile an der Aufgabe und komme
> einfach nicht drauf.. :\ Deine Gleichung erinnert mich zum
> einen an das Lemma von Bezout.
Bingo, Volltreffer!
> Damit könnte ich sowas basteln wie ggT(p,q)=pk-ql=1, was
> allerdings eher aus der Verzweiflung heraus entstanden
> ist..
Nun, wenn du $1 = p [mm] \cdot [/mm] k - q [mm] \cdot \ell$ [/mm] mit $z$ multiplizierst und passend klammerst, steht doch das Gesuchte da.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:18 Sa 18.06.2011 | | Autor: | chesn |
Hallo! Deine Hinweise haben mir sehr geholfen, erstmal Danke dafür!
Ich habe die ganze Zeit versucht, ein konkretes n zu finden, aber wenn ich das jetzt richtig verstanden habe, ist nur die Lösbarkeit der o.g. Gleichung zu zeigen. (?)
Zusammengefasst:
Mit n=pk+a und n=ql+b ist pk+a=ql+b [mm] \gdw [/mm] pk-ql=z mit z:=(b-a)
Da p und q teilerfremd sind, folgt mit dem Lemma von Bezout:
Es existieren $ k,l [mm] \in \IZ [/mm] $ mit $ pk-ql=1 $
Jetzt multipliziere ich mit z => z(pk-ql)=z [mm] \gdw [/mm] z=z
Reicht das so? Bin gerade der Meinung, ich müsste noch zeigen, dass es für alle a,b gilt(?) Meine Überlegung dazu: Wenn es ja $ k,l [mm] \in \IZ [/mm] $ mit $ pk-ql=1 $ gibt, dann gibt es auch Koeffizienten, nennen wir sie r und s,
mit $p*r - q*s = x $ für alle x [mm] \in \IZ [/mm] , mit x=b-a also auch für alle a,b [mm] \in \IZ.
[/mm]
Danke schonmal fürs drüber Schauen! :)
Gruß
chesn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:26 Sa 18.06.2011 | | Autor: | chesn |
Hallo!
Könnte nochmal jemand drüber schauen? Wäre sehr nett! :)
Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:06 So 19.06.2011 | | Autor: | rammy |
Hallo!
Dein Beweis sieht auf dem ersten Blick sehr richtig aus!
Der allgemeine Fall könnte noch etwas ausgebaut werden, mit mehr Erklärungen, aber so würde es für mich reichen (denke auch für den / die Prof.).
LG
R
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:54 Mo 20.06.2011 | | Autor: | SimSSS |
Hallo chesn,
eine Aussage irritiert mich etwas:
Jetzt multipliziere ich mit z => z(pk-ql)=z $ [mm] \gdw [/mm] $ z=z
naja egal, welche Gleichung man mit z multipliziert, man kann immer sagen, dass z=z ist, wann sollte das denn nicht stimmen. Und aus welchem Grund sollte das deine Aufgabenstellung beweisen?
Gruß SimSSS
|
|
|
|
