euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Gibt es eine obere Schranke für die maximale Anzal der Divisionen mit Rest für zwei beliebige Zahlen a, [mm] b\in \IN? [/mm] |
Hallo zusammen,
hab mal wieder ein zahlentheoretisches Problemchen. Hat es was damit zu tun, welche Differenz a und b haben? Meine ,,heißeste" Spur war bisher, dass die Reste ja immer kleiner werden müssen. Weiß aber nicht wies weitergehen soll.
Wär echt super wenn mir jemand nen kleinen Tipp geben könnt.
Gruß, der KommissarLachs
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:36 So 27.05.2007 | | Autor: | statler |
Guten Morgen!
> Gibt es eine obere Schranke für die maximale Anzal der
> Divisionen mit Rest für zwei beliebige Zahlen a, [mm]b\in \IN?[/mm]
>
> hab mal wieder ein zahlentheoretisches Problemchen. Hat es
> was damit zu tun, welche Differenz a und b haben? Meine
> ,,heißeste" Spur war bisher, dass die Reste ja immer
> kleiner werden müssen. Weiß aber nicht wies weitergehen
> soll.
> Wär echt super wenn mir jemand nen kleinen Tipp geben
> könnt.
Mir kommen da 2 mögliche Ansätze in den Sinn.
1. Wenn auch negative Reste r zugelassen sind, dann ist jedenfalls im ersten Schritt |r| [mm] \le \bruch{b}{2}. [/mm] Was ergibt dann der 2. Schritt?
2. Wenn - wie meistens - nur positive Reste genehm sind, dann kann man sich mal überlegen, was denn so im dummsten Fall passieren kann. Das ist, daß der Divisor immer nur einmal in den Dividenden paßt. Und jetzt fang mal von hinten an: Wie lautet dann die letzte Zeile? Und die vorletzte? Usw. Da müßtest du in das gelobte Fibonacci-Land kommen.
Gruß und frohe Pfingsten
Dieter
|
|
|
| |
|
> 2. Wenn - wie meistens - nur positive Reste genehm sind,
> dann kann man sich mal überlegen, was denn so im
> dummsten
> Fall passieren kann. Das ist, daß der Divisor immer nur
> einmal in den Dividenden paßt. Und jetzt fang mal von
> hinten an: Wie lautet dann die letzte Zeile? Und die
> vorletzte? Usw. Da müßtest du in das gelobte Fibonacci- > Land kommen.
Hallo und guten Morgen,
danke erstmal für die schnelle Antwort. Die Variante 2 passt zu unserer Definition vom Rest. Nur kann ich keine Verbindung zu Fibonacci entdecken. Wäre super, wenn du mir das erklärst.
Gruß, KommissarLachs
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:42 So 27.05.2007 | | Autor: | statler |
Moin noch mal!
> danke erstmal für die schnelle Antwort. Die Variante 2
> passt zu unserer Definition vom Rest. Nur kann ich keine
> Verbindung zu Fibonacci entdecken. Wäre super, wenn du mir
> das erklärst.
Naja, die letzte Zeile wäre doch in diesem Fall
2 = 2*1
(1 = 1*1 geht nicht, weil bie Division durch 1 kein Rest bleibt und die vorletzte Z. dann schon die letzte gewesen wäre)
und die vorletzte
3 = 1*2 + 1
und die drittletzte dann
? = 1*3 + 2
usw.
Siehst du jetzt Land?
Gruß
Dieter
|
|
|
| |
|
Hallo und besten Dank.
Also deine Argumentation in Ehren, aber ich sehe leider keine Verbindung zwischen Fibonacci und der Aufgabe. Wie komm ich denn auf eine Zahl n, wenn die FibonacciZahlen ständig wachsen?
Gruß, KommissarLachs
|
|
|
| |
|
> Also deine Argumentation in Ehren, aber ich sehe leider
> keine Verbindung zwischen Fibonacci und der Aufgabe. Wie
> komm ich denn auf eine Zahl n, wenn die FibonacciZahlen
> ständig wachsen?
Die Aufgabenstellung ist nicht ganz klar:
1) Fuer jedes Paar [mm] $a,b\in \IN$ [/mm] gibt es ganz sicher eine obere Schranke der Divisionen mit Rest. Diese haengt natuerlich von den Zahlen $a,b$ ab, kann aber nicht groesser als die groesste Zahl unter diesen sein (grobe Abschaetzung)
2)Gibt es eine obere Schranke unabhaengig von $a,b$? Ich denke, dass mein Vorredner darauf abzielen wollte und deshalb die Fibonacci-Folge erwaehnt hat. Mir ist aber auch noch nicht klar, weshalb...
LG Kornfeld
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:47 So 27.05.2007 | | Autor: | statler |
Hallo!
> Die Aufgabenstellung ist nicht ganz klar:
> 1) Fuer jedes Paar [mm]a,b\in \IN[/mm] gibt es ganz sicher eine
> obere Schranke der Divisionen mit Rest. Diese haengt
> natuerlich von den Zahlen [mm]a,b[/mm] ab, kann aber nicht groesser
> als die groesste Zahl unter diesen sein (grobe
> Abschaetzung)
Das ist klar, weil es ja jedesmal mindestens um 1 'runtergeht'. Aber ich hatte mir eigentlich gedacht, daß n-2 eine obere Schranke ist, wenn die größere der beiden Zahlen kleiner oder gleich der n-ten Fibonacci-Zahl ist.
(Wobei [mm] F_{0} [/mm] = 0, [mm] F_{1} [/mm] = 1 ist.)
> 2)Gibt es eine obere Schranke unabhaengig von [mm]a,b[/mm]? Ich
> denke, dass mein Vorredner darauf abzielen wollte und
> deshalb die Fibonacci-Folge erwaehnt hat. Mir ist aber auch
> noch nicht klar, weshalb...
So eine Schranke gibt es nicht, wie eben daraus folgt: Wenn ich mit der n-ten und der (n-1)-ten Fibonacci-Zahl anfange, brauche ich n-2 Divisionen. Daß man die Aufgabe überhaupt so auffassen kann (sollte?), ist mir erst durch eure Kritik aufgefallen.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Hallo,
laut Aufgabenstellung geht es darum eine obere Schranke für die Dauer des euklidischen Algorithmus für beliebige Paare von Zahlen a,b zu bestimmen.
Daher auch mein Problem. Ich wüsste nicht, wie man da ran gehen sollte.
Hoffe, dass es jetzt etwas deutlicher ist.
|
|
|
| |
|
Hallo nochmals,
also eure Tipps leuchten mir mittlerweile ein. Irgendwie scheinen die Fibonacci-Zahlen was damit zu tun zu haben. Könnt mir vielleicht noch jemand erklären, wie ich damit jetzt anfangen soll???
Gruß, KommissarLachs
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 29.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
