Modulo < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:01 Mo 11.02.2008 | | Autor: | Boki87 |
| Aufgabe | Also ich hab folgende Aufgabe aus der Informatik, diese geht aber auch relativ weit in die Mathematik rüber...hab sie bereits im Info-Forum gestellt gehabt und dort wurde mir geraten die Frage hier nochmals zu stellen...hoff mal jetzt bin ich richtig^^
Ich hab folgende Aufgabe:
Ich soll Zahlentripel(a,b,c) finden die folgende Bedingung erfüllen:
a*b mod c = 1, a*c mod b = 1, c*b mod a = 1 mit a<=b<=c.
Ich habe die Aufgabe programiert und hab als Lösung 2-3-5 raus. Nun kommt die nächste Teilaufgabe, ich soll beweisen das dies das Einzige Paar ist, das die Bedingung erfüllt.
Ich hab leider keinen Ansatz wie ich da Anfangen könnte.
Danke schonmal |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Ich würd erst mal versuchen die Modulo gleichungen überzufüher in normale Gleichungen:
1) a*b=k*c+1
2) a*c=n*b+1
3) b*c=m*a+1
Jetzt würde ich alle gleichungen mit dem Fehlenden element multiplizieren.
1) [mm] a*b*c=k*c^2+c
[/mm]
2) [mm] a*b*c=n*b^2+b
[/mm]
3) [mm] a*b*c=m*a^2+a
[/mm]
Jetzt kannst du die gleichungen Paarweise gleichsetzen und schauen was für Teilbarkeitseigenschaften du da zusätzlich kriegst. Z.B.
1)=2):
[mm] k*c^2+c=n*b^2+b [/mm]
Die linke seite ist durch c teilbar also muss es die rechte auch sein! Natürlich ist auch anderstrum die rechte seite durch b teilbar also muss es die linke auch sein.
...
Versuch mal so weiterzumachen vielleicht kommst du auf irgendwas nützliches.
Oder du kannst auch überprüfen mit einer tabelle
| gerade | ungerade
a | |
b | |
c | |
Ob du z.b. die Fälle (gerade gerade gerade), (gerade,gerade, ungerade),...
ausschließen kannst wegen den kongruenzgleichungen
Z.B. sieht man dass gerade, gerade, gerade nicht möglich ist wegen a*b (mod c) =1
Und so weiter... du musst halt ein bisschen rumspielen.
Ich hoffe ich konnte dir irgendwie helfen:).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:25 Mo 11.02.2008 | | Autor: | Boki87 |
Danke schön schonmal
Wie tu ich denn genau eine Mod-Gleichung in normale Gleichungen umwandeln...ist nämlich das erste mal das ich eine mathemtische Aufgabenstellung mit mod habe und kenn mich daher nicht so gut mit aus.
des mit dem gerade ungerade denke ich mal hilft mir nicht weiter...im endeffekt würde ich wenn ich einen ansatz finde nur zum Schluss kommen das die Variante gerade-ungerade-ungerade funktioniert, aber die schließt nicht aus das es weitere Tripel außer 2-3-5 gibt...oder hab ich da einen Denkfehler?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:13 Di 12.02.2008 | | Autor: | Marcel |
Hallo,
> Wie tu ich denn genau eine Mod-Gleichung in normale
> Gleichungen umwandeln...ist nämlich das erste mal das ich
> eine mathemtische Aufgabenstellung mit mod habe und kenn
> mich daher nicht so gut mit aus.
es wurde im Prinzip schonmal gemacht. Du musst einfach nur beachten:
Sind $m [mm] \in \IN$ [/mm] und $n [mm] \in \IN_0$ [/mm] sowie $r [mm] \in \IN_0$ [/mm] mit $0 [mm] \le [/mm] r < n$, so gilt $n [mm] \mod [/mm] m=r$ genau dann, wenn es ein $k [mm] \in \IN_0$ [/mm] so gibt, dass $n=k*m+r$
(Ähnliches kann man auch auf [mm] $\IZ$ [/mm] definieren, ich weiß gerade nicht, ob ihr nur auf [mm] $\IN$ [/mm] bzw. [mm] $\IN_0$ [/mm] Modulo-Rechnungen definiert habt oder auch auf [mm] $\IZ$, [/mm] aber ich denke, dass Du Dir das ggf. auch selbst weiterdenken könntest, wie es zu definieren wäre.)
Z.B.:
$15 [mm] \mod [/mm] 4=3$, denn:
Zunächst ist hier $r=3 [mm] \in \{0,1,...,(n-1)\}=\{0,1,2,3\}$, [/mm] also es gelten $r [mm] \in \IN_0$ [/mm] und $0 [mm] \le [/mm] r < 4$.
Ferner:
15=3*4+3, und es ist $k=3 [mm] \in \IN_0$ [/mm] .
Gogetta hatte das schon getan:
$(a*b) [mm] \mod [/mm] c=1$ hat er umgeschrieben zu:
$a*b=k*c+1$ (wobei er $k [mm] \in \IN_0$ [/mm] als selbstverständlich angenommen hat und es nicht extra dazugeschrieben hat, das kannst Du aber tun, wenn Du magst, also genauer schreiben:
$(a*b) [mm] \mod [/mm] c=1 [mm] \gdw \exists [/mm] k [mm] \in \IN_0$: [/mm] $a*b=k*c+1$ etc.)
Das wurde hier getan. Und wenn wir uns das nun mal angucken:
[mm] $k*c^2+c=c(k*c+1)=b*(n*b+1)=n*b^2+b$, [/mm] so erkennst Du Gogettas Argumentation
> Die linke seite ist durch c teilbar also muss es die rechte auch sein!
[mm] $\frac{k*c^2+c}{c}=\frac{c*(k*c+1)}{c}=k*c+1 \in \IN_0$, [/mm] also muss auch [mm] $\frac{n*b^2+b}{c} \in \IN_0$ [/mm] gelten.
> Natürlich ist auch anderstrum die rechte seite durch b teilbar also muss
> es die linke auch sein.
[mm] $\frac{n*b^2+b}{b}=\frac{b*(n*b+1)}{b}=n*b+1 \in \IN_0$, [/mm] also muss auch [mm] $\frac{k*c^2+c}{b} \in \IN_0$ [/mm] gelten...
Ob man damit nun weiterkommt oder nicht, weiß ich gerade nicht, soviele Gedanken habe ich mir noch nicht zu der Aufgabe gemacht...
Aber Du kannst Dir ja folgendes überlegen:
Nach Voraussetzung gilt $a [mm] \le [/mm] b [mm] \le [/mm] c$, und nun soll [mm] $\frac{n*b^2+b}{c} \in \IN_0$ [/mm] gelten....
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:58 Di 12.02.2008 | | Autor: | Boki87 |
Super...soweit ist des echt einleuchtend.
Aber trotzdem komme ich nicht weiter...weil mir einfach allgemein nicht klar ist was ich letzten endes erreichen müsste um das zu beweisen.
Eigentlich hab ich mir gedacht das man irgendwie 3 gleichungen mit 3 unbekannten aufstellt...aber da wenn man mod umwandelt eine 4te unbekannte auftaucht komm ich auf keine 4 gleichung damit ich 4 gleichungen mit 4 unbekannten hätte.
hat da vllt einer eine idee?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:32 Di 12.02.2008 | | Autor: | Gogeta259 |
Erst mal sorry, dass ich die Modulo funktionen einfach so angewendet habe ohne weiter zu erläutern(ich dachte du kennst dich damit aus weil du auch nichts anderes gesagt hast).
Im grunde geht es bei solchen aufgaben immer deine Kandidatenliste zu verkleinern (darum gereade gerade gerade)
Damit du dann am Ende nur noch ganz wenige kandidaten hast die du dann per hand überprüfen kannst!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:48 Di 12.02.2008 | | Autor: | Gogeta259 |
Also was ich zuerst machen würde, wäre zu zeigen, dass nur die Kombination gerade,ungerade, ungerade klappen kann.
Dann würde ich zeigen mit einnem ansatz der form 2*n für die gerade zahl, dass n gleich 1 sein muss oder durch den ansatz [mm] 2^n*t [/mm] und dann bist du auch schon fast fertig.
Ich wähle immer die gerade ungerade eigenschaft weil sie die einfachste ist (2 zustände).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:48 Di 12.02.2008 | | Autor: | Boki87 |
woran sieht man denn mathematisch das gerade gerade gerade nicht sein kann, weil ich versuch grad gerade, gerade , ungerade auszuschließen aber es will mir einfach nicht gelingen...ich sehs zwar anhand dessen das ich irgendwelche werte reinsetzte und nie mod 1 sein kann...aber das ist ja kein mathematischer beweis.
|
|
|
| |
|
Als erste muss du eine Reihenfolge deiner Variablen wäheln (da es ein Symmetrisches problem ist kannst du O.B.d.A bestimmte Rollen festsetzen); Ich setzte a =>b=>c
Gerade gerade, gerade geht nicht wegen den Gleichungen(== als Kongruenzzeichen):
a*b==1(mod c)
==> a*b=k*c+1
JEtzt ist die rechte seite durch 2 teilbar ==> die rechte muss es auch sein aber wir haben da k*c (ist gerade) +1 also ist die zahl ungerade==> gerade gerade gerade geht nicht!
gerade gerade ungerade geht nicht weil
wegen a*c==1(mod b) denn a*c=l*b+1
Jetzt ist die linke Seite durch 2 teilbar weil a gerade ist aber die rechte seite nicht da l*b wegen b gerade wird aber durch die 1 ungerade ==> nicht durch 2 teilbar ==> gerade gerade ungerade geht auch nicht.
Und so geht es dann weiter bis du zeigst(also alle 8 möglichkeiten abklappern), dass gerade ungerade ungerade die einzige möglichkeit ist.
Dann fängst du an mit dem geraden Element(bei mir a) rumzuspielen und zeigst dass dieses nur 2 sein kann und dann bist du fertig(so gut wie der rest ist dann trivial :D).
Ich hoffe ich konnte dir helfen.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 00:03 Mi 13.02.2008 | | Autor: | Boki87 |
Vielen dank schonmal...alleine wäre ich da nie drauf gekommen.
aber eins ist mir trotzdem nicht klar...wie komm ich darauf das grad das kleinste Element gerade sein muss und nicht ein anderes?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:14 Mi 13.02.2008 | | Autor: | Gogeta259 |
Ja des mit der Ungleichung ist nur gegeben, damit du wirklich nur eine Lösung hast sonst hättest du 3 Lösungen, da die Modulogleichungen symmetrisch sind.
Aber ich rechne die Gleichung erst allgemein sprich ohne diese Ungleichung.
Ich hab ja in meinem Text gesagt dass ich einfach a als die gerade Zahl verwende. Wenn du dann gezeigt hast, dass
Paar (2,3,5) die einzige ( eigentlich ja drei) lösung ist dann sagst du noch wegen der Ungleichung a<=b<=c folgt, dass es nur eine Lösung gibt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:21 Do 14.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
