Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » HJKweseleits Thread

HJKweseleits Thread

Universität / Fachhochschule

Tags: Klotzturmproblem

Randolph Esser aktiv_icon

02:04 Uhr, 31.05.2026

Hallo !

Dies bezieht sich auf einen Thread von HJKweseleit,

der hier bis vor kurzem noch in den Charts war (siehe Anhang).

Ich repetiere nochmal kurz, wobei hier

0 \notin ℕ

gelte:

Seien

a, b \in ℕ

mit

a, b \geq 2

und

g g T (a, b) = 1

.

Dann gibt es (nach eventuellem Vertauschen von a und

b)

gemäß Bezout

r, s \in ℕ,

sodass

r a - s b = 1

.

Für

n \in ℕ

gilt dann also

r a n - s b n = n

und wegen

a (- k b) + b (k a) = 0

für alle

k \in ℤ

(wobei

{k (\begin{matrix} - b \\ a \end{matrix}) : k \in ℤ}

auch genau alle ganzzahligen Lösungen von

a x + b y = 0

sind) weiter

a (r n - k b) + b (- s n + k a) = n

für alle

k \in ℤ

.

Die Forderungen

r n - k b \geq 0, - s n + k a \geq 0

liefern dann

\frac{s n}{a} \leq k \leq \frac{r n}{b}

.

So, nun zunächst ein Beweis, dass es für

n := (a - 1) (b - 1)

ein ganzes solches

k

gibt.

Fall

1, a > b :

\frac{s n}{a} \leq k \leq \frac{r n}{b} | n = (a - 1) (b - 1) = a b - a - b + 1

\Leftrightarrow

s (b - 1 - \frac{b}{a} + \frac{1}{a}) \leq k \leq r (a - \frac{a}{b} - 1 + \frac{1}{b}) | r = \frac{1 + s b}{a}

\Leftrightarrow

s (b - 1 - \frac{b}{a} + \frac{1}{a}) \leq k \leq (1 + s b) (1 - \frac{1}{b} - \frac{1}{a} + \frac{1}{a b})

\Leftrightarrow

s b - s - \frac{s b}{a} + \frac{s}{a} \leq k \leq s b - s - \frac{s b}{a} + \frac{s}{a} + 1 - \frac{1}{b} - \frac{1}{a} + \frac{1}{a b} | \frac{s b}{a} = r - \frac{1}{a}

\Leftrightarrow

s b - s - r + \frac{1}{a} + \frac{s}{a} \leq k \leq s b - s - r + \frac{s}{a} + 1 - \frac{1}{b} + \frac{1}{a b} | \frac{s}{a} = \frac{r}{b} - \frac{1}{a b}

\Leftrightarrow

s b - s - r + \frac{1}{a} + \frac{r}{b} - \frac{1}{a b} \leq k \leq s b - s - r + \frac{r}{b} + 1 - \frac{1}{b}

| \frac{r}{b} = m_{r} + \frac{p_{r}}{b}

für ein

m_{r} \in ℕ_{0}

und ein

p_{r} \in ℕ

mit

p_{r} < b,

b

nicht

r

teilt,

insbesondere gilt auch

g g T (p_{r}, b) = 1

\Leftrightarrow

s b - s - r + m_{r} + \frac{p_{r}}{b} + \frac{b - 1}{a b} \leq k \leq s b - s - r + m_{r} + 1 + \frac{p_{r} - 1}{b} (I),

was wegen

0 < \frac{p_{r}}{b} + \frac{b - 1}{a b} < 1

(denn

\frac{b - 1}{a b} < \frac{1}{b})

und

\frac{p_{r} - 1}{b} \geq 0

eine ganze Zahl

k

einrahmt

(nämlich

s b - s - r + m_{r} + 1)

Fall

2, b > a :

\frac{s n}{a} \leq k \leq \frac{r n}{b} | n = (a - 1) (b - 1) = a b - a - b + 1

\Leftrightarrow

s (b - 1 - \frac{b}{a} + \frac{1}{a}) \leq k \leq r (a - \frac{a}{b} - 1 + \frac{1}{b}) | s = \frac{r a - 1}{b}

\Leftrightarrow

(r a - 1) (1 - \frac{1}{b} - \frac{1}{a} + \frac{1}{a b}) \leq k \leq r (a - \frac{a}{b} - 1 + \frac{1}{b})

\Leftrightarrow

r a - \frac{r a}{b} - r + \frac{r}{b} - 1 + \frac{1}{b} + \frac{1}{a} - \frac{1}{a b} \leq k \leq r a - \frac{r a}{b} - r + \frac{r}{b} | \frac{r a}{b} = s + \frac{1}{b}

\Leftrightarrow

r a - s - r + \frac{r}{b} - 1 + \frac{1}{a} - \frac{1}{a b} \leq k \leq r a - s - \frac{1}{b} - r + \frac{r}{b} | \frac{r}{b} = \frac{s}{a} + \frac{1}{a b}

\Leftrightarrow

r a - s - r + \frac{s}{a} - 1 + \frac{1}{a} \leq k \leq r a - s - \frac{1}{b} - r + \frac{s}{a} + \frac{1}{a b}

| \frac{s}{a} = m_{s} - \frac{p_{s}}{a}

für ein

m_{s} \in ℕ

und ein

p_{s} \in ℕ

mit

p_{s} < a,

da a nicht

s

teilt,

insbesondere gilt auch

g g T (p_{s}, a) = 1

\Leftrightarrow

r a - s - r + m_{s} - 1 - \frac{p_{s} - 1}{a} \leq k \leq r a - s - r + m_{s} - (\frac{p_{s}}{a} + \frac{a - 1}{a b}) (I I),

was wegen

\frac{p_{s} - 1}{a} \geq 0

und

0 < \frac{p_{s}}{a} + \frac{a - 1}{a b} < 1

(denn

\frac{a - 1}{a b} < \frac{1}{a})

eine ganze Zahl

k

einrahmt

(nämlich

r a - s - r + m_{s} - 1)

\approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx \approx

Das Gezeigte kann nun weiterverwendet werden, um zu zeigen,

dass es auch für

n := (a - 1) (b - 1) + q

mit

q \in ℕ, 1 \leq q \leq a + b - 2

klappt.

Für

a > b

ergibt sich

z . B

. mit

(I)

s b - s - r + (q + 1) m_{r} + \frac{(q + 1) p_{r}}{b} + \frac{b - (q + 1)}{a b} \leq k \leq s b - s - r + (q + 1) m_{r} + 1 + \frac{(q + 1) p_{r} - 1}{b}

(links kommt

q \frac{s}{a} = q (\frac{r}{b} - \frac{1}{a b}) = q (m_{r} + \frac{p_{r}}{b} - \frac{1}{a b})

dazu und rechts

q \frac{r}{b} = q (m_{r} + \frac{p_{r}}{b}))

.

Falls

\frac{(q + 1) p_{r}}{b} \in ℕ,

gilt

\frac{b - (q + 1)}{a b} \leq 0,

da dann

q + 1 \geq b

wegen

g g T (p_{r}, b) = 1,

und man findet

k = s b - s - r + (q + 1) m_{r} + \frac{(q + 1) p_{r}}{b}

.

Falls

\frac{(q + 1) p_{r}}{b} \notin ℕ,

also

\frac{(q + 1) p_{r}}{b} = t + \frac{v}{b}

mit

t \in ℕ_{0}

und

v \in ℕ, v < b,

hat man

s b - s - r + (q + 1) m_{r} + t + \frac{v}{b} + \frac{b - (q + 1)}{a b} \leq k \leq s b - s - r + (q + 1) m_{r} + 1 + t + \frac{v - 1}{b}

und findet

k = s b - s - r + (q + 1) m_{r} + t + 1

wegen

\frac{v}{b} + \frac{b - (q + 1)}{a b} < 1

und

\frac{v - 1}{b} \geq 0

.

Der Fall

b > a

geht mit

(I I)

analog.

HJKweseleit aktiv_icon

17:39 Uhr, 04.06.2026

Vielen Dank für deine Lösung. Mir fehlte die Idee, die entsprechenden Zahlen nach Euklid aufzuspalten, und das ist der Kern des Lösungsweges.

Randolph Esser aktiv_icon

03:49 Uhr, 05.06.2026

Ich danke auch für die Inspiration,
die ich zu Ende bringen durfte.

Was ich oben nicht gezeigt habe
(weil es gestört hätte und nicht besonders schwer ist):

b

teilt nicht

r :

Angenommen, es wäre doch so, also

r = k b

für ein

k \in ℕ

.
Dann erhalten wir

1 = r a - s b = b (k a - s),

also

b

teilt

1,

Widerspruch !

a teilt nicht

s

geht analog.

g g T (p_{r}, b) = 1 :

Angenommen,

g g T (p_{r}, b) > 1,

also

p_{r} = k c, b = k d

für

k, c, d \in ℕ, k \geq 2

.
Dann erhalten wir

1 = r a - s b = (m_{r} b + p_{r}) a - s b = k ((m_{r} d + c) a - s d),

also

k

teilt

1,

Widerspruch !

g g T (p_{s}, a) = 1

geht analog.

Randolph Esser aktiv_icon

04:27 Uhr, 05.06.2026

In meinem zweiten Beitrag habe ich ein bisschen Mist gebaut:

Die

k

dort sind andere als das im ersten Beitrag.

Ich kann es leider nicht mehr korrigieren, sorry.

Im angehängten Bild sind die

k

im zweiten Beitrag aber durch

z

ersetzt,

sodass es keinen Variablenkonflikt mehr gibt...

Randolph Esser aktiv_icon

02:13 Uhr, 06.06.2026

Mal nebenbei:

Onlinemathe scheint ja so gut wie tot zu sein.
Liegt das an KI ?
Wäre schade, wenn Onlinemathe nun vor die Hunde ginge.
Die Idee eines Matheforums ist großartig
und darf nicht sterben.
Schade auch, wenn die Menschheit
sich nun endgültig der totalen Verblödung (KI) hingeben würde...

Randolph Esser aktiv_icon

13:43 Uhr, 07.06.2026

. .

HJKweseleit aktiv_icon

18:57 Uhr, 10.06.2026

Durch Zufall bin ich (jetzt erst) auf einen einfachen Beweis von Sylvester gestoßen, der keine Fallunterscheidung benötigt und nur wenige Überlegungen enthält Es kommt beispielsweise nur eine einzige Division vor: a/(-a) = -1.

Gegeben: a, b

\in ℕ

mit ggt(a | b) = 1.
Behauptung: Für jedes n > ab - a - b, n

\in ℕ

gibt es eine Darstellung
n = xa + yb mit x, y

\in ℕ_{0}

, für n = ab - a - b aber nicht.

Beweis:

Mit Hilfe des Euklidschen Algorithmus findet man r, s

\in ℕ

mit
ra - sb = 1 (Bezout).

Dann ist nra - nsb = n, und für jedes k

\in ℤ

gilt:

(nr - kb)a + (ka - ns)b = n oder
xa + yb = n mit x = nr - kb und y = ka - ns.

-------- Bis hier stimmt das mit dem Bisherigen überein. ------

Betrachte die Zahlen ns+0, ns+1, ns+2, ... ns+(a-1).
Das sind a aufeinanderfolgende Zahlen aus

ℕ

, und folglich ist eine davon ein Vielfaches von a.

Folglich gibt es ein k mit ns

\leq

\leq

ns+(a-1). Daraus folgt

0

\leq

ka - ns = y

\leq

a - 1

Damit haben wir ein y

\in ℕ_{0}

gefunden, fraglich ist nun, ob das x dazu passt.

Sei nun n > ab - a - b.

Mit -y

\geq

-(a - 1) ergibt sich
Dann ist xa + yb = n

\overset{}{\Leftrightarrow}

xa = n - yb

\geq

n - (a-1)b > ab - a - b -(a-1)b = -a, also

xa > -a und damit x > -1, also x

\in ℕ_{0}

.

-----------------------------------------------------

Wäre xa + yb = ab - a - b mit x, y

\in ℕ_{0}

möglich, so folgt
a(x+1) + b(y+1) = ab.

Dann müssen a(x+1) durch b und b(y+1) durch a teilbar sein. Wegenn ggt(a | b) = 1 müssen dann
x+1 durch b teilbar sein, also

\geq

b und y+1 x+1 durch a teilbar, also

\geq

a und damit

ab = a(x+1) + b(y+1)

\geq

ab + ab =2ab, also

\geq

2ab, was zum Widerspruch führt.

-----------------------------------------------------------

Hierzu noch ein Rechenbeispiel: a = 11, b = 7, n = 151

2a - 3 b = 1, also r=2 und s=3

Dann ist ns = 151*3 =453. Die erste 11-er Zahl ab 453 ist 462, also 9 größer, daher ist y = 9.

11x + 9*7 = 151
11x = 151 - 63 = 88
x = 8

8*11 + 9 * 7 = 151

Randolph Esser aktiv_icon

20:21 Uhr, 10.06.2026

Gelesen und verstanden.
Schöner Beweis und schönes Rechembeispiel, Danke.
Jetzt bin ich Klotzturmprofi !

Randolph Esser aktiv_icon

08:43 Uhr, 11.06.2026

Und Haken machen...

1592502

1592479

	Status: nicht eingeloggt	Noch nicht registriert?