Bonjour à tous !

Je discutais hier avec mon frère sur les opérations mathématiques en binaire, notamment de l'addition (http://fr.wikipedia.org/wiki/Additionneur). De cela, je me suis interrogé sur quelques propriétés sur "la position des chiffres" lors de ces opérations, et plus particulièrement sur "le nombre de chiffres" lors d'opération.
Ainsi, j'ai trouvé intuitivement :

Citation

Une addition de deux nombres (de même base), composés de n chiffres, a pour résultats un nombre composé de n + 1 chiffres au maximum.

Citation

Une multiplication de deux nombres (de même base), composés de n chiffres, a pour résultat un nombre composé de 2n chiffres au maximum.

Après discussion avec mon frère, celui-ci m'a fait remarqué que c'était, de manière plus générale :

Citation

Une addition de deux nombres (de même base), composés de n et m chiffres, a pour résultats un nombre composé de max(n;m) + 1 chiffres au maximum.

Citation

Une multiplication de deux nombres (de même base), composés de n et m chiffres, a pour résultat un nombre composé de n + m chiffres au maximum.

Nous avons ensuite tenté de démontrer cela. Intuitivement, nous pouvons constater que quelque soit la base utilisée, la somme de deux nombres de n et m chiffres, les plus grand possibles, avait pour résultat un nombre qui respectait les hypothèses que nous avions.
Ainsi, par exemple :
Soit deux nombres en base 10, respectivement de 5 et 6 chiffres et les plus grands possible, c'est-à-dire 99999₁₀ et 999999₁₀ :

<math>\(99999_{10} + 999999_{10} = 1099998_{10}\)</math>

De même en base 2 et avec d'autres valeurs pour n et m :

<math>\(1111111_{2} + 111111_{2} = 10111110_{2}\)</math>

Etc.

De la même manière, avec la multiplication, en base 16 et avec n = 4 et m = 3 :

<math>\(FFFF_{16} \times FFF_{16} = FFEF001_{16}\)</math>
Et ainsi de suite…

Je suis conscient que pour démontrer cela, il faudrait un système de notation adapté. Cependant, malgré quelques recherches sur internet, je n'ai absolument rien trouvé.
Pourriez-vous m'aider à démontrer cela ?
Merci de votre aide !

Citation : smilz

<math>\(99999_{10} + 999999_{10} = 1099998_{10}\)</math>

C'est l'idée de la preuve.

Soit q une base. Soient a et b des nombres à n et m chiffres, avec par exemple m ≤ n : <math>\(a = \sum_{k=0}^{n-1} a_k q^k, b = \sum_{k=0}^{m-1} b_k q^k\)</math> où <math>\(a_k, b_k \in [\![0,q-1]\!]\)</math>.
Alors <math>\(a \leq \sum_{k=0}^{n-1} (q-1) q^k, b \leq \sum_{k=0}^{m-1} (q-1) q^k \leq \sum_{k=0}^{n-1} (q-1) q^k\)</math>.
Donc <math>\(a+b \leq 2 \sum_{k=0}^{n-1} (q-1) q^k = 2(q-1) \sum_{k=0}^{n-1} q^k\)</math>.
Or <math>\(\sum_{k=0}^{n-1} q^k\)</math> est la somme des n premiers termes d'une suite géométrique, on sait donc la calculer, elle vaut <math>\(\frac{q^n-1}{q-1}\)</math>.
Donc <math>\(a+b\leq 2q^n-2q\)</math>. Pour montrer que ce nombre a au maximum n+1 chiffres, il suffit de prouver qu'il est <math>\(<q^{n+1}\)</math>.
Or q ≥ 2 donc <math>\(2q^n - 2 < 2q^n \leq q^{n+1}\)</math> : c'est gagné.

C'est le même genre de preuve pour la multiplication mais j'ai la flemme de le faire

Salut,

Je pense que plutôt que de considérer les nombres de la forme 9999 avec des inégalités larges, il est plus simple de regarder les puissances de la base avec des inégalités strictes.

Pour les multiplications Si <math>\(a\)</math> et <math>\(b\)</math> sont des nombres à <math>\(n\)</math> et <math>\(m\)</math> chiffres alors :


et ceci est vrai quelque soit la base ! (10 désigne la base, c'est-à-dire 10 est égal à deux en base deux, à trois en base trois,... à dix en base dix...). On a donc :


et <math>\(ab\)</math> a donc au plus <math>\(n+m\)</math> chiffres.

Pour les additions.

Ce nombre possède autant de chiffres que <math>\(10^{\max(n,m)}\)</math> c'est-à-dire <math>\(\max(n,m)+1\)</math> (<math>\(\max(n,m)\)</math> zéros et un 1)?

Ah oui en effet, ce n'est vraiment pas compliqué en fait .

Par contre, krosian, j'ai du mal à suivre ton raisonnement, pourrais-tu (si tu en as le courage, je comprends que ça soit fastidieux), détailler plus en détails ta démonstration ? Je ne comprends pas du tout où tu veux en venir par ta somme. Que représentent a_k et q^k ? En quoi sont-ils liés ?

Merci beaucoup.

<math>\(a = \sum_{k=0}^{n-1} a_k q^k\)</math> où <math>\(a_k \in [\![0,q-1]\!]\)</math> représente la décomposition dans la base q du nombre a.

Un exemple tout simple : si je veux décomposer 453 en base 10, ça va me donner <math>\(453 = 4.10^2+5.10^1+3.10^0\)</math> soit encore <math>\(453 = \sum_{k=0}^{2} a_k 10^k\)</math> avec <math>\(a_0=3, a_1=5, a_2=4\)</math>.

Ah merci, je n'avais pas compris que l'indice après un nombre correspondait au chiffre « associé » à cet indice.
Enfin, je vois ce que je veux dire :).

Merci encore à vous.