Gemeinsame Teiler 2er Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:15 Do 18.12.2008 | | Autor: | adoon |
| Aufgabe | Gesucht ist das kleinste Paar (a,b) natürlicher Zahlen, so dass
a und b einen gemeinsamen Teiler [mm] \ge [/mm] 2 haben
a+1 und b einen gemeinsamen Teiler [mm] \ge [/mm] 2 haben
a und b+1 einen gemeinsamen Teiler [mm] \ge [/mm] 2 haben |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also ich habe bisher keinen vernünftigen Ansatz gefunden... Das a und b in Primfaktoren zu zerlegen, hat zu nichts geführt, denn wenn [mm] a=p_1^{b_1}*...*p_n^{b_n}, [/mm] dann kann ich zwar viel über gemeinsame Teiler von a und b sagen, aber ich hab keine Informationen zu [mm] p_1^{b_1}*...*p_n^{b_n} [/mm] + 1 bezüglich irgendwelcher Teiler. Ich hab die Zahlen a=2 und b=6 gefunden, da haben a und b einen gT und a+1 und b, aber ich habs nicht geschafft, 2 Zahlen zu finden, so dass alle 3 Eigenschaften gelten. Gibt es überhaupt a und b? Ich hab auch überlegt, ob man irgendwas über a > b oder so aussagen kann und so einen Widerspruch erzeugen kann, aber das hat bisher auch zu nichts geführt :o(
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:28 Do 18.12.2008 | | Autor: | M.Rex |
Hallo und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich würde versuchen, ein GLS aufzustellen.
> Gesucht ist das kleinste Paar (a,b) natürlicher Zahlen, so
> dass
> a und b einen gemeinsamen Teiler [mm]\ge[/mm] 2 haben
Also gibt es ein m, so dass a=m*b
> a+1 und b einen gemeinsamen Teiler [mm]\ge[/mm] 2 haben
Also gibt es ein n, so dass a+1=n*b
> a und b+1 einen gemeinsamen Teiler [mm]\ge[/mm] 2 haben
Also gibt es ein l, so dass a=l(b+1)
Das ganze kannst du mal in ein GLS packen, und aussagen über die Lösbarkeit treffen. (mit [mm] m;n;l\ge2 [/mm] )
Also: [mm] \vmat{a=m*b\\a+1=n*b\\a=l(b+1)}
[/mm]
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:36 Do 18.12.2008 | | Autor: | adoon |
Das haut nicht hin. Es ist nicht gefordert, dass a ein Vielfaches von b ist, sondern nur, dass a und b einen gemeinsamen Teiler haben. Als ich glaube, ein GLS kann ich ohne Weiteres nicht aufbaun.
Trotzdem danke für deine Antwort.
|
|
|
| |
|
Hallo,
nette Aufgabe.
Schwierig wird vor allem der Nachweis, dass Du das kleinste Paar solcher Zahlen gefunden hast, wenn Du denn welche hast.
Du kannst leicht zeigen, dass die drei genannten gemeinsamen Teiler zueinander teilerfremd sein müssen. Nennen wir die drei Teiler [mm] s,t,u\in\IN, [/mm] dann gilt s,t,u>1, ggT(s,t)=ggT(s,u)=ggT(t,u)=1
Es sei nun:
[mm] a\equiv b\equiv 0\mod{s}
[/mm]
[mm] a\equiv b+1\equiv 0\mod{t}
[/mm]
[mm] a+1\equiv b\equiv 0\mod{u}
[/mm]
Hieraus gewinnst Du ohne große Nachbearbeitung Angaben für a und b, die Du mit dem chinesischen Restesatz auflösen kannst.
Dass s,t,u aller Wahrscheinlichkeit nach die drei kleinstmöglichen teilerfremden Zahlen >1 sind, darf man annehmen: s,t,u=2,3,5. Nur fragt sich, welche der 6 möglichen Zuordnungen das kleinste Paar liefert.
edit: es zeigt sich, dass s,t,u=2,5,7 eine kleinere Lösung liefert!
Im Endeffekt wirst Du wohl zu Fuß zeigen müssen, dass alle kleineren Paare (nebenbei: wann ist ein Paar kleiner?) die Bedingung nicht erfüllen.
edit: siehe zur Lösung und zur Überprüfung auch diesen Beitrag.
Falls Du eine Beispielrechnung brauchst, könnte ich eine z.B. für s,t,u=7,8,9 einstellen. Aber vielleicht probierst Du erst mal selbst, wie weit Du kommst.
Viel Erfolg!
|
|
|
| |
|
Hmmm. Ich glaube, mein letzter Beitrag hätte hierhin gehört, als Antwort auf Deine erste Anfrage.
Trotzdem noch ein kurzer Nachtrag: für das kleinste Paar a,b, das ich auf die Schnelle finde, gilt: [mm] a+b\equiv0\mod{7}.
[/mm]
Nur so zur Kontrolle.
Der Nachweis, dass es sich um das kleinste Paar handelt, ist auch nicht so mühsam, wenn Du zeigen kannst, dass es im vorliegenden Fall genügt, wenn a,b,a+1,b+1 nicht prim sein dürfen und |a-b| höchstens dann prim ist, wenn |a-b|=s,t,u. Vielleicht aber ist es mehr Aufwand, dass alles zu zeigen, statt einfach die 148 möglichen "kleineren" Paare vernünftig gruppiert durchzugehen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:44 Do 18.12.2008 | | Autor: | adoon |
Ah, alles klar
Danke für die Hilfe :)
Ich glaub, ich hab die Zahlen gefunden, müssten 15 und 20 sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:00 Do 18.12.2008 | | Autor: | reverend |
Die habe ich auch. 
edit: Es gibt aber eine kleinere Lösung, wenn man die Teiler 2,5,7 ansetzt. Dann findet man das Paar 14,6.
Darauf hat mich adoon nach Besprechung der Aufgabe hingewiesen.
Jetzt der Ausschluss der kleineren Paare:
Sei a die größere, b die kleinere Zahl.
a=19 geht nicht, weil prim
a=18 geht nicht, weil a+1 prim
a=17 geht nicht, weil a prim
a=16 geht nicht, weil a+1 prim
a=15:
. b=14 ...
. b=13 -> b prim
. b=12 -> b prim
.
.
.
So viele Fälle gibt es gar nicht zu untersuchen.
edit: ... und wenn man das gründlich tut, dann findet man natürlich das angegebene kleinere Paar.
Sieht jemand übrigens einen eleganteren Weg? Mir gefällt dieser noch nicht.
Grüße,
rev
|
|
|
|
