Elementare Zahlentheorie WS 2003/04

Teil 1: Referat "Pythagoreische Zahlentripel"

Es stand noch ein Beweis von der letzten Veranstaltung aus:

Lemma:

Es seien [a, b, c] aus P_N0, [a´, b´, c´,] aus P_Z und, wie schon in der letzten Veranstaltung, die Matrizen a, B = m₁a, C = m₂a, und D = m₁m₂a gegeben (siehe Protokoll vom 13.01.2004). Es gilt:

a.) Aus [a´, b´, c´] = [a, b, c] * a folgt: a´ > a, b´ > b, c´ > c.

Beweis: a´ = a + 2b + 2c > a. (Rest analog.)

b.) Aus [a´, b´, c´] = [a, b, c] * B folgt: a´ > a, b´ > b, c´ > c.

Beweis: a´ = -a + 2b + 2c > -a + 2b + 2a = a + 2b > a,

b´ > b analog,

c´ = -2a + 2b +2c + c > c.

c.) Aus [a´, b´, c´] = [a, b, c] * C folgt: a´ > a, b´ > b, c´ > c.

Beweis: Analog zu b.).

d.) Aus [a´, b´, c´] = [a, b, c] * D folgt: |a´| < a, |b´| < b, 0 < c´ < c.

Beweis: 1. Fall: a´ > 0: |a´| = -2 - 2b + 2c < -a - 2b + 2a + 2b = a.

2. Fall: a´< 0: |a´| = a + 2b - 2c < a + 2b - 2c < a + 2b - 2b = a.

Analog: |b´| < b.

c´ = -2a - 2b + 3c = -2(a + b) + 3c < -2c + 3c = c.

c´ = 3c - (2a + 2b) > 3c - (2a + 2b) = 3c - ((2a + 2b)²)^1/2 > 3c - ((2a + 2b)² + (2a - 2b)²)^1/2 = 3c - (4a² + 8ab + 4b² + 4a² - 8ab + 4b²)^1/2 = 3c - (8(a² + b²))^1/2 > 3c - (9c²)^1/2 = 0.

e.) Aus [a´, b´, c´] = [a, b, c] * D und [a, b, c] ist nicht aus der Menge J := {[1, 0, 1], [0, 1, 1]} folgt: a´ < 0 oder b´ < 0.

Beweis: Angenommen, a´ und b´ wären größer oder gleich 0:

[a´´, b´´, c´´] := [a´, b´, c´] * D = [a, b, c] * D² = [a, b, c].

Aus d.) folgt: |a| = |a´´| < a´ < a. Dann folgt: [a´, b´, c´] = [a, b, c], was im Widerspruch zu "[a´, b´, c´] ist nicht aus J" liegt.

Es ergibt sich die Folgerung: Die Operation *D "verkleinert jedes [a, b, c] aus P_N0 (bis auf das Vorzeichen).

Es ergibt sich ein Reduktionsverfahren: Gegeben sei [a₀, b₀, c₀] aus P_Z.

[a₁, b₁, c₁] = [a₀, b₀, c₀] * X₀, wobei X_o aus <m₁, m₂, m₃> =: M ist, sodass [a₁, b₁, c₁] aus P_N0 ist.

Dieser Vorgang wird iteriert: T := [a_k, b_k, c_k] * X_k, X_k ist aus M mit T aus der Menge {[1, 0, 1], [0, 1, 1]} = J.

[1, 0, 1] = T * Y, wobei Y aus <P> ist (P ist Permutationsmatrix). [1, 0, 1] = [a₀, b₀, c₀] * (X₀DX₁D...X_kY)

[a₀, b₀, c₀] = [1, 0, 1] * (YX_k...DX₀).

Es ergibt sich das Lemma:

a^-1 = Dm₁m₂, B^-1 = Dm₂, C^-1 = Dm₁, D^-1 = D. Beweis: Selbst.

Also sind die X_i aus <m₁, m₂>. Daraus ergibt sich: P_Z ist transitiv. (Jedes Tripel lässt sich auf [1, 0, 1] zurückführen.)

Beispiel: Gegeben sei [-51, -140, 149] aus PZ.

[51, 140, 149] = [-51, -140, 149] * m₁m₂,

[51, 140, 149] * D = [-33, 56, 65],

[33, 56, 65] = [-33, 56, 65] * m₁,

[33, 56, 65] * D = [-15, 8, 17],

[15, 8, 17] = [-15, 8, 17] * m1,

[15, 8, 17] * D = [3, -4, 5],

[3, 4, 5] = [3, -4, 5] * m₂,

[3, -4, 5] * D = [-1, 0, 1],

[1, 0, 1] = [-1, 0, 1] * m₁.

Also ist  [1, 0, 1] = [-51, -140, 149] * (m₁m₂Dm₁...Dm₁), also  [-51, -140, 149] = [1, 0, 1] * (CBCCm₁m₂).

Teil 2 der Veranstaltung war die Fortsetzung von § 7: Der Euklidische Algorithmus (Konvergenten).

0 < z aus IR sei gegeben. Dann sei z : 1 = a : b = r_-1 : r₀ := |_z_| + r.

Der EA ergibt: r_-1 - Q₀r₀  = r₁ (Q₀ ist aus IN und 0 < r₁ <1).

Danach ist: r₀ - Q₁r₁ = r₂ und so weiter.

(Parallel läuft der XEA mit den Startwerten x_-1 = 1, x₀ = 0, Y_-1 = 0 und Y₀ = 1 wie gehabt aus LAI. Ziel ist die Darstellung r_i = x_ia + y_ib.)

z : 1 = a / b = Q₀ + r₁ / r₀ = Q₀ + 1 / (r₀ / r₁) = Q₀ + 1 / (Q₁ + (r₂ / r₁)) = Q₁ + 1 / (Q₁ + (1 / Q₂ + (1/ (r₂ / r₃)))) usw.

[Q₀, Q₁, Q₂] =: A₂, [Q₀, ..., Q_k] =: A_k.

A_k := -y_k+1 / x_k+1. Unsere Vermutung ist: A_k konvergiert gegen a / b (für k gegen unendlich). Für die rationale Zahl z bricht der EA ab mit r_n+1 = 0. A_n ist a / b.

Erinnerung an Satz 3 aus der Veranstaltung vom 12.11.2003: Die Determinante der Matrix

xi	yi
xi+1	yi+1

ist gleich (-1)ⁱ⁺¹. Die A_k = -y_k+1 / x_k+1 sind gekürzt.

Satz 6 vom 16.12.2003: x_k < 0 für ungerade k > 1, x_k < 0 für gerade k > 2. |x_k+1| > |x_k| für k > 2; |x_k| > f_k [=f_k-2 + f_k-1]. Ähnlich ist es bei den y_j.

Satz 7: A_k+1 - A_k = (-1)^k+1 / x_k+2x_k+1.

Beweis: -y_k+2 / x_k+2 + y_k+1 / x_k+1 = (-x_k+1y_k+2 + y_k+1x_k+2) / x_k+2x_k+1 = (nach Satz 3) -1 / x_k+2x_k+1 · det H = (-1)^k+1 / x_k+2x_k+1, wobei H :=

xi+1	yi+1
xi+2	yi+2

A₀ = -y₁ / x₁ = Q₀ (siehe EA), A₁ = -y₂ / x₂ = -(1 + Q₀Q₁) / -Q₁ = 1 / Q₁ + Q₀ > Q₀ = A₀.

Zur vorangehenden Stunde (13.01.04),
zur nächsten Stunde (16.01.04),
zur Protokollübersicht.