Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Bezout macht glücklich

Bezout macht glücklich

Universität / Fachhochschule

Tags: Bezout

Sukomaki aktiv_icon

07:27 Uhr, 14.09.2023

Hallo,

ich beschäftige mich zur Zeit mit der Frage, welche Zahlen - gegeben relativ prime Zahlen

A

und

B

- als Linearkombination dieser Erzeugenden darstellbar sind.

Sei

s

die Schranke, ab der alle Zahlen als Linearkombination von

A

und

B

mit Koeffizienten aus

ℕ_{0}

darstellbar sind.

(Tatsächlich gibt es eine solche für alle relativ prime

[A, B]

die ich finden konnte)

[A, B] : s

[2, 3]:1
[2, 5]:3
[3, 5]:7
[2, 7]:5
[3, 7]:11
[5, 7]:23
[5, 11]:39
[7, 11]:59
[11, 13]:119
[11, 19]:179
[13, 19]:215
[2, 31]:29
[3, 37]:71
[5, 29]:111
[7, 31]:179
[11, 23]:219
[17, 19]:287
[21, 29]:559

Die zugrunde liegende Formel lautet

s = A \cdot B - (A + B)

Ist das schon bekannt oder betrete ich hier Neuland?

Gruß
Sukomaki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

08:56 Uhr, 14.09.2023

Hallo,

also,
> [2, 7]:5

kann nicht sein, da

4 = 2 \cdot 2 + 0 \cdot 7

ebenfalls darstellbar ist.

Mfg Michael

EDIT: Jedenfalls interpretiere ich
> Sei s die Schranke,[...]
> ab der alle Zahlen als Linearkombination von A und B mit Koeffizienten aus ℕ0 darstellbar sind.

so, dass

s

die KLEINSTE untere Schranke sei und

ℕ_{0}

eben auch Null als Koeffizienten erlaubt.

HAL9000

09:08 Uhr, 14.09.2023

Das ist ein bekannter Fakt, und lässt sich auch relativ einfach nachweisen:

Für gegebenes

n

betrachten wir für die Diophantische Gleichung

n = A u + B v

zunächst die zugeordnete Kongruenzgleichung

A u + B v \equiv n mod A B

. Die ist eindeutig lösbar hinsichtlich der Restklassen

u mod B

sowie

v mod A

.

Betrachten wir nun die kleinsten nichtnegativen Repräsentanten

u_{0}, v_{0}

jener Lösung, dann wissen wir wegen

u_{0} \leq B - 1

sowie

v_{0} \leq A - 1

für die Zahl

n_{0} = A u_{0} + B v_{0}

auf jeden Fall

n_{0} \leq A (B - 1) + B (A - 1) = 2 A B - A - B

und zudem

n_{0} \equiv n mod A B

.

Die Annahme

n_{0} > n

ist dann gleichbedeutend mit

n_{0} \geq n + A B

, folglich

n \leq A B - A - B = : s

. Das bedeutet:

1) Für

n > s

ist

n_{0} \leq n

, wegen

n_{0} \equiv n mod A B

können wir nun beispielsweise Lösung

u = u_{0}, v = v_{0} + \frac{n - n_{0}}{B}

unserer Diophantischen Lösung angeben.

2) Für

n = s

klappt das hingegen nicht, denn man kann sich leicht davon überzeugen, dass in diesem Fall

u_{0} = B - 1

und

v_{0} = A - 1

ist, mit Ergebnis

n_{0} = A u_{0} + B u_{0} = 2 A B - A - B > s

.

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

Es gab mal eine IMO-Aufgabe (Nr. 3 von 1983), die ging einen kleinen Schritt weiter:

Für paarweise teilerfremde positive Zahlen

A, B, C

ist nachzuweisen, dass die Zahl

s = 2 A B C - A B - A C - B C

die größte ganze Zahl ist, die sich NICHT in der Form

A B u + A C v + B C w

mit nichtnegativen ganzen Zahlen

u, v, w

dastellen lässt.

HAL9000

09:13 Uhr, 14.09.2023

@michaL

Hab deinen Beitrag erst jetzt gelesen:

Die klarere Formulierung wäre gewesen, dass

s = A B - A - B

die größte ganze Zahl ist, die sich nicht so darstellen lässt (vgl. IMO-Aufgabe). Dass es kleinere Zahlen gibt, die dennoch so darstellbar sind, bleibt davon unbenommen.

EDIT: Die fehlende Reaktion von Sukomaki deute ich mal als Enttäuschung, kein Neuland betreten zu haben. ;-)

Sukomaki aktiv_icon

15:11 Uhr, 14.09.2023

> Die fehlende Reaktion von Sukomaki deute ich mal als Enttäuschung, kein Neuland betreten zu haben. ;-)

Sorry, ich bin nun mal nicht der Schnellste im Verarbeiten und Antworten.

Das solltest Du inzwischen bemerkt haben.

Das hat mit Enttäuschung nichts zu tun.

Im Gegenteil : es freut mich, dass jemand denselben Gedankengang hatte.

Und in diesem Zusammenhang : Ich habe mal wieder zu kompliziert gedacht.

Auf Deinen Post komme ich in Bälde zurück.

(Ich hatte heute morgen einiges zu tun)

Sukomaki aktiv_icon

15:56 Uhr, 14.09.2023

> mit Ergebnis

n_{0} = A u_{0} + B u_{0}

Typo?

\to n_{0} = A u_{0} + B v_{0}

zu 1)

Probe, dass die Lösung richtig ist :

A u_{0} + B (v_{0} + \frac{n - n_{0}}{B}) = n_{0} + n - n_{0} = n

zu 2)

n_{0} = 2 A B - A - B, n = A B - A - B \Rightarrow v = v_{0} + \frac{n - n_{0}}{B} = A - 1 - \frac{A B}{B} = - 1

,

was nicht zulässig ist.

Daraus folgt, dass für

n = s

keine Lösung existiert.

Und weil die Lösung eindeutig ist, kommt auch kein anderes

u

in Frage.

Ich denke, ich habe es soweit verstanden :-)

HAL9000

16:17 Uhr, 14.09.2023

Ja klar, Copy+Paste-Typo. Immer Au und Bv, in allen Indexvarianten. ;-)

In deiner Argumentation zu 2) gibt es einen Schönheitsfehler: Du darfst da nicht mit der speziellen Lösung von 1) argumentieren - es könnte jemand kommen und sagen: "OK, mit der speziellen Lösungsdarstellung in 1) klappt es hier nicht, aber vielleicht ja mit einer anderen?"

Richtig ist, dass im Fall

n < n_{0}

man dann stets wegen

u \equiv u_{0} mod B

sowie

v \equiv v_{0} mod A

entweder

u \leq u_{0} - B \leq - 1

oder aber

v \leq v_{0} - A \leq - 1

wählen müsste, was in beiden Fällen der geforderten Nichtnegativität der Lösung widerspricht.

Und noch was:

n < n_{0}

ist was anderes als

n \leq s

. Das Beispiel von michaL zeigt klar, das es auch

n < s

mit

n = n_{0}

geben kann.

Sukomaki aktiv_icon

16:34 Uhr, 14.09.2023

Ist an meinen Überlegungen etwas auszusetzen?

Schon interessant, dass für

n > A B - A - B

sämtliche Zahlen darstellbar sind.

Ach ja genau :

Wie kommt die Tatsache ins Spiel, dass

A

und

B

relativ prim sein müssen?

Das heißt, wenn ich zum Beispiel

A = 10

und

B = 15

nehme :

Warum kann ich nur

n

(außer

5

) mit

n = g \cdot k

mit

g = g g T (10, 15) = 5

als Linearkombination darstellen?

Oder wenn ich zum Beispiel

A = 2

und

B = 4

nehme :

Warum kann ich nur

n

mit

n = g \cdot k

mit

g = g g T (2, 4) = 2

als Linearkombination darstellen?

Eigentlich trivial, aber ich hätte es gerne korrekt formuliert.

HAL9000

16:37 Uhr, 14.09.2023

> Die ist eindeutig lösbar hinsichtlich der Restklassen

u mod B

sowie

v mod A

.

Bei nicht teilerfremden

A, B

kannst du diese Aussage in die Tonne treten. ;-)

Angesichts dessen, dass du laut Überschrift ja das Lemma von Bezout zu kennen scheinst, stellst du reichlich seltsame Fragen in diesem deinen letzten Beitrag... Alle Linearkombinationen

A u + B v

sind trivialerweise durch

g = ggT (A, B)

teilbar, was im Fall

g > 1

...

Sukomaki aktiv_icon

16:45 Uhr, 14.09.2023

Mir ging es nur darum, zu sagen, dass

n

höchstens gleich

g g T (A, B) \cdot k

mit

k \in ℕ_{0}

sein kann. :-D)

Und für relativ prime Zahlen

A

und

B

ist

g g T (A, B)

eben Eins.

Ist doch richtig, oder?

Sukomaki aktiv_icon

18:11 Uhr, 14.09.2023

Habe ich das Argument wie folgt richtig verstanden :

Wenn

n < n_{0}

und

n_{0} = A u_{0} + B v_{0}

, dann muss ich etwas von

n_{0}

abziehen.

Das bedeutet aber nichts anderes als, dass ich von

u_{0}

ein

B

, bzw. von

v_{0}

ein

A

abziehen müsste (weil die potentielle Lösung eindeutig modulo B, bzw. modulo A ist). Das widerspricht der Nichtnegativität. Ergo existiert keine Lösung.

Es gibt aber auch

n = n_{0}

kleiner s, die eine gültige Lösung haben. (wie in dem Beispiel von michaL)

HAL9000

18:42 Uhr, 14.09.2023

Wir wissen nur sicher: Für

n > s

klappt es, für

n = s

nicht.

Für

0 \leq n < s

hingegen sieht man einen Flickenteppich: Für manche klappt die Darstellung, für andere wieder nicht. Nimm z.B.

A = 3, B = 7

3 = 1 \cdot 3 + 0 \cdot 7

6 = 2 \cdot 3 + 0 \cdot 7

7 = 0 \cdot 3 + 1 \cdot 7

9 = 3 \cdot 3 + 0 \cdot 7

10 = 1 \cdot 3 + 1 \cdot 7

Für

n = 1, 2, 4, 5, 8, 11

klappt es nicht. Für

n \geq 12

klappt es dann aber immer.

Sukomaki aktiv_icon

20:42 Uhr, 14.09.2023

Der chaotische, nichttriviale Bereich macht die Angelegenheit doch erst interessant.

Ich schaue mir diesen Flickenteppich mal für größere

A

und

B

an. Vielleicht erkenne ich ein Muster darin.

Sukomaki aktiv_icon

16:48 Uhr, 15.09.2023

Also,

[2, p]

ist einfach :

\frac{1}{3} (4^{\frac{p - 1}{2}} - 1)

in Binärdarstellung steht für die Darstellbarkeit von

n

.

Das läuft über einen Links-Shift (also Multiplikation mit

4

) mit anschließender Addition von Eins :

[2, 3] : [1, 0] 1
[2, 5] : [1, 0, 1, 0] 5
[2, 7] : [1, 0, 1, 0, 1, 0] 21
[2, 9] : [1, 0, 1, 0, 1, 0, 1, 0] 85
[2, 11] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 341
[2, 13] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 1365
[2, 15] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 5461
[2, 17] : [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 21845

Daraus folgt die Rekursion

a_{n} = 4 a_{n - 1} + 1

und daraus wiederum die obige Formel.

Jetzt bin ich gerade bei

[3, p]

.

Mal schauen was draus wird :-)

Nur so hier die ersten

B

zu dem

A = 3

:

[3, 4] : [100 110] 25
[3, 5] : [100 101 10] 105
[3, 7] : [100 100 110 110] 1737
[3, 8] : [100 100 101 101 10] 6985
[3, 10] : [100 100 100 110 110 110] 112201
[3, 11] : [100 100 100 101 101 101 10] 449097
[3, 13] : [100 100 100 100 110 110 110 110] 7189065
[3, 14] : [100 100 100 100 101 101 101 101 10] 28758601

Es kristallisieren sich erste Muster heraus :-)

HAL9000

17:20 Uhr, 15.09.2023

Ich kann dir nicht folgen: Wovon redest du überhaupt? Hast du dich im Thread geirrt?

Falls doch kein Irrtum: Was zeichnet 341 aus hinsichtlich der Darstellbarkeit von Zahlen in der Form

2 A + 11 B

???

EDIT: Jetzt kapiere ich erst - du willst (warum auch immer) die GESAMTMENGE aller darstellbaren Zahlen in einer Zahl kodieren über deren Binärdarstellung.

Allerdings hörst du einfach bei Bitposition

n = A B - A - B

auf, die Binärzahl zu bilden, aus verständlichen Gründen: Denn alle Bits ab Position

n = A B - A - B + 1

müssten ja 1 sein, womit immer unendlich herauskommt.

Wäre es da nicht logisch stringenter, stattdessen die darstellbaren Zahlen mit Binärbit 0 zu kodieren, und die nicht darstellbaren Zahlen mit Bit 1 ? Dann braucht es diese künstliche Stoppbedingung nicht.

Sukomaki aktiv_icon

17:51 Uhr, 15.09.2023

A = 2

und

B = 11

n = 0

ist darstellbar.

n = 1

ist nicht darstellbar.

n = 2

ist darstellbar.

n = 3

ist nicht darstellbar.

n = 4

ist darstellbar.

n = 5

ist nicht darstellbar.

n = 6

ist darstellbar.

n = 7

ist nicht darstellbar.

n = 8

ist darstellbar.

n = 9

ist nicht darstellbar.

Ich ordne "nicht darstellbar" die Null und "darstellbar" die Eins zu.

Das gibt mir die Folge

(1, 0, 1, 0, 1, 0, 1, 0, 1, 0)

.

Im Binärsystem interpretiert ist das 341.

Das heißt es geht nicht um die Darstellbarkeit von 341.

Sondern die 341 enthält die Information über die Darstellbarkeit von

n \in {0, 1, 2, \dots, s - 1, s}

So weit nachvollziehbar?

Dann schalte ich jetzt einen Gang hoch :

Sei

A = 3

und

B = p

Falls

p m o d 3 = 1

, dann

f := (3 \cdot 8^{k} + 1) \cdot (\frac{8^{k} - 1}{7})

und

c = f (\frac{p - 1}{3})

Falls

p m o d 3 = 2

, dann

g := 8^{2 k} + (5 \cdot 8^{k} + 1) \cdot (\frac{8^{k} - 1}{7})

und

c = g (\frac{p - 2}{3})

Das

c

- im Binärsystem interpretiert - verrät, welche

n \in {0, 1, 2, \dots, s - 1, s}

darstellbar sind.

Sukomaki aktiv_icon

17:55 Uhr, 15.09.2023

> Wäre es da nicht logisch stringenter, stattdessen die darstellbaren Zahlen mit Binärbit 0 zu
> kodieren, und die nicht darstellbaren Zahlen mit Bit 1 ? Dann braucht es diese künstliche
> Stoppbedingung nicht.

Stimmt. Das habe ich nicht bedacht.

Ich probiere das mal aus, was sich dadurch ändert in den Formeln.

Sukomaki aktiv_icon

01:13 Uhr, 16.09.2023

A = 2

:

Gemäß Deiner inversen Zuordnung wird aus

\frac{1}{3} (4^{\frac{p - 1}{2}} - 1)

das nur unwesentlich kompliziertere

\frac{2}{3} (4^{\frac{p - 1}{2}} - 1)

Das zuständige Bit, das die Darstellbarkeit von

n

codiert, lässt sich beschreiben als

b_{n} = (c & (1 < < n)) > > n)

wobei "<<" und ">>" die Shift-Operationen sind.

Aber das weißt Du schon.

Die Formeln für

A = 3

gibt es später.

Sukomaki aktiv_icon

02:52 Uhr, 16.09.2023

Nun zu

A = 3

und

B = p

:

Wenn

p m o d 3 = 1

ist, ist

f = (4 \cdot 8^{k} + 6) \cdot (\frac{8^{k} - 1}{7})

und

c = f (\frac{p - 1}{3})

Wenn

p m o d 3 = 2

ist, ist

g = 2 \cdot 8^{2 k} + (2 \cdot 8^{k} + 6) \cdot (\frac{8^{k} - 1}{7})

und

c = g (\frac{p - 2}{3})

Durch Zerlegung von

c

lassen sich sämtliche

n

hinsichtlich Darstellbarkeit überprüfen.

Sukomaki aktiv_icon

18:55 Uhr, 16.09.2023

Wenn ich mich nicht täusche habe ich ein nettes Zwischenergebnis :

Gegeben ein

A

und ein dazu relativ primes

B

f := \frac{1}{2^{A} - 1} \cdot \sum_{j = 1}^{A - 1} {(2^{B m o d A} \cdot 2^{A \cdot k})}^{j} - \frac{2^{A} - 2}{2^{A} - 1}

mit

k = \frac{B - (B m o d A)}{A} = ⌊ \frac{B}{A} ⌋

Es ist der Funktion nicht sofort anzusehen, aber sie ist tatsächlich symmetrisch.

Und noch einfacher ausgedrückt ist

f := \frac{2^{A B} - 2^{A + B} + 2^{A} + 2^{B} - 2}{(2^{A} - 1) (2^{B} - 1)}

EDIT : Oder nach Belieben auch

f := \frac{2^{A B} - 1}{(2^{A} - 1) (2^{B} - 1)} - 1

In dieser Form ist die Symmetrie gut einzublicken :-)

Und jetzt bist Du dran :-)

Sukomaki

Sukomaki aktiv_icon

14:50 Uhr, 18.09.2023

@HAL9000

Ist es okay für Dich, wenn ich den Thread hiermit schließe?

Ach, ich mache es einfach.

Danke für den Tipp mit der inversen Zuordnung.

Er har mir sozusagen geholfen, mich zu ordnen :-)

Für eine verwandte Frage mache ich einen neuen Thread auf.

Sukomaki

1575818

1575696

	Status: nicht eingeloggt	Noch nicht registriert?