Zehnersystem/Schriftliches Multiplizieren/Einstelliger Faktor/Korrekt/Fakt/Beweis

Beweis

Die linke Faktor sei

${}m=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,$

und der rechte Faktor sei ${}b_{0}$, wir haben also die schriftliche Multiplikation der Form

$a_{k}\ldots a_{2}a_{1}a_{0}\,\,\cdot \,\,b_{0}$

im Sinne von Fakt durchzuführen. Das Ergebnis ist die Zahl ${}c_{k+1}c_{k}\ldots c_{2}c_{1}c_{0}$. Wir müssen zeigen, dass dies das wahre Produkt ist. Dies zeigen wir durch das folgende Invarianzprinzip des Multiplikationsalgorithmus, dass nämlich nach dem ${}i$-ten Schritt (${}i=-1,0,1,\ldots ,k+1$) der Ausdruck

$P_{i}={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}\cdot b_{0}+d_{i+1}10^{i+1}+c_{i}10^{i}+\cdots +c_{1}10+c_{0}\,$

konstant ist. Wegen

${}m\cdot b_{0}=P_{-1}\,$

und da für

${}i>k\,$

das Produkt vollständig abgebaut ist, folgt daraus, dass die ${}c_{i}$ die Ziffern des Produktes sind. Die Konstanz ergibt sich unter Verwendung von

${}a_{i}b_{0}+d_{i}=d_{i+1}\cdot 10+c_{i}\,$

aus (das beschreibt den ${}i$-ten Rechenschritt)

${}{\begin{aligned}P_{i-1}&={\left(a_{k}10^{k}+\cdots +a_{i}10^{i}\right)}\cdot b_{0}+d_{i}10^{i}+c_{i-1}10^{i-1}+\cdots +c_{1}10+c_{0}\\&={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}\cdot b_{0}+a_{i}b_{0}10^{i}+d_{i}10^{i}+c_{i-1}10^{i-1}+\cdots +c_{1}10+c_{0}\\&={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}\cdot b_{0}+{\left(a_{i}b_{0}+d_{i}\right)}10^{i}+c_{i-1}10^{i-1}+\cdots +c_{1}10+c_{0}\\&={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}\cdot b_{0}+{\left(d_{i+1}10+c_{i}\right)}10^{i}+c_{i-1}10^{i-1}+\cdots +c_{1}10+c_{0}\\&={\left(a_{k}10^{k}+\cdots +a_{i+1}10^{i+1}\right)}\cdot b_{0}+d_{i+1}10^{i+1}+c_{i}10^{i}+c_{i-1}10^{i-1}+\cdots +c_{1}10+c_{0}\\&=P_{i}.\end{aligned}}$

Zur bewiesenen Aussage