#009900

#0000ff

\textcolor{#009900}

\textcolor{#ff0000}

Der Euklidische Algorithmus

\text{Sei a ≥ b    a,b ∈  ℕ}\
\text{k ist Teiler von a und k ist Teiler von  b⇔a = n \cdot k  und  b = m \cdot k       k, n, m ∈ ℕ}  \
\text{Teilen mit Rest: mod(a , b) =  r⇔a = p \cdot b + r       p ∈ ℕ , r ∈  ℕ_0 }  \
\text{⇔a = p\cdot m \cdot k+r      a, k, m, p  ∈  ℕ ,   r ∈ ℕ_0}    \
\text{⇔n \cdot k  = q \cdot m \cdot k+r       k, n, m, p ∈ ℕ ,  r ∈ ℕ_0 }   \
\text{⇔ r  = (n−p \cdot m) k       k, n, m, p, r  ∈  ℕ  }    \
\text{ ⇒ r  = q \cdot  k     mit q=(n −p \cdot m)  , k  ∈  ℕ ,  r ∈ ℕ_0}    \
 \text{⇒ k  ist auch Teiler von r  } \ \space  \

 \textcolor{#ff0000} {Fazit:} \
\text{Sei a ≥ b    a,b ∈  ℕ} \
\text{Ein (größter) gemeinsamer Teiler von a und b ist auch} \
 \text{ein (größter) gemeinsamer Teiler von Rest(a:b) und b} \

 \text{→ siehe  Demo 1 unten}

Ganzzahldivision mit Rest

Werner Knobloch, 2013

$ \mathbf {GGT}$

#ff0000

#7f00ff

a_1 = 474 (slider from 1 to 600, step 1)
b_2 = 277 (slider from 1 to 600, step 1)
a' = Max(a_1, b_2)
A1: a'
b' = Min(a_1, b_2)
B1: b'
C1 = Mod(A1, B1)
B2: C1
A3: B2
A2: B1
C2 = Mod(A2, B2)
B3: C2
C3 = Mod(A3, B3)
B4: C3
A5: B4
A4: B3
C4 = Mod(A4, B4)
B5: C4
C5 = Mod(A5, B5)
B6: C5
A7: B6
A6: B5
C6 = Mod(A6, B6)
B7: C6
C7 = Mod(A7, B7)
B8: C7
A9: B8
A8: B7
C8 = Mod(A8, B8)
B9: C8
C9 = Mod(A9, B9)
B10: C9
A11: B10
A10: B9
C10 = Mod(A10, B10)
B11: C10
C11 = Mod(A11, B11)
B12: C11
A13: B12
A12: B11
C12 = Mod(A12, B12)
B13: C12
C13 = Mod(A13, B13)
B14: C13
A15: B14
A14: B13
C14 = Mod(A14, B14)
B15: C14
C15 = Mod(A15, B15)
B16: C15
A17: B16
A16: B15
C16 = Mod(A16, B16)
B17: C16
C17 = Mod(A17, B17)
B18: C17
A19: B18
A18: B17
C18 = Mod(A18, B18)
B19: C18
C19 = Mod(A19, B19)
B20: C19
A20: B19
C20 = Mod(A20, B20)
Liste1 = RemoveUndefined({C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11, C12, C13, C14, C15, C16, C17, C18, C19, C20})
L = Length(Liste1)
Liste19 = Sequence(If[j ≟ L - 1, Farbe, If[j ≟ L, Farbe2, ""]], j, 1, L)
a = 24 (slider from 1 to 64, step 1)
b = 43 (slider from 1 to 64, step 1)
dd = Max(a, b)
Blau: {0, 0, 255}
BlauDyn: Blau / 255
Gruen: {0, 153, 0}
GruenDyn: Gruen / 255
cd = Min(a, b)
A = (-9.84, -6.63)
B: A + (0, -1)
Einheit = Min(25 / dd, 1)
Start1 = If(cd ≟ a, A, B)
Trenn = 0.1 (slider from 0.1 to 1, step 0.01)
t0 = Segment(A + (0, Trenn), A + (0, (-Trenn)))
Liste2 = RemoveUndefined({A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19, A20})
Liste3 = RemoveUndefined({B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15, B16, B17, B18, B19, B20})
Liste5 = Sequence(GCD[Element[Liste2, j], Element[Liste3, j]], j, 1, L)
k = GCD(a', b')
r = Mod(a', b')
e = GCD(b', r)
j = 1 (slider from -5 to 5, step 1)
Liste7 = Join({{"Algorithmus"}, Sequence["GGT[" + (Element[Liste2, j]) + "," + (Element[Liste3, j]) + "] =" + (Element[Liste5, j]), j, 1, L]})
n: a' / k
m: b' / k
p = Div(a', b')
rtest: ((n - (p * m)) * k)
q: n - (p * m)
ggt = GCD(a, b)
t0' = Translate(t0, (Einheit, 0))
C = Point(t0')
c = Segment(A, C)
Liste10 = Translate({t0, t0', c}, (0, -1))
D: A + ((Einheit * ggt), 0)
E: B + ((Einheit * ggt), 0)
visual = 0.01
d = Segment(A + (0, (2 * Trenn)), A + (0, ((-2) * Trenn)))
f = Segment(B + (0, (2 * Trenn)), B + (0, ((-2) * Trenn)))
g = Segment(B + ((Einheit * ggt), (2 * Trenn)), B + ((Einheit * ggt), ((-2) * Trenn)))
h = Segment(A + ((Einheit * ggt), (2 * Trenn)), A + ((Einheit * ggt), ((-2) * Trenn)))
vielfa = Div(a, ggt)
vielfb = Div(b, ggt)
i = Segment(A, D)
l = Segment(B, E)
A' = Translate(A, (0, -1))
C' = Translate(C, (0, -1))
c' = Segment(A', C')
Quot = Div(Max[a, b], Min[a, b])
Liste14 = Sequence(Segment[A + (j * Min[a, b]), A + (j * Min[a, b])], j, 1, Quot)
Start2 = If(cd ≟ a, B, A)
F: Start1 + ((Einheit * dd), 0)
rest = Mod(dd, cd)
G: Start1 + (((Einheit * Quot) * cd), 0)
Liste12 = Sequence(Translate[{h, D, i}, (((Einheit * j) * ggt), 0)], j, 1, vielfa - 1)
Liste13 = Sequence(Translate[{g, E, l}, (((Einheit * j) * ggt), 0)], j, 1, vielfb - 1)
Liste11 = Sequence(A + ((Einheit * j) * (1, 0)), j, 1, a)
Liste9 = Sequence(B + ((Einheit * j) * (1, 0)), j, 1, b)
Liste18 = Sequence(Segment[Start1 + (((Einheit * j) * cd), (4 * Trenn)), Start1 + (((Einheit * j) * cd), ((-4) * Trenn))], j, 1, Quot)
b_1 = Segment(Start2 + ((Einheit * dd), (4 * Trenn)), Start2 + ((Einheit * dd), ((-4) * Trenn)))
s = Segment(Start1 + (((Einheit * Quot) * cd), 0), Start1 + ((Einheit * dd), 0))
Liste15 = Sequence(Segment[A + (((j * Einheit) * cd), 0.6), A + (((j * Einheit) * cd), (-1.6))], j, 1, Quot)
Liste17 = Sequence({Segment[A + (((Einheit * j) * cd), 0), A + (((Einheit * (j + 1)) * cd), 0)]}, j, 1, Quot - 1)
t = Segment(Start1 + ((Einheit * dd), (4 * Trenn)), Start1 + ((Einheit * dd), ((-4) * Trenn)))
Blautext: "\textcolor{" + (LaTeX[ColorBlue]) + "}"
Gruentext: "\textcolor{" + (LaTeX[ColorGreen]) + "}"
Liste4 = If(Start1 ≟ A, BlauDyn, GruenDyn)
Erstfarbe = If(cd ≟ a, Gruentext, Blautext)
Zweitfarbe = If(cd ≟ a, Blautext, Gruentext)
Liste6 = Sequence(Element[Liste19, j] + {Element[Liste1, j]}, j, 1, L)
Liste8 = Join({{" "}, Sequence["Mod[" + (Element[Liste2, j]) + "," + (Element[Liste3, j]) + "] =" + (Element[Liste6, j]), j, 1, L]})
Text9 = TableText({Liste7, Liste8}, "_|v")
Liste16 = Sequence({Segment[Start1 + (((Einheit * j) * cd), 0), Start1 + (((Einheit * (j + 1)) * cd), 0)]}, j, 1, Quot - 1)
ZweitfarbeDyn = If(cd ≟ a, BlauDyn, GruenDyn)
Text10: "a = " + (LaTeX[a]) + ""
Text11: "b=" + (LaTeX[b]) + ""
Rest: "Rest = " + rest + ""
H: A + (0, (-2))
I: D + (0, (-2))
c_1 = Segment(H, I)
Text6: "Demo\;2:\\
 GGT[ " + (LaTeX[a']) + "," + (LaTeX[b']) + " ] =\textcolor{#009900}{ " + (LaTeX[k]) + " }\\
r = Rest( " + (LaTeX[a']) + ":" + (LaTeX[b']) + " ) = Mod[ " + (LaTeX[a']) + "," + (LaTeX[b']) + " ] = " + (LaTeX[r]) + "\\
GGT[ " + (LaTeX[b']) + "," + (LaTeX[r]) + " ] =\textcolor{#009900}{ " + (LaTeX[e]) + " } = GGT[ " + (LaTeX[a']) + ", " + (LaTeX[b']) + " ]\\
r = " + (LaTeX[q]) + " \cdot \textcolor{#009900}{" + (LaTeX[k]) + "}"
Text7: " \text{Ein Computer kann diesen Algorithmus in einer Rechenschleife sehr schnell durchführen.}\\
 \text{Die Abbruchbedingung ist } \textcolor{" + (LaTeX[ColorRed]) + "}{“Rest=0”}, \text {dann kann in der } \fgcolor{" + (LaTeX[ColorRed]) + "} {rechten Tabellenspalte}\text{ in der } \textcolor{" + (LaTeX[ColorRed]) + "} {vorletzten}\\
\textcolor{" + (LaTeX[ColorRed]) + "} {Zeile} \text{ der Wert für GGT[a,b] abgelesen werden. Eine Berechnung auf der linken Seite der Tabelle}\\
\text{ist somit unnötig. Es genügt also die Beherrschung der } \textcolor{" + (LaTeX[ColorRed]) + "}{\text{Ganzzahldivision mit Rest}}."
Text8: "Demo \;1: \\
\textcolor{" + (LaTeX[ColorRed]) + "}{GGT} [ " + (LaTeX[Blautext]) + "{" + (LaTeX[a]) + " } , " + (LaTeX[Gruentext]) + "{" + (LaTeX[b]) + " }] =\textcolor{" + (LaTeX[ColorRed]) + "}{ " + (LaTeX[ggt]) + "} \\
Rest(" + (LaTeX[Erstfarbe]) + "{" + (LaTeX[dd]) + "}:" + (LaTeX[Zweitfarbe]) + "{" + (LaTeX[cd]) + "}) =Mod[" + (LaTeX[Erstfarbe]) + "{" + (LaTeX[dd]) + "}," + (LaTeX[Zweitfarbe]) + "{" + (LaTeX[cd]) + "}] = " + (LaTeX[rest]) + "=" + (LaTeX[Div[rest, ggt]]) + "\cdot \textcolor{" + (LaTeX[ColorRed]) + "}{ " + (LaTeX[ggt]) + "}"