Ganzzahlige Lösungen < Sonstiges < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:03 Fr 08.06.2012 | | Autor: | ivan19 |
| Aufgabe | | Wieviele ganzzahlige Lösungen hat die Gleichung [mm] x^{2}-y^{2}=n [/mm] ? |
Hallo!
Mir fehlt irgendwie der Ansatz bei dieser Aufgabe... Wenn ich den Fall n=0 betrachte, hab ich ja da schon unendlich viele Lösungen, oder? (Es steht zwar nicht dabei, aber ich geh mal davon aus, dass das n eine natürliche Zahl sein soll.)
Hab die Gleichung mal zerlegt in (x-y)(x+y)=n, aber jetzt weiß ich schon nicht mehr weiter...
Hoffe mir kann jemand helfen.
Danke!
Lg
|
|
| |
|
> Wieviele ganzzahlige Lösungen hat die Gleichung
> [mm]x^{2}-y^{2}=n[/mm] ?
> Hallo!
>
> Mir fehlt irgendwie der Ansatz bei dieser Aufgabe... Wenn
> ich den Fall n=0 betrachte, hab ich ja da schon unendlich
> viele Lösungen, oder? (Es steht zwar nicht dabei, aber ich
> geh mal davon aus, dass das n eine natürliche Zahl sein
> soll.)
> Hab die Gleichung mal zerlegt in (x-y)(x+y)=n, aber jetzt
> weiß ich schon nicht mehr weiter...
Hallo ivan19,
man muss sich das Ganze natürlich jeweils für ein
vorgegebenes n betrachten. Damit es überhaupt
ganzzahlige Lösungen geben kann, muss natürlich
auch n ganzzahlig sein. Der Fall n=0 ist praktisch
trivial (hast du schon erwähnt), und der Fall mit -n
ist analog zum Fall mit n. Also kann man sich im
Wesentlichen auf [mm] n\in\IN [/mm] beschränken. Ferner kann
man dann noch etwa [mm] x>y\ge0 [/mm] verlangen, weil ein
Vorzeichenwechsel bei x und/oder y bei jedem Lösungs-
paar nichts am Wert von [mm] x^2-y^2 [/mm] ändert.
Die Zerlegung $\ n=(x-y)*(x+y)$ ist wohl durchaus nützlich.
Nach den Annahmen [mm] x>y\ge0 [/mm] ergibt sich damit eine
Zerlegung von n in zwei natürliche Faktoren, über die
man weiterhin noch sagen kann, dass diese entweder
beide gerade oder beide ungerade sein müssen (warum?).
Es empfiehlt sich also bestimmt, für eine vorgegebene
Zahl [mm] n\in\IN [/mm] zuerst die möglichen Faktorzerlegungen zu
betrachten.
Manche n können überhaupt nicht in zwei Faktoren
derselben Parität (beide gerade oder beide ungerade)
zerlegt werden und scheiden damit aus.
Ich würde nun mal empfehlen, das Ganze für einige
kleine Werte von n (etwa bis n=2) konkret durchzuspielen !
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:28 Fr 08.06.2012 | | Autor: | ivan19 |
Warum müssen die entweder beide gerade oder beide ungerade sein?
Ich hab das jetzt mal ausprobiert und hab festgestellt, dass ich
für n=0 unendlich viele Lösungen hab,
für n=1 hab ich die Lösungen (1,0) und (-1,0) und
für n=2 hab ich keine Lösungen gefunden.
Dafür hab ich für n=3 die Lösungen (2,1),(-2,1),(2,-1) und (-2,-1), da ja
[mm] x^{2}-y^{2}=3=4-1 \Rightarrow x=\pm2 [/mm] und [mm] y=\pm1.
[/mm]
Aber ich hab das nur so durchprobiert und nichts gerechnet, deshalb weiß ich auch nicht ob das stimmt und was ich jetzt damit anfangen soll...
|
|
|
| |
|
> Warum müssen die entweder beide gerade oder beide ungerade
> sein?
Überleg dir nur: Wenn x und y ganze Zahlen sind, so sind (x+y)
und (x-y) entweder beide gerade oder beide ungerade.
> Ich hab das jetzt mal ausprobiert und hab festgestellt,
> dass ich
> für n=0 unendlich viele Lösungen hab,
> für n=1 hab ich die Lösungen (1,0) und (-1,0) und
> für n=2 hab ich keine Lösungen gefunden.
> Dafür hab ich für n=3 die Lösungen (2,1),(-2,1),(2,-1)
> und (-2,-1), da ja
> [mm]x^{2}-y^{2}=3=4-1 \Rightarrow x=\pm2[/mm] und [mm]y=\pm1.[/mm]
Zur Vereinfachung würde ich eben (wie schon gesagt)
negative Werte ausschließen. Sie am Schluss eventuell
wieder dazu zu nehmen, ist problemlos.
> Aber ich hab das nur so durchprobiert und nichts gerechnet,
> deshalb weiß ich auch nicht ob das stimmt und was ich
> jetzt damit anfangen soll...
Das Wesentliche sieht man wohl erst an Beispielen mit
etwas größeren n hervortreten. Nehmen wir deshalb etwa
einmal die Zahl [mm] 600=2^3*3^1*5^2 [/mm] (Primfaktorzerlegung) .
600 lässt sich natürlich nur in zwei gerade (aber nicht in zwei
ungerade) Faktoren zerlegen. Wegen [mm] x>y\ge0 [/mm] (würde ich eben
für die Untersuchung so voraussetzen) ist natürlich (x+y) der
größere und (x-y) der kleinere der beiden Faktoren. Im Falle,
wo n eine Quadratzahl ist, gäbe es auch eine Zerlegung
(x+0)*(x-0) in zwei gleich große Faktoren.
In Frage kommende Zerlegungen von 600 sind demnach:
$\ 2*300\ =\ [mm] (2^1*3^0*5^0)*(2^2*3^1*5^2)$ [/mm]
$\ 4*150\ =\ [mm] (2^2*3^0*5^0)*(2^1*3^1*5^2)$ [/mm]
$\ 6*100\ =\ [mm] (2^1*3^1*5^0)*(2^2*3^0*5^2)$
[/mm]
$\ 10*60\ =\ [mm] (2^1*3^0*5^1)*(2^2*3^1*5^1)$
[/mm]
$\ 12*50\ =\ [mm] (2^2*3^1*5^0)*(2^1*3^0*5^2)$ [/mm]
$\ 20*30\ =\ [mm] (2^2*3^0*5^1)*(2^2*3^1*5^1)$
[/mm]
Es wird natürlich klar, dass es nur auf die in den Primfak-
torzerlegungen von n und dessen beiden Faktoren
auftretenden Exponenten ankommt.
Es ist möglich, die Berechnung der Lösungsanzahl
(nennen wir sie einmal L(n), hier im Beispiel L(600)=6)
auf eine recht einfache kombinatorische Aufgabe zurück-
zuführen, welche man auch durch ein einfaches Spiel
mit farbigen Kugeln, welche auf je 2 Schachteln
verteilt werden sollen, simulieren kann.
LG Al-Chw.
|
|
|
| |
|
moin,
Al hat ja schon so einiges zur Frage gesagt, wie man solche Lösungen finden könnte.
Allerdings sollte man sich (als theorieliebender Mathematiker^^) vor der Suche nach Lösungen erstmal um die Frage kümmern, ob die Gleichung überhaupt lösbar ist.
Sei dafür erstmal $n = 2k+1$ mit $k [mm] \in \IN_0$ [/mm] ungerade.
Dann liefert die Wahl $x = k+1$ und $y=k$ eine Lösung.
Damit ist die Gleichung schonmal für alle ungeraden $n$ lösbar.
Sei nun $n$ gerade.
Da aus [mm] $x^2-y^2 [/mm] = n$ sofort [mm] $(2x)^2-(2y)^2 [/mm] = 4n$ folgt, folgt also aus der Lösbarkeit für $n$ die Lösbarkeit für $4n$.
Somit können wir mit ein wenig Argumentation schonmal alle $n$ in der Form $n= [mm] 2^e*k$ [/mm] für ein ungerade $k$ und ein gerade $e$ abhaken.
Es bleiben also einzig die $n= [mm] 2^e*k$ [/mm] für ein ungerades $k$ und ein ungerades $e$ übrig, die noch Probleme bereiten.
Dass diese tatsächlich echte Probleme bedeuten zeigt etwa das Beispiel [mm] $n=2=2^1*1$, [/mm] denn wie du richtig festgestellt hast gibt es dafür keine Lösung.
Mal so eben eine Formel für die Menge aller Lösungen, am besten in Abhängigkeit von $n$, hinzuschreiben dürfte nicht ganz leicht sein.
Deshalb würde ich dir raten das ganze möglichst einzuschränken und dann mit einem PC durchzurechnen.
Es könnte auch sein, dass dieses Problem bereits vollständig gelöst ist.
Dazu könntest du ggf. mal ein wenig recherchieren, aber so spontan eine Lösung aus dem Hut zu zaubern dürfte nix werden.
lg
Schadow
PS:
Ich hab mal in meinem alten Zahlentheorieskript gekramt, aber außer dass die Darstellung von ungeraden Primzahlen als Differenz zweier Quadrate eindeutig ist habe ich nichts brauchbares finden können.
|
|
|
| |
|
Guten Abend Shadowmaster !
> moin,
>
> Al hat ja schon so einiges zur Frage gesagt, wie man solche
> Lösungen finden könnte.
> Allerdings sollte man sich (als theorieliebender
> Mathematiker^^)
Ja Moment mal, shadow: dafür halte ich mich natürlich ebenfalls ... 
Und ich habe auch schon angedeutet, dass die Gleichung nicht
für alle n lösbar ist:
Manche n können überhaupt nicht in zwei Faktoren
derselben Parität (beide gerade oder beide ungerade)
zerlegt werden und scheiden damit aus.
Die Einzelheiten genau auszuarbeiten, möchte ich gerne dem
Fragenden und allen übrigen Interessierten überlassen.
> vor der Suche nach Lösungen erstmal um die
> Frage kümmern, ob die Gleichung überhaupt lösbar ist.
> Sei dafür erstmal [mm]n = 2k+1[/mm] mit [mm]k \in \IN_0[/mm] ungerade.
> Dann liefert die Wahl [mm]x = k+1[/mm] und [mm]y=k[/mm] eine Lösung.
> Damit ist die Gleichung schonmal für alle ungeraden [mm]n[/mm]
> lösbar.
> Sei nun [mm]n[/mm] gerade.
> Da aus [mm]x^2-y^2 = n[/mm] sofort [mm](2x)^2-(2y)^2 = 4n[/mm] folgt, folgt
> also aus der Lösbarkeit für [mm]n[/mm] die Lösbarkeit für [mm]4n[/mm].
> Somit können wir mit ein wenig Argumentation schonmal
> alle [mm]n[/mm] in der Form [mm]n= 2^e*k[/mm] für ein ungerade [mm]k[/mm] und ein
> gerade [mm]e[/mm] abhaken.
>
> Es bleiben also einzig die [mm]n= 2^e*k[/mm] für ein ungerades [mm]k[/mm]
> und ein ungerades [mm]e[/mm] übrig, die noch Probleme bereiten.
> Dass diese tatsächlich echte Probleme bedeuten zeigt etwa
> das Beispiel [mm]n=2=2^1*1[/mm], denn wie du richtig festgestellt
> hast gibt es dafür keine Lösung.
>
> Mal so eben eine Formel für die Menge aller Lösungen, am
> besten in Abhängigkeit von [mm]n[/mm], hinzuschreiben dürfte nicht
> ganz leicht sein.
So wie ich es jetzt sehe, ist es aber mittels gewisser
Fallunterscheidungen durchaus möglich, ein recht
einfaches Rezept zur Berechnung anzugeben. Muss ja
nicht unbedingt eine einzige geschlossene Formel sein.
> Deshalb würde ich dir raten das ganze möglichst
> einzuschränken und dann mit einem PC durchzurechnen.
Ich denke, dass einige mit Stift und Papier durchge-
rechnete Beispiele deutlich mehr Einsicht bringen als
das Verwursten im PC.
> Es könnte auch sein, dass dieses Problem bereits
> vollständig gelöst ist.
Das halte ich sogar für sehr, sehr wahrscheinlich. Aber viel
spannender, als nach der wohl schon irgendwo vorhandenen
fertigen Lösung zu suchen, ist es, den Weg zu einer
eigenen Lösung zu pfaden !
> Dazu könntest du ggf. mal ein wenig recherchieren, aber
> so spontan eine Lösung aus dem Hut zu zaubern dürfte nix
> werden.
Man muss nicht "zaubern" wollen, sondern nur Schritt für
Schritt die wesentlichen Ecksteine finden bzw. setzen
und kann dann mit etwas beharrlicher Arbeit durchaus
zum Ziel kommen.
Zuerst habe ich auch gedacht, dass die Aufgabe wohl
wirklich schwierig sein könnte. Jetzt, nach schätzungsweise
2 Stunden des Probierens und Nachdenkens, sehe ich
dies ziemlich anders. Die Aufgabe liegt durchaus im Bereich
dessen, was wir hier für viele verständlich abhandeln
können.
LG Al-Chwarizmi
|
|
|
| |
|
Hallo,
ich denke, dass ich inzwischen sogar eine "geschlossene" Lösung
in einer Formel habe ...
LG Al
|
|
|
| |
|
| Aufgabe | | Wieviele ganzzahlige Lösungen hat die Gleichung [mm]x^{2}-y^{2}=n[/mm] ? |
Hallo an alle Zahlentheoriefans !
da ich gerade Zeit dazu habe, möchte ich nun den
Deckel aufmachen und den Weg zu meiner oben schon
angedeuteten Lösung erläutern. Am Schluss kommt
tatsächlich eine geschlossene Formel für die Anzahl
L(n) der Lösungen heraus, welche sich auf die Prim-
faktorzerlegung der Zahl n stützt.
Dabei betrachte ich nur [mm] n\in\IN [/mm] und Lösungspaare
(x|y) mit [mm] x\in\IN [/mm] , [mm] y\in\IN_0 [/mm] und x>y . L(n) sei die Anzahl
aller solchen Paare (x|y) mit [mm] x^2-y^2=n [/mm] .
Der Fall mit n=0 ist trivial (mit unendlich vielen
Lösungspaaren), und die Anzahl der Lösungspaare,
wenn auch negative Werte von x und y zugelassen
sein sollten, lässt sich aus "unserem" L(n) leicht
ermitteln.
Wie schon in den obigen Artikeln erläutert, kommt es
wesentlich darauf an, auf welche - und vor allem auf
wie viele - Arten die vorgegebene natürliche Zahl n
in zwei gerade oder aber in zwei ungerade Faktoren
zerlegt werden kann. Man kann leicht zeigen (Übungs-
aufgabe für den Leser !), dass zu jeder solchen Faktor-
zerlegung (wobei die Reihenfolge der beiden Faktoren
unerheblich ist) genau ein Lösungspaar (x|y) mit [mm] x>y\ge0
[/mm]
existiert - und auch umgekehrt. Die Frage nach der
Anzahl L(n) reduziert sich also für ein gegebenes n auf
die Frage: Auf wieviele Arten lässt sich n in ein Produkt
$\ u*v$ aus natürlichen Faktoren u,v mit [mm] u\le{v} [/mm] zerlegen,
wobei u und v gleiche Parität haben müssen (also ent-
weder beide gerade oder beide ungerade) ?
Es ist nun klar, dass wir für die weitere Untersuchung
die Primfaktorzerlegung von n betrachten müssen.
Es sei
$\ n\ =\ [mm] \prod_{i=1}^{k}p_i^{\alpha_i}$
[/mm]
Dabei sei [mm] p_1=2 [/mm] und die übrigen [mm] p_i [/mm] die weiteren (von-
einander und von 2 verschiedenen) Primteiler von n.
Ist n ungerade, setze man einfach [mm] \alpha_1:=0 [/mm] .
Jeder Zerlegung von n in ein Produkt von zwei natürlichen
Faktoren u und v entspricht nun natürlich eine Aufteilung
aller insgesamt [mm] $\summe_{i=1}^{k}\alpha_i$ [/mm] Primfaktoren in zwei Gruppen,
nämlich die Faktoren von u und die von v, jeweils in
ihren Vielfachheiten. Um uns das etwas anschaulicher zu
machen, können wir uns dafür ein Bild machen:
Die PFZ (Primfaktorzerlegung) von n werde dargestellt
durch eine Menge K von insgesamt [mm] $\summe_{i=1}^{k}\alpha_i$ [/mm] Kugeln,
davon [mm] \alpha_2 [/mm] schwarze und je [mm] \alpha_i [/mm] Stück einer Farbe [mm] F_i
[/mm]
(für i=2,3, ... ,k). Alle diese Farben sollen voneinander
verschieden sein. Ein Beispiel: Um etwa die Zahl
126000 = [mm] 2^4*3^2*5^3*7^1 [/mm] darzustellen, könnten wir 4 schwarze,
2 rote, 3 blaue und 1 gelbe Kugel(n) nehmen.
Um eine Faktorisierung n=u*v darzustellen, teilen wir
jetzt einfach die Menge K aller Kugeln in zwei Teilmengen
[mm] K_u [/mm] und [mm] K_v [/mm] auf, eine für die Faktoren von u und die andere
für die Faktoren von v. Wir können für die beiden Teilmengen
also je eine Schachtel bereitstellen. Im Folgenden müssen
wir uns eigentlich nur um den Inhalt der einen Schachtel
kümmern - denn in der anderen liegt ja jeweils einfach
der Rest der Kugeln: [mm] K_v=K\smallsetminus{K_u} [/mm]
Für die zulässigen Faktorisierungen haben wir nun die
Bedingungen, dass entweder beide Faktoren ungerade oder
aber beide gerade sein müssen.
Der erste Fall kommt natürlich nur dann in Frage, wenn n
selber ungerade ist, d.h. [mm] \alpha_1=0 [/mm] (Anzahl der Faktoren 2
in der PFZ von n). In diesem Fall haben wir also gar keine
schwarzen Kugeln.
Die übrigen Kugeln können wir eigentlich ganz frei auf die
Schachteln verteilen, oder anders gesagt: in die erste
Schachtel dürfen wir irgendeine Teilmenge von K legen
(angefangen von der leeren Menge bis zu ganz K).
Um aus dem Schachtelinhalt dann die zugehörige Zahl
u zu berechnen, müssen wir nur die entsprechenden
Primfaktoren multiplizieren. Wegen der Eindeutigkeit der
PFZ müssen wir nur beachten, wie oft jede Farbe (bzw.
jede Primzahl) in der ersten Schachtel vorkommt.
Kommt etwa der Faktor 3 in n viermal vor, so kann er
in u entweder 0,1,2,3 oder 4 mal vorkommen. Das sind
[mm] (\alpha_2+1)=4+1=5 [/mm] Möglichkeiten. Für jeden
weiteren Primfaktor [mm] p_i [/mm] haben wir [mm] (\alpha_i+1) [/mm] Möglich-
keiten für die Wahl des Exponenten [mm] \beta_i [/mm] in der PFZ
$\ u\ =\ [mm] \prod_{i=1}^{k}p_i^{\beta_i}$
[/mm]
der Zahl u. Für jeden Primfaktor kann man unabhängig
auswählen, wie groß das jeweilige [mm] \beta_i\in\{0,1,2,\,...\,\alpha_i\}
[/mm]
sein soll. Insgesamt kommen wir so auf eine Anzahl von
[mm] $\prod_{i=2}^{k}(\alpha_i+1)$
[/mm]
Möglichkeiten für den Faktor u.
Nur müssen wir jetzt noch berücksichtigen, dass wir auf
diese Weise jedes Produkt zweimal produzieren, nämlich
etwa 21=3*7=7*3 . Deshalb müssen wir die Anzahl der
Möglichkeiten halbieren, denn von den beiden Paaren
(u|v)=(3|7) und (u|v)=(7|3) erfüllt nur das eine die
Bedingung [mm] u\le{v} [/mm] , die wir wegen unserer Voraussetzung
[mm] x>y\ge0 [/mm] und den Definitionen u:=x-y , v:=x+y fordern
müssen. Ist allerdings n eine Quadratzahl, so gibt es
(genau) ein Paar (u|v) mit u=v , welches in unserer
Aufzählung doch nicht doppelt auftrat.
Beispiel: für die Zahl [mm] 225=15^2 [/mm] kämen wir zuerst auf
3*3=9 Möglichkeiten für u, wovon am Ende noch 5
übrig bleiben. Für die Berechnung der Anzahl L(n)
können wir nach dem Halbieren die Ceiling-Funktion
(Aufrunden) verwenden:
$\ L(n)\ =\ [mm] \left\lceil \frac{1}{2}*\prod_{i=2}^{k}(\alpha_i+1)\right\rceil$
[/mm]
Nun noch der andere mögliche Fall (wobei u und v
beide gerade sein sollen). Dieser kann nur eintreten,
wenn n durch 4 teilbar ist. Wäre also n zwar durch 2, aber
nicht durch 4 teilbar, d.h. [mm] \alpha_1=1 [/mm] (genau ein Faktor 2
in der PFZ von n), so gäbe es gar keine Lösung, also
L(n)=0.
Setzen wir also für das Folgende [mm] \alpha_1\ge2 [/mm] voraus.
Da u und v je mindestens einen Faktor 2 enthalten
müssen, können wir quasi in jede der beiden Schachteln
die entsprechende "obligatorische" schwarze Kugel legen.
Daran gibt's nicht zu variieren - nur die von der PFZ von
n ferner ev. noch vorhandenen schwarzen Kugeln können
wir frei verteilen.
So wie wir oben (für die ungeraden Primfaktoren) jeweils
[mm] (\alpha_i+1) [/mm] Möglichkeiten der Wahl (für die 1. Schachtel)
hatten, ergeben sich jetzt für den Primfaktor [mm] p_1=2 [/mm] nicht
[mm] (\alpha_1+1) [/mm] , sondern nur [mm] ((\alpha_1-2)+1)=(\alpha_1-1) [/mm] Möglichkeiten.
Für eine durch 4 teilbare (positive) Zahl n erhalten wir
demnach zunächst
$ [mm] (\alpha_1-1)*\prod_{i=2}^{k}(\alpha_i+1) [/mm] $
Möglichkeiten zur Auswahl eines (ersten) Faktors u in
der Zerlegung n=u*v . Auch diese Anzahl müssen wir
halbieren und dabei noch den Sonderfall einer Quadratzahl
n betrachten. Damit ergibt sich für [mm] \alpha_1\ge2 [/mm] die Formel:
$\ L(n)\ =\ [mm] \left\lceil \frac{1}{2}*(\alpha_1-1)*\prod_{i=2}^{k}(\alpha_i+1)\right\rceil$
[/mm]
Nun haben wir die gesamte Auslegeordnung und eine
Fallunterscheidung je nach den Fällen
1.) [mm] \alpha_1=0 [/mm] : ungerade Zahl n ----> $\ L(n)\ =\ [mm] \left\lceil \frac{1}{2}\cdot{}\prod_{i=2}^{k}(\alpha_i+1)\right\rceil [/mm] $
2.) [mm] \alpha_1=1 [/mm] : n mod 4 = 2 ----> $\ L(n)\ =\ 0$
3.) [mm] \alpha_1\ge2 [/mm] : n durch 4 teilbar ----> $\ L(n)\ =\ [mm] \left\lceil \frac{1}{2}\cdot{}(\alpha_1-1)\cdot{}\prod_{i=2}^{k}(\alpha_i+1)\right\rceil [/mm] $
Ganz zum Schluss gibt es nun noch ein süßes Zückerchen:
die drei Formeln lassen sich in eine einzige verpacken,
nämlich:
$\ [mm] \mbox{\LARGE{L(n)\ =\ \left\lceil \frac{1}{2}\cdot{}|\alpha_1-1|\cdot{}\prod_{i=2}^{k}(\alpha_i+1)\right\rceil}} [/mm] $
... und jetzt wird eine Flasche geöffnet ... 
Al-Chwarizmi
|
|
|
|
