La multiplication est commutative !

La multiplication des entiers est commutative : vous êtes d’accord ?

Pour le démontrer proprement on utilise les axiomes de Peano (dont la récurrence).

Je considère  maintenant  l’algorithme « ordinaire » de multiplication pour des chiffres écrits en base 2.

Question : Pourquoi cet algorithme est-il commutatif?

Voici par exemple la multiplication \(55\times 9=495\) écrite en base 2:
\[ \begin{array}{ccccccccc}
&&&1&1&0&1&1&1\\ &&&&& 1 & 0 & 0&1 \\ \hline &&&1&1&0&1&1&1 \\ 1&1&0&1&1&1&&& \\ \hline  1&1&1&1&0&1&1&1&1 \end{array} \]
Et nous pouvons ausi l’écrire
\[ \begin{array}{ccccccccc}
 &&&&&1&0&0&1 \\ &&&1&1&0&1&1&1 \\ \hline &&&&&1&0&0&1 \\&&&&1&0&0&1& \\&&&1&0&0&1&& \\&1&0&0&1&&&& \\1&0&0&1&&&&& \\ \hline  1&1&1&1&0&1&1&1&1 \end{array} \]
Si on regarde les deux déroulements de l’algorithme il n’est pas du tout évident que les deux résultats soient identiques !

Regardons les sommes (en décimal) de chacune des 9 colonnes sans faire la retenue. On trouve le même résultat dans les deux cas :
\[ \begin{array}{ccccccccc} 1&1&0&2&2&1&1&1&1 \end{array} \]
et c’est cela qui garantit le même résultat dans les deux cas ! Les sommes par colonnes sont identiques dans les deux cas. Et ceci n’est pas dû à la base 2 employée dans mon example. C’est vrai dans n’importe quelle base de numération (vous pouvez vérifier).

Voici une démonstration :
On écrit la multiplication :
\[\sum_{i\geq 0} a_i2^i \times \sum _{j \geq 0} b_j2^j \]
\[=\sum_{k\geq 0} \left(\sum_{i+j= k} a_ib_j\right) 2^k\]
et il est bien clair que le terme entre parenthèses ne dépend pas du tout de l’ordre dans lequel on développe l’algorithme car la multiplication des chiffres est commutative \(a_ib_j=b_ja_i\). C’est pour cela que l’algorithme usuel est bien commutatif !

C’est aussi d’une certaine façon la justifiction de la multiplication « égyptienne ».
Je vais m’intéresser maintenant à l’aspect « binaire » de la multiplication.
On applique la règle \(1+1=0\). L’algorithme devient
\[ \begin{array}{ccccccccc}
&&&1&1&0&1&1&1\\ &&&&& 1 & 0 & 0&1 \\ \hline &&&1&1&0&1&1&1 \\ 1&1&0&1&1&1&&& \\ \hline  1&1&0&0&0&1&1&1&1 \end{array} \]
Et nous pouvons ausi l’écrire
\[ \begin{array}{ccccccccc}
 &&&&&1&0&0&1 \\ &&&1&1&0&1&1&1 \\ \hline &&&&&1&0&0&1 \\&&&&1&0&0&1& \\&&&1&0&0&1&& \\&1&0&0&1&&&& \\1&0&0&1&&&&& \\ \hline  1&1&0&0&0&1&1&1&1 \end{array} \]
Sans surprise cela reste commutatif. En effet l’algorithme traduit maintenant la multiplication suivante dans l’algèbre \(F_2[X]\) :
\[(X^5+X^4+X^2+X+1)(X^3+1)= X^8+X^7+X^3+X^2+X+1.\]
Je vais expliquer mon intérêt pour ces considérations dans mon prochain article.

Laisser un commentaire