erste Lösung finden < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:04 Mo 03.11.2014 | | Autor: | M.Rex |
| Aufgabe | <br>
alle ganzzahligen Lösungen für x und y von 24x+55y=1 finden <|br> |
Hallo Ihr.
Ich habe mal ein banales Problem, bin aber gerade zu doof, auf die erste Lösung zu kommen.
Gesucht sind alle [mm] x,y\in\IZ, [/mm] die die Gleichung 24x+55y=1 lösen. Es ist klar, dass ich sobald ich die erste Lösung [mm] x_{0}, y_{0} [/mm] habe, mit [mm] x=x_{0}+\frac{55}{ggT(24;55)} [/mm] und [mm] y=y_{0}+\frac{24}{ggT(24;55)} [/mm] alle weiteren Lösungen habe.
Aber ich finde keine "Startlösung", gibt es dafür einen netten Trick.
Marius
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:20 Mo 03.11.2014 | | Autor: | Marcel |
Hallo,
> <br>
> alle ganzzahligen Lösungen für x und y von 24x+55y=1
> finden <|br>
der Witz ist: Diese Gleichung ist gleichwertig zu
$24x [mm] \equiv [/mm] 1 [mm] \mod 55\,.$
[/mm]
(Oder auch zu
$55y [mm] \equiv [/mm] 1 [mm] \mod 24\,.$)
[/mm]
Kennst Du einen Satz, der sagt, wann eine solche Kongruenz lösbar ist?
Falls nicht, ich habe ihn
hier (klick!)
zitiert.
Die Lösbarkeit der Kongruenz ist kein Problem:
Wegen
[mm] $55=5*11\,$ [/mm] und [mm] $24=2^3*3$
[/mm]
ist [mm] $\ggT(55,24)=1\,.$
[/mm]
Und natürlich kannst Du auch mit dem euklidischen Algorithmus direkt etwa
"multiplikativ Inverse mod 24" berechnen.
Ich begründe es Dir mal gerade:
$55y [mm] \equiv [/mm] 1 [mm] \mod [/mm] 24$
bedeutet nichts anderes, als "das [mm] $y\,$ [/mm] multiplikativ invers mod 24 zu 55 mod 24
ist". (Vielleicht kann jemand, der sich in Zahlentheorie besser ausdrücken
kann, das mal schöner formulieren?)
Mit dem (erweiterten) euklidischen Algorithmus findest Du $a,b [mm] \in \IZ$ [/mm] mit
[mm] $a*55+b*24=\ggT(55,24)=1\,.$
[/mm]
Dann ist
$a*55=1-b*24$
und daher
$a*55 [mm] \equiv [/mm] 1 [mm] \mod 24\,,$
[/mm]
denn $b*24 [mm] \equiv [/mm] 0 [mm] \mod 24\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:30 Mo 03.11.2014 | | Autor: | Marcel |
Hallo Marius,
> <br>
> alle ganzzahligen Lösungen für x und y von 24x+55y=1
> finden <|br>
>
> Hallo Ihr.
>
> Ich habe mal ein banales Problem, bin aber gerade zu doof,
> auf die erste Lösung zu kommen.
>
> Gesucht sind alle [mm]x,y\in\IZ,[/mm] die die Gleichung 24x+55y=1
> lösen. Es ist klar, dass ich sobald ich die erste Lösung
> [mm]x_{0}, y_{0}[/mm] habe, mit [mm]x=x_{0}+\frac{55}{ggT(24;55)}[/mm] und
> [mm]y=y_{0}+\frac{24}{ggT(24;55)}[/mm] alle weiteren Lösungen
> habe.
>
> Aber ich finde keine "Startlösung", gibt es dafür einen
> netten Trick.
achso, es gibt zwei "straight forward"-Wege, ein solches Lösungspaar zu
finden:
1. [mm] $1=\ggT(24,55)$ [/mm] beobachten, der Rest folgt dann mit dem (erweiterten) euklidischen Algorithmus.
2. Ein bisschen rumspielen (Strategie: [mm] $k\,$ [/mm] hochlaufen lassen, und dann:
$k*55-m*24$ berechnen, wobei $m [mm] \in \IN$ [/mm] maximal ist, so dass
$m*24 < [mm] k*55\,,$ [/mm] aber $(m+1)*24 [mm] \ge [/mm] k*55$):
[mm] $55-2*24=7\,.$
[/mm]
[mm] $110-4*24=14\,.$
[/mm]
[mm] [s][nomm]$165-6*24=1\,.$[/nomm][/s]
[/mm]
edit: Korrektur des letzten Quatsches:
.
.
.
$ [mm] 7\cdot{}55-16\cdot{}24=1\,. [/mm] $
Diese 2. "Probier-Methode" kann man sicher auch programmieren... (man
muss sich halt im Klaren sein, dass man sich die Differenzen am Besten
permanent ausgeben läßt, um zu entscheiden, ob "Weiterrechnen" sinnvoll
ist; denn wenn man keine Prüfkriterien verwendet, kann es sonst sein,
dass man in eine Endlosschleife rechnen läßt... aber bei obiger Aufgabe ist
das kein Problem).
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:46 Di 04.11.2014 | | Autor: | Marcel |
Hallo nochmal,
> Hallo Marius,
>
> > <br>
> > alle ganzzahligen Lösungen für x und y von 24x+55y=1
> > finden <|br>
> >
> > Hallo Ihr.
> >
> > Ich habe mal ein banales Problem, bin aber gerade zu doof,
> > auf die erste Lösung zu kommen.
> >
> > Gesucht sind alle [mm]x,y\in\IZ,[/mm] die die Gleichung 24x+55y=1
> > lösen. Es ist klar, dass ich sobald ich die erste Lösung
> > [mm]x_{0}, y_{0}[/mm] habe, mit [mm]x=x_{0}+\frac{55}{ggT(24;55)}[/mm] und
> > [mm]y=y_{0}+\frac{24}{ggT(24;55)}[/mm] alle weiteren Lösungen
> > habe.
> >
> > Aber ich finde keine "Startlösung", gibt es dafür einen
> > netten Trick.
>
> achso, es gibt zwei "straight forward"-Wege, ein solches
> Lösungspaar zu
> finden:
> 1. [mm]1=\ggT(24,55)[/mm] beobachten, der Rest folgt dann mit dem
> (erweiterten) euklidischen Algorithmus.
>
> 2. Ein bisschen rumspielen (Strategie: [mm]k\,[/mm] hochlaufen
> lassen, und dann:
> [mm]k*55-m*24[/mm] berechnen, wobei [mm]m \in \IN[/mm] maximal ist, so
> dass
> [mm]m*24 < k*55\,,[/mm] aber [mm](m+1)*24 \ge k*55[/mm]):
>
> [mm]55-2*24=7\,.[/mm]
>
> [mm]110-4*24=14\,.[/mm]
>
> [mm]165-6*24=1\,.[/mm]
mir ist mal gerade aufgefallen, dass die 2. Methode fast nichts anderes
macht, als den Rest (in ungünster Weise aus [mm] $\{1,...,24\}$) [/mm] der Division
$k*55/24$
auszugeben. Naja, dann denkt man sich im Kopf irgendeinen Algorithmus
aus, beschreibt denn irgendwie, und dann sowas...
Also einfacher: Man schreibe sich etwa in Octave ein Programm der Art
| 1: | test=1;
| | 2: | k=0;
| | 3: | while(test==1)
| | 4: | k=k+1;
| | 5: | Rest=mod(k*55,24)
| | 6: | test=input('Weitermachen? Ihre Eingabe bitte (1=Ja, 0=Nein): ');
| | 7: | end;
| | 8: | if (Rest==1)
| | 9: | x=k
| | 10: | y=floor(x*55/24)
| | 11: | end
|
P.S.: Damit habe ich auch gerade mein obiges, unsinniges Ergebnis
kontrolliert - natürlich ist
[mm] $7*55-16*24=1\,.$
[/mm]
P.P.S. Du musst Dir immer den Rest angucken, und wenn Du siehst, dass
er =1 ist, solltest Du für test 0 eingeben!
Die Vorzeichen von x,y habe ich hier auch noch nicht beachtet - ich denke,
es wird ausreichen, oben y durch -y zu ersetzen.
Aber solche Feinheiten kannst Du Dir ja selbst zusammenbauen...
Gruß,
Marcel
|
|
|
|
