p * q = a² + 1

[Otmar]

Gesucht sind drei verschiedene Primzahlen kleiner als 17, die paarweise multipliziert, drei Produkte bilden, die um Eins größer sind, als eine Quadratzahl. Kann man zu diesen drei Primzahlen eine vierte Primzahl größer als 17 finden, so dass diese vierte Primzahl mit den drei anderen drei weitere Produkte bildet, die um Eins größer sind, als eine Quadratzahl?

[gp3050]

Mehr ->

Es gibt genau 6 Zahlen, die kleiner als 17 sind, und die Bedingung 1 (ist eine Primzahl) erfüllen.
2,3,5,7,11,13. Nun könnte man einmal das Produkt aus allen möglichen Kombinationen bilden. Mit 2 ergeben sich direkt 2 Treffer. Einmal 2x5, sowie 2x13. Des weiteren ist 5x13 auch ein Treffer, womit schon ein Trio gefunden wäre. Es gibt keine weiteren Zahlen, die dieses Kriterium erfüllen. Also sind unsere 3 gesuchten Zahlen 2,5 und 13. Nun stellt sich die Frage, ob es eine weitere Primzahl gibt >17 gibt, die dieses Kriterium erfüllt. In den paar Minuten, die ich bisher probiert habe, habe ich alle Möglichkeiten für a^2 bis a=100 probiert, habe jedoch keine Lösung erhalten, die für alle 3 Zahlen funktioniert

[Neuling]

Mehr ->

Die drei Primzahlen sind 2, 5 und 13.
2 * 5 = 3² + 1
2 * 13 = 5² + 1
5 * 13 = 8² + 1

Gesucht ist jetzt eine Primzahl r > 17 mit
2 * r = x² + 1
5 * r = y² + 1
13 * r = z² + 1

Primzahlen größer als 17 können nur auf 1, 3, 7, 9 enden.
Quadratzahlen können nur auf 0, 1, 4, 5, 6, 9 enden.

2 * r - 1 = x²
Für Einerstelle r = 1 (3, 7, 9) endet x² auf 1 (5, 3, 7) ---> Primzahl r darf nicht auf 7 oder 9 enden.

13 * r - 1 = z²
Für Einerstelle r = 1 (3, 7, 9) endet z² auf 2 (8, 0, 6) ---> Primzahl r muss auf 7 oder 9 enden.

Widerspruch! - Es gibt keine Primzahl, die die Bedingungen der Aufgabe erfüllt.

Eigentlich zu leicht für eine harte Nuss. Da habe ich bestimmt wieder mal einen Denkfehler drin!?

[MadMac]

Mehr ->

Nein.

Die gesuchten drei Zahlen kleiner 17 sind 2, 5 und 13.

n*2 = a1^2+1
n*5 = a2^2+1 = a1^2+1 + 3n (3n ungerade)
n*13 = a3^2+1 = a1^2+1 + 11n (11n ungerade)

3 und 11 sind Primzahlen, n ist eine Primzahl.

Die Quadratzahlen lassen sich darstellen als Summe von aufeinanderfolgenden ungeraden Zahlen.

a1^2 = summe(1..2a1-1)(ungerade Zahlen) = 1+3+5+7+...+2a1-1

Ergo ist (a2^2+1) - (a1^2+1) = 2a1+1 + 2a1+3 + ... + 2a2-1

Diese Summe ist in den Zeilen oben 3n bzw. 11n.

Beide sind ungerade, also kann es keine gerade Anzahl Summanden geben.

Bei einer ungeraden Anzahl Summanden lässt sich die Summe

2a1+1 + 2a1+3 + ... + 2a2-1

umformen in

summe(n-x + ... n-4 + n-2 + n + n+2 + n+4 ... + n+x)
ODER
summe(3-n+1 + ... 3-4 + 3-2 + 3 + ... + 3+n-1)
bzw.
summe(11-n+1 + ... 11-4 + 11-2 + 11 + ... + 11+n-1)

Letztere beide Formen kann ich ausschließen, da die Summanden für n > 17 teilweise kleiner 0 wären, solche kommen in der Summendarstellung von Quadratzahlen (und somit auch in der Summendarstellung der Differenz zweier Quadratzahlen) nicht vor.

Nach der ersten Darstellung wäre

a2^2 = a1^2 + n-2 + n + n+2 = summe(1..n+2)(ungerade Zahlen) = (a1+3)^2
und
a3^2 = a1^2 + n-10 + n-8 + n-6 + ... n + ... + n+10 = summe(1..n+10)(ungerade Zahlen) = (a1+11)^2

Andere Variationen sind ausgeschlossen.


Es ergibt sich

2a1+1 = n-2 und gleichzeitig 2a1+1 = n-10, das ist ein Widerspruch.

Probier's mit Zahlen, deren Differenzen nicht auch Primzahlen sind. Dann besteht nach meiner Beweisführung noch eine theoretische Chance (an die ich aber selber kaum glaube).

Gruß,
MadMac

[Otmar]

Ja schön! an Neuling und MadMac Ein Trostpreis geht an gp3050 für den gemachten Anfang.

@Neuling, deiner Lösung hab ich nichts hinzuzufügen. Wie immer sehr schön beschrieben.
@MadMac, eine Kleinigkeit würde ich noch ergänzen:

Mehr ->

Bei einer ungeraden Anzahl Summanden lässt sich die Summe

2a1+1 + 2a1+3 + ... + 2a2-1

umformen in

summe(n-x + ... n-4 + n-2 + n + n+2 + n+4 ... + n+x)
ODER
summe(3-n+1 + ... 3-4 + 3-2 + 3 + ... + 3+n-1)

Hier hab ich versucht zwischen den Zeilen zu lesen, denn der Begriff "umformen" stimmt ja nicht ganz, weil bei einer Umformung der Wahrheitsgehalt einer Gleichung erhalten bleibt.

Hab's so verstanden:

Zur besseren Lesbarkeit verwende ich a1=r und a2=s.

3n = 2s+1 + 2s+3 + .... + 2r-1 (Anzahl der Summanden k)
Umformen liefert:
3n = m-x + ... + m-4 + m-2 + m + m+2 + m+4 ... + m+x (Anzahl der Summanden k, m die Zahl in der Mitte.)
3n = k * m
Jetzt argumentierst du m.E. so:
"Weil 3 und n Primzahlen sind, muss man jetzt für m entweder 3 oder n einsetzen."
Und daraus folgt:
entweder muss gelten:
3n = n-x + ... n-4 + n-2 + n + n+2 + n+4 ... + n+x
oder es muss gelten:
3n = 3-n+1 + ... 3-4 + 3-2 + 3 + ... + 3+n-1

Dieser Schluss ist nicht ganz OK, weil es noch eine weitere dritte Möglichkeiten gibt:

Und zwar für s=r+1, was ja noch nirgends ausgeschlossen war:
Dann ist k=1 und m=3n (k=3n und m=1 ist trivial ausschließbar). Beispiel: r=28, s=29: 3n = 2*28+1 = 1*57 = 3*19

Wegen a3 > a2 > a1, also a3 > a1+1 geht diese dritte Möglichkeit für die zweite Gleichung 11n = ... natürlich nicht.

Der Widerspruch würde dann lauten:

Es ergibt sich: 2a1+1 = n-2 oder 2a1+1 = 3n und gleichzeitig 2a1+1 = n-10, das ist ein Widerspruch.

Sicher kann man den Fall m=3n auch anders ausschließen, aber der Ordnung halber sollte man es dann auch aufschreiben.

Eine meiner Lösungen geht so:

Mehr ->

Die drei gesuchten Primzahlen 2, 5 und 13 lassen sich durch Probieren finden.

Angenommen die vierte Primzahl sei p > 17. Dann gilt: 2p=r²+1 und 5p=s²+1. (Die dritte Gleichung 13p=... braucht man gar nicht.)
Aus beiden Gleichungen erhält man nach Multiplikation mit 5 bzw. 2:

10p = 5r²+5 = 2s²+2 --->
2s² = 5r²+3 > 5r² = 2*10r²/4 > 2*9r²/4 = 2*(3r/2)² --->
s² > (3r/2)² --->
s > 3r/2 --->
s-r > r/2

Wegen p > 17 ist r² > 2*17-1=33, also r >= 6 und damit s-r > r/2 >= 6/2 --->s-r > 3.
Subtrahiert man beide Gleichungen von ganz oben und verwendet die 3. binomische Formel, steht da:
5p-2p=s²-r²=(s-r)*(s+r)=3p

Da s-r > 3 und s+r > r > 6 also auch s + r > 3 und die Zahl 3p=(s-r)*(s+r) eine eindeutige Primfaktorzerlegung hat, gibt es einen Widerspruch, da entweder s-r oder s+r drei oder 1 sein müsste, was nicht der Fall ist.

Eigentlich zu leicht für eine harte Nuss.

Stimmt, aber ich hatte mich an den "alten" Rätseln in dieser Rubrik orientiert. Tatsächlich ist das Original eine ganze Ecke schwieriger. Dort sind die drei zu suchenden Primzahlen gegeben und es soll beweisen werden, dass es keine vierte von den drei gegebenen Zahlen verschiedenen natürlich Zahl gibt, die mit den drei anderen drei Produkte bildet, die um Eins größer sind, als eine Quadratzahl. Also die Bedingung, dass auch die vierte Zahl eine Primzahl > 17 ist, braucht man nicht. Wer mag, kann das ja mal versuchen.

[Neuling]

Tatsächlich ist das Original eine ganze Ecke schwieriger. Dort sind die drei zu suchenden Primzahlen gegeben und es soll beweisen werden, dass es keine vierte von den drei gegebenen Zahlen verschiedenen natürlich Zahl gibt, die mit den drei anderen drei Produkte bildet, die um Eins größer sind, als eine Quadratzahl. Also die Bedingung, dass auch die vierte Zahl eine Primzahl > 17 ist, braucht man nicht. Wer mag, kann das ja mal versuchen.

Ich habe es mal versucht:

Mehr ->

Nach der gleichen Methode wie oben, betrachte ich jetzt die Einerstelle einer gesuchten Zahl n. Dabei verwende ich, dass ich 1, 3, 7, 9 schon ausgeschlossen habe und untersuche nur noch 0, 2, 4, 5, 6, 8
Da 2*n - 1 für Einerstelle n = 2 bzw. 4 auf 3 bzw. 7 endet, fallen diese beiden schon mal raus.
Da 13*n - 1 für Einerstelle n = 6 bzw. 8 auf 7 bzw. 3 endet, fallen auch diese beiden raus.

Wenn es also eine Zahl n gibt, dann kann sie nur auf 0 oder 5 enden.
Für n = 10 (20, 30, 40, 50, 60, 70, 80, 90, 100) endet 2*n - 1 auf 19 (39, 59, 79, 99, 19, 39, 59, 79, 99). Darauf kann keine Quadratzahl enden (die Zehnerstelle muss bei Einerstelle 9 gerade sein - müsste man noch beweisen.)

Damit muss nur noch die Einerstelle 5 untersucht werden.
Für n = 15 (35, 55, 75, 95) endet 5*n - 1 immer auf 74 - so kann keine Quadratzahl enden (die Zehnerstelle muss bei Einerstelle 4 gerade sein - müsste auch noch bewiesen werden.)

Es bleiben für die weitere Untersuchung Zahlen > 100, die auf 05, 25, 45, 65 oder 85 enden. (n > 100, weil ich 25, 45, 65 und 85 probiert habe - führen nicht zu einer Lösung und 5 ja ausgeschlossen ist.)

Hier endet im Moment mein Latein (und hier beginnt für mich die harte Nuss )

[Otmar]

gar nicht schlecht!

Mehr ->

die Zehnerstelle muss bei Einerstelle 9 gerade sein - müsste man noch beweisen.
....
die Zehnerstelle muss bei Einerstelle 4 gerade sein - müsste auch noch bewiesen werden.

Gut erkannt. Das wären die Beweise dafür:

Einerstelle 9 geht nur bei (10a±3)² =10a(10a ± 6) + 9
Einerstelle 4 geht nur bei (10a±2)² =10a(10a ± 4) + 4

Weiß aber nicht, ob es weiter hilft. Meine Lösung geht ganz ähnlich, aber es gibt einen entscheidenden Unterschied. Vielleicht bin ich darauf gekommen, weil ich mir Zahlen oft in Computern ansehen muss...

[Otmar]

Anbei eine Lösung zum Original:

Mehr ->

Ganz ähnlich zu der Lösung von Neuling, kann man auch zeigen, dass es keine ganze Zahl gibt, die die Anforderung erfüllt. Dazu geht man aber ins Hexadezimalsystem. Dort ist der Prozentsatz der Endziffern für Quadratzahlen noch kleiner als im Dezimalsystem:

0² = 0
(±1)² = 1
(±2)² = 4
(±3)² = 9
(±4)² = 10
(±5)² = 19
(±6)² = 24
(±7)² = 31
8² = 40

Also sind nur ein Viertel der Endziffern, nämlich 0, 1, 4 und 9 möglich für Quadratzahlen. Für a²+1 gehen also nur Endziffern 1, 2, 5 und A.

Die gesuchte Zahl x hat eine der Endziffern 0, 1, ... , 9, A, B, ..., F

2 * x hat eine gerade Endziffer, also eine von 0, 2, 4, 6, 8, A, C, E. Davon sind nur 2 oder A erlaubt. D.h. x endet auf
1 oder 9 für Endziffer 2 von 2 * x = a² + 1 oder
5 oder D für Endziffer A von 2 * x = a² + 1

5 * x endet für verbliebene Endziffern von x:
1, 5, 9, D
auf Endziffer 5, 9, D, 1 und davon sind für a²+1 nur 5 und 1 erlaubt. D.h x endet auf 1 oder D.

D * x endet für verbliebene Endziffern von x:
1 oder D
auf D oder 9. Beide sind für a²+1 nicht möglich. D.h. es gibt kein passendes x als vierte Zahl. Was zu beweisen war.

Die Originalaufgabe war die erste Aufgabe bei der internationalen Matheolympiade 1986. Alle Achtung für die jungen Teilnehmer, die da in kurzer Zeit draufgekommen sind!