Un petit exercice sur les multiples de 3 en base 2

A l’occasion, je vous raconterai des choses sur les caractères de divisibilité. En attendant, je vous propose de vérifier que les nombres naturels dont l’écriture en base 2 est de la forme

10\underbrace{1\cdots1}_{n_1}00\underbrace{1\cdots1}_{n_2}0\cdots0\underbrace{1\cdots1}_{n_p}01

dans laquelle p, n_1,...,n_p \geq 0, sont tous multiples de 3.

2 réflexions sur “Un petit exercice sur les multiples de 3 en base 2

  1. Je propose une solution élémentaire (en me doutant bien qu’une jolie solution avec des automates nous attend).
    Les nombres 2^{k+1}+2^k sont (c’est immédiat, avec ou sans congruences) divisibles par 3. On peut donc « boucher les trous » et on est ramené à montrer que les nombres qui s’écrivent \underbrace{10111\dots 101}_N en base 2 sont divisibles par 3. Or ce nombre est 2^N-1-2^{N-2}-2, sa divisibilité par 3 est claire.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s