Écriture des nombres entiers

2	Écriture des nombres entiers

Pour représenter les entiers (et les nombres de façon plus générale), il va nous falloir diviser. Le premier résultat, élémentaire (puisqu'il est enseigné à l'école élémentaire), concerne la division dite <<euclidienne>> :

Théorème 2.1 Soient a et b deux entiers positifs, b>1. Il existe un unique couple d'entiers (q,r) vérifiant

(1)	a = b.q + r
(2)	0 £ r < b

Preuve : elle est en deux parties. On démontre d'abord l'existence d'un tel couple, puis son unicité.

Existence : si a=0, il suffit de prendre q=0 et r=0. Sinon, 0<a, et considérons l'ensemble d'entiers Q = {n Î IN | b.n £ a}. Q est non vide, puisque 0 en est l'un des éléments. Il est de plus borné, car les relations 1 < b et 0 < a impliquent que a < a.b, qui implique à son tour que tous les éléments n de Q vérifient n<a. Il est donc fini, et admet (d'après les propriétés bien connues de IN ) un plus grand élément, notons-le q. On note r la différence entre a et b.q : par construction, a = b.q+r et 0 £ r. Il reste à montrer que r<b : supposons au contraire que b £ r; alors (par définition de £ ¹ ) il existe un entier i³ 0 tel que r = b + i; on aurait alors

a = b.q+r = b.q+b+i = b. (q+1) + i,

ce qui implique (par définition de £) que b.(q+1) £ a, c'est-à-dire que q ne serait pas le plus grand élément de Q, ce qui est contraire aux hypothèses.

Unicité : supposons qu'il existe deux couples, (q,r) et (q',r'), vérifiant les deux propriétés. On aurait alors

b.q+r = b.q'+r'

puisque les deux expressions sont, d'après (1), toutes deux égales à a, et donc, par de l'algèbre simple,

b.(q-q') = r'-r

c'est-à-dire que r'-r est un multiple de b. Comme r et r' vérifient tous deux (2), leur différence vérifie

-b < r'-r < b

Or le seul multiple de b strictement compris entre -b et b est 0 : on a nécessairement r'-r = 0, donc r=r', et par conséquent q=q'

L'entier q s'appelle le quotient de a par b, r est le reste de la division. On note aussi q = a div b et r = a mod b. Remarquons que, si a>0, q<a. Le résultat suivant (dont nous donnerons deux preuves) appelé théorème de numération, donne une représentation des entiers :

Théorème 2.2 Soit b>1. Pour tout x Î IN , il existe un unique k³ 0 et une unique suite d'entiers x₀,...,x_k tels que

(1)

i=0

x_ibⁱ

(2)

" i Î {0,...,k}, 0 £ x_i < b

Preuves : nous allons voir deux preuves de ce théorème. Comme souvent en informatique, chacune des preuves va donner lieu à un algorithme qui nous permettra de trouver la représentation d'un entier dans une base quelconque.

Preuve 1 : cette preuve, bien que valable pour tout b>1, donne lieu à un algorithme bien adapté au cas où b=2, et beaucoup moins pratique dans les autres cas. Distinguons deux cas :

x<b : alors il suffit de prendre k=0, x₀=x et le tour est joué.
b£ x : alors, grâce à des propriétés bien connues de N, il existe k³ 1 tel que
b^k£ x <b^k+1
On considère la suite de couples (x_i,r_i) définie pour 0<i£ k par

ì
í
î

(x_k,r_k) est la division euclidienne de x par b^k

pour 1£ i <k, (x_i,r_i) est la division euclidienne de r_i+1 par bⁱ

et on pose x₀=r₁. Notons que les x_i sont uniques (puisqu'ils sont des quotients euclidiens, ou un reste pour x₀), et qu'ils vérifient bien (2) : ceci résulte de ce que, par construction, r_i < bⁱ, et du fait que l'on ne manipule que des nombres positifs. Il reste à montrer (1). On va se servir de la propriété suivante : pour tout i Î {1,...,k},

r_i=

i-1

å

j=0
x_j.b^j
Montrons-la par récurrence sur i :
- on a r₁ = x₀ = x₀.1=x₀.b⁰, et la propriété est vérifiée au rang 1;
- supposons la propriété vraie au rang i<k, et montrons-la au rang i+1 :
  
  r_i+1 = x_i.bⁱ+r_i (par définition)
  
  =
  
  x_i.bⁱ+
  
  i-1
  
  å
  
  j=0
  x_j.b^j
  (par hypothèse de récurrence)
  
  =
  
  i
  
  å
  
  j=0
  x_j.b^j
  
  Il ne nous reste plus qu'à vérifier (1) :
  
  x = x_k.b^k+r_k (par définition)
  
  =
  
  x_k.b^k+
  
  k-1
  
  å
  
  i=0
  x_i.bⁱ
  (propriété ci-dessus au rang k)
  
  =
  
  k
  
  å
  
  i=0
  x_i.bⁱ

Preuve 2 : cette deuxième preuve est celle qui est en général utilisée pour trouver l'écriture d'un nombre dans une base quelconque. Encore une fois, distinguons deux cas :

x<b : alors il suffit de prendre k=0, x₀=x et le tour est joué.

b£ x : on considére la suite de couples d'entiers (q_i,x_i)_{i Î}_N définie par

(q₀,x₀)	est la division euclidienne de x par b
et, pour i ³ 1,
(q_i,x_i)	est la division euclidienne de q_i-1 par b

Cette suite est stationnaire, de valeur (0,0), à partir d'un certain rang, et il existe un rang, notons-le k, tel que q_k =0 et x_k >0 (la preuve de ces assertions est laissée en exercice). La propriété (2) est bien vérifiée, puisque les x_i sont des restes de divisions euclidiennes. De même, les x_i sont uniques, d'après le théorème précédent. Il reste maintenant à prouver la propriété (1). À cet effet, on va montrer que, pour i Î {0,...,k},

q_i=

i+1

j=k

x_j.b^j-(i+1)

La preuve se fait par récurrence descendante sur i :

commençons par le cas de base i=k : on a, puisque l'intervalle [k+1,k] est vide,

q_k=

k+1

å

j=k
x_j.b^j-i=0

supposons la propriété vraie pour i>0, et montrons que la relation est encore vérifiée pour i-1 :

q_i-1

b.q_i + x_i

par définition

i+1

j=k

x_j.b^j-(i+1) + x_i

par hypothèse de récurrence

i+1

j=k

x_j.b^j-(i+1)+1 + x_i.b⁰

i+1

j=k

x_j.b^j-((i-1)+1)+x_i.b^i-((i-1)+1)

(i-1)+1

j=k

x_j.b^j-((i-1)+1)

qui est la formule que l'on voulait obtenir.

À l'aide de cette relation entre les q_i et les x_i, on va pouvoir maintenant démontrer (1) : on a

b.q₀ + x₀

par définition de (q₀,x₀)

j=k

x_j.b^j-1+x₀

d'après la propriété précédente, écrite pour i=0

j=k

x_j.b^j + x₀.b⁰

j=0

x_j.b^j

La suite finie (x₀,...,x_k) s'appelle représentation de x en base b ou écriture de x en base b. Les x_i sont les chiffres de x en base b. Le poids d'un chiffre est son indice. On écrit x en général à l'envers, en donnant les chiffres de poids fort en premier, et en terminant par le chiffre des unités x₀. On peut, si le contexte le justifie, indicer cette écriture par la base, pour souligner la base de représentation dans le cas où l'on utilise simultanément plusieurs bases. Remarquons que, d'après le point (2) du théorème de numération, les chiffres en base b sont les entiers 0,1,...,b-1 : il y en a exactement b. Si b>10, il va nous falloir des chiffres supplémentaires : l'usage veut qu'on prenne les lettres à partir de A. Ainsi les chiffres en base 16 sont

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

Remarque : nous sommes habitués à manipuler des nombres écrits en base 10. Il va nous falloir distinguer entre différentes représentations des nombres. Nous adopterons la convention suivante, dans toute la suite de ce document : une écriture normale d'un nombre indiquera qu'il est écrit en base 10. Ainsi par exemple 1253 dénote bien l'entier mille deux cent cinquante trois. Pour écrire un nombre en base b, on indicera sa représentation par la base. Par exemple, 1253₇ désigne le nombre dont la représentation en base 7 comporte 4 chiffres, le plus lourd étant 1 et le plus léger 3.

Exemples :

Reprenons le nombre 1253₇. Quelle est sa représentation en base 10 ? Il suffit de reprendre la formule donnée dans le théorème de numération. La notation 1253₇ désigne en fait la formule

k

å

i=0
x_ibⁱ
dans laquelle k=3, b=7, x₀=3, x₁=5, x₂=2 et x₃=1, ce qui donne (si on écrit en base 10)

k

å

i=0
x_ibⁱ
= 3.7⁰ + 5.7¹ + 2.7² + 1.7³

= 3.1 + 5.7 + 2.49 + 1.343

= 3 + 35 + 98 + 343

= 479
considérons le nombre dénoté par 100110₂. On a k=5 et b=2, et sa valeur en base 10 est donnée par

k

å

i=0
x_ibⁱ
= 0.2⁰ + 1.2¹ + 1.2² + 0.2³ + 0.2⁴ + 1.2⁵

= 0.1 + 1.2 + 1.4 + 0.8 + 0.16 + 1.32

= 0 + 2 + 4 + 0 + 0 + 32

= 38

2.1

Changement de base

Il nous faut maintenant répondre à une question cruciale : comment obtient-on la représentation d'un nombre dans une base donnée ? Supposons, pour commencer, que l'on dispose d'un nombre n écrit en base 10. L'algorithme de passage dans une base b>1 le plus général est celui donné dans la deuxième preuve du théorème de numération : on fait des divisions successives, d'abord de n par b, puis des quotients obtenus (par b toujours), jusqu'à tomber sur un quotient nul. L'écriture de n en base b est alors la suite des restes, prise en sens inverse. Illustrons ceci par un exemple : quelle est la représentation de 479 en base 7?

on a 479 = 7.68+3, donc le dernier chiffre de 479 en base 7 est 3;
on a 68=7.9+5, donc le chiffre de poids 1 de 479 en base 7 est 5;
on a 9=7.1+2, donc le chiffre de poids 2 de 479 en base 7 est 2;
on a 1=7.0+1, donc le chiffre de poids le plus élevé de 479 en base 7 est 1.

En prenant ces chiffres dans l'ordre inverse, on obtient

479=1253₇

En pratique, on dispose les calculs de la façons suivante :

479

7×68

7×9

7×1

7×0

On arrête dès que le quotient devient nul, et la représentation de n en base b se lit de bas en haut.

Le cas particulier de la base 2 : La première preuve du théorème donne un algorithme qui est efficace pour trouver la représentation en base 2 d'un entier, dès lors que l'on connaît bien les puissances de 2 (ce qui est le cas de n'importe quel informaticien digne de ce nom...). En effet, les quotients des divisions euclidiennes successives (qui sont les chiffres du nombre en base 2) ne peuvent prendre que les valeurs 0 ou 1. Il suffit donc de soustraire les puissances de 2, en commençant par la plus grande inférieure à n, et de continuer jusqu'à ce qu'on arrive à 0. Le chiffre de poids i de l'écriture de n en base 2 sera 1 si l'on a soustrait 2ⁱ, et 0 sinon. Trouvons par exemple la représentation en base 2 de 479. Pour simplifier, on va commencer par écrire les puissances de 2 :

k	0	1	2	3	4	5	6	7	8	9	...
2^k	1	2	4	8	16	32	64	128	256	512	...

On a alors :

479 - 256	=	223	et le chiffre de poids 8 est donc 1
223 - 128	=	95	et le chiffre de poids 7 est donc 1
95 - 64	=	31	et le chiffre de poids 6 est donc 1
31 - 16	=	15	et le chiffre de poids 4 est donc 1
15 - 8	=	7	et le chiffre de poids 3 est donc 1
7 - 4	=	3	et le chiffre de poids 2 est donc 1
3 - 2	=	1	et le chiffre de poids 1 est donc 1
1 - 1	=	0	et le chiffre de poids 0 est donc 1

Tous les autres chiffres sont 0, et l'écriture de 479 en base 2 est 111011111₂

Nous savons donc comment passer de la représentation en base 10 à n'importe quelle base et vice-versa. Mais comment fait-on pour passer d'une représentation à une autre, dans le cas où aucune des deux bases n'est 10 ? Supposons que l'on veuille l'écriture en base 3 du nombre (écrit en base 5) 431₅. Il y a deux manières de faire :

on trouve l'écriture en base 10 de 431₅ en utilisant la formule du théorème de numération, puis on effectue les divisions nécessaires pour trouver l'écriture en base 3 :

k

å

i=0
x_ibⁱ
= 4.5² + 3.5¹ + 1.5⁰

= 4.25 + 3.5 + 1.1

= 100 + 15 + 1

= 116
puis

116 = 3×38 +

2

38 = 3×12 +

2

12 = 3×4 +

0

4 = 3×1 +

1

1 = 3×0 +

1

et on a 431₅=11022₃.
on peut être plus rapide, et se passer de la transformation en base 10 en effectuant les divisions directement en base 5 : pour cela, il faut connaître (comme en base 10 !) ses tables d'addition et de multiplication en base 5. On obtient alors :

431₅ = 3₅ × 123₅ + 2₅

123₅ = 3₅ × 22₅ + 2₅

22₅ = 3₅ × 4₅ + 0₅

4₅ = 3₅ × 1₅ + 1₅

1₅ = 3₅ × 0₅ + 1₅

et on retrouve, en lisant les chiffres de bas en haut, 431₅=11022₃.

2.2

Un cas particulier très important

Il s'agit des passages entre les bases b et b^k, pour k>1. Soit n un entier.

Passage de la base b à la base b^k:

On découpe la représentation de n en base b en tranches de k chiffre, en commençant par la droite et en rajoutant des 0 à gauche si le nombre de chiffres de n n'est pas un multiple de k. Chaque tranche de k chiffres est alors transformée en un chiffre en base b^k. Ces chiffres, écrits dans cet ordre, constituent l'écriture de n en base b^k.

Par exemple, soit 1022102₃ à écrire en base 9=3². On le coupe en tranches de k=2 chiffres, à partir de la droite, en rajoutant un 0 au début puisque le nombre de chiffres n'est pas un multiple de 2:

1022102₃ = 01022102

On écrit chaque tranche comme un chiffre en base 9 :

01₃=1₉, 02₃=2₉, 21₃=7₉, 02₃=2₉.

L'écriture de 1022102₃ en base 9 est donc 1272₉

Passage de la base b^k à la base b :

C'est la transformation inverse; il suffit d'exprimer chaque chiffre en base b^k comme un nombre écrit en base b sur k chiffres, en rajoutant des 0 si l'écriture du nombre obtenu comporte moins de k chiffres en base b.

Par exemple, on souhaite obtenir l'écriture en base 2 du nombre E801₁₆. 16=2⁴, et il faut traduire chaque chiffre en base 16 par un nombre de 4 chiffres en base 2. On a

E₁₆=1110₂, 8₁₆=1000₂, 0₁₆=0₂=0000₂, 1₁₆=1₂=0001₂.

On a donc E801₁₆ = 1110.1000.0000.0001₂ (les points ont été ajoutés dans un souci de lisibilité, ils ne sont pas nécessaires).

2.3

Un peu d'exotisme

Jusqu'ici on a parlé d'écriture des entiers, dans un cadre standard. Il existe beaucoup d'autres façons de représenter des nombres, et nous allons en voir trois :

la représentation en <<base Fibonacci>> : comme son nom l'indique, elle utilise les valeurs de la célèbre suite de Fibonacci. Cette représentation est peu pratique pour les calculs (par exemple l'addition en base Fibonacci est loin d'être triviale, pour ne pas parler de la multiplication). On la retrouve cependant dans de nombreux problèmes, où le simple fait d'écrire les nombres manipulés dans cette base rend la résolution évidente.
les systèmes d'Avizienis : il s'agit d'une représentation standard dans laquelle les chiffres peuvent être négatifs. Une des conséquences importantes de l'introduction de chiffres négatifs est l'existence d'un algorithme très efficace d'addition, comme on le verra plus loin.
enfin, pour égayer un peu le ton un peu austère de ce document, nous parlerons du système de numération dit << Bi-Binaire >>, que nous devons au regretté Boby Lapointe.

2.3.1

Base Fibonacci

On rappelle la définition de la suite de Fibonacci :

F₀=0, F₁=1, et pour n>1, F_n=F_n-1+F_n-2

Les premières valeurs de cette suite sont

k	0	1	2	3	4	5	6	7	8	9	...
F_k	0	1	1	2	3	5	8	13	21	34	...

Les nombres de Fibonacci sont présents dans quantité de domaines, qu'ils soient de nature mathématique, informatique, voire biologique. Comme l'a dit un de leurs découvreurs,

La suite de Fibonacci possède des propriétés nombreuses fort intéressantes²

La propriété qui nous intéresse ici est le sujet du théorème suivant, dit <<de Zeckendorf>> :

Théorème 2.3 Tout entier strictement positif n a une unique représentation de la forme

n=F

k₁

k₂

+···+F

k_r

vérifiant les propriétés

pour i Î {1,...,r-1}, k_i ³ k_i+1 + 2
k_r ³ 2

Ce théorème donne un nouveau système de numération : l'écriture d'un nombre en base Fibonacci est une suite de 0 et de 1, comme en base 2, sauf que d'après la condition (1) on ne peut avoir deux 1 consécutifs : en effet, la somme de deux nombres de Fibonacci consécutifs est un nombre de Fibonacci, par définition. On a alors (les b_i représentent soit 0 soit 1)

n=(b_mb_m-1...

b₂)_F n=

i=2

b_iF_i

Donnons un exemple : quelle est la représentation Fibonacci de 30? On a

30 = 21 + 8 + 1 = 1.F₈+0.F₇+1.F₆+0.F₅+0.F₄+0.F₃+1.F₂

et l'écriture de 30 en base Fibonacci est 1010001_F (comme de coutume, les chiffres de poids forts sont à gauche).

2.3.2

Systèmes d'Avizienis

Pourquoi restreindre les chiffres de l'écriture en base b à être dans l'ensemble {0,...,b-1} ? Que se passe-t-il si l'on s'autorise des chiffres négatifs ? Ce sont les questions auxquelles nous allons répondre.

Définition 2.1 Soit b >1. Un système de numération d'Avizienis de base b est la donnée d'un ensemble de chiffres C tel que

C={-a,-a+1,...,0,...,a-1,a}
a£ b-1
b+1£2a

L'ensemble C est l'ensemble des chiffres que l'on va utiliser pour écrire les nombres en base b. Les conditions sur C sont très peu contraignantes, mais on peut noter que les deux dernières excluent l'usage de la base 2 : les systèmes d'Avizienis ne sont utilisables que pour des bases strictement plus grandes que 2. On utilise en général les ensembles de chiffres

C_b¹ = {-(b-1),...,0,...,b-1}

ou bien, en arrondissant (b+1)/2 à l'entier immédiatement inférieur,

C_b² = {-(b+1)/2,,...,0,...,(b+1)/2}

Les chiffres négatifs sont écrits avec une barre au-dessus : ainsi 7 désigne le chiffre -7.

Exemples :

Considérons le système d'Avizienis de base 10 dont les chiffres sont

C₁₀¹ = {

9
,

8
,

7
,

6
,

5
,

4
,

3
,

2
,

1
,0,1,2,3,4,5,6,7,8,9}
Dans ce système, le nombre 7 admet comme écriture 7 (comme on pouvait s'y attendre !), mais aussi 13 (car 7=10 -3), mais aussi 193 (car 7 = 100 -93), et, de façon générale, toute écriture de la forme 19...93 représente 7.
Toujours en base 10, on prend comme ensemble de chiffres

C₁₀² = {

5
,

4
,

3
,

2
,

1
,0,1,2,3,4,5}
Trouvons une représentation de 63 : on a 63 = 100 - 37, et 37 = 40 -3, donc 63 = 100 -40 +3 et une représentation de 63 dans cette base est 143.

Dans le système d'Avizienis de base 5 et de chiffres

C₅² = {

,0,1,2,3}

les nombres de 1 à 20 peuvent s'écrire

1_5A

11_5A

21_5A

31_5A

2_5A

12_5A

22_5A

32_5A

3_5A

13_5A

23_5A

33_5A

_5A

10_5A

20_5A

30_5A

_5A

Ici aussi, on remarque que 12, par exemple, a plusieurs écritures :

22_5A, car 12 = 2×5+2;
33_5A, car 12 = 3×5-3;
et 123_5A, car 12 = 1×5²-2×5-3.

L'un des avantages des systèmes d'Avizienis, qui en fait un candidat intéressant pour la représentation en machine, est que le passage de n à -n se fait simplement en changeant les signes des chiffres, ce qui implique qu'il suffit de savoir additionner pour savoir soustraire, et donc que le même algorithme va servir aussi bien pour l'addition que pour la soustraction. Ceci a un prix, visible sur les exemples : on ne peut plus garantir que la représentation d'un nombre soit unique.

2.3.3

Le système Bi-Binaire

Le système de numération Bi-Binaire a été mis au point par Boby Lapointe dans les années 60 (1969). Il s'agit moins d'un système de numération que d'une façon d'écrire les entiers, la motivation principale étant de pouvoir énoncer des nombres, aussi grands soient-ils, sans qu'il soit besoin d'inventer des mots (une autre motivation, tout aussi importante, est de se donner la possibilité d'euphonies et d'allitérations qui sont la marque distinctive de l'oeuvre de Boby Lapointe, et dont on peut raisonnablement penser qu'elles fourniront la matière à quantité de calembours et autres << lape-près >>...).

On considère la base 16. Dans cette base, il y a 16 chiffres, de 0 à F; si l'on écrit ces chiffres en base 2, chacun est représenté par quatre chiffres. Ainsi 5 s'écrit 0101₂, et D s'écrit 1101₂. Si l'on découpe ces écritures en base 2 en deux groupes de deux chiffres binaires par le milieu, ce qui n'est pas à conseiller, on obtient deux moitiés de chiffre hexadécimal, et deux bits d'un côté, et deux bits de l'autre. Les deux bits de gauche s'appellent (par conséquent ?) les bits de poids forts³, les deux bits de droite constituant les poids faibles.

Le système Bi-Binaire consiste à faire correspondre à chacun de ces groupes une lettre, selon les tableaux suivants :

Poids forts
`00`	H
`01`	B
`10`	K
`11`	D

Poids faibles
`00`	O
`01`	A
`10`	E
`11`	I

Les chiffres en base 16 se traduisent donc de la façon suivante :

Base 16	Base 2	Bi-binaire	Base 16	Base 2	Bi-binaire
0	0000	HO	8	1000	KO
1	0001	HA	9	1001	KA
2	0010	HE	A	1010	KE
3	0011	HI	B	1011	KI
4	0100	BO	C	1100	DO
5	0101	BA	D	1101	DA
6	0110	BE	E	1110	DE
7	0111	BI	F	1111	DI

Ainsi, 31, qui s'écrit 1F₁₆, devient HADI, et KAHABA dénote l'entier qui s'écrit 915 en base 16, c'est-à-dire 2325 en base 10. L'entier 1000, quant à lui, s'écrit HIDEKO. Enfin, si un commerçant peut parler d'HAHIKIDO quotidien, il ne s'agit pas d'arts martiaux, mais simplement de son chiffre d'affaire (Exercice : calculer du coup son chiffre d'affaire annuel).

Exercices de la partie 2

Quels sont les chiffres en base 13 ?
Donner la représentation des nombres 45, 128, 91, 1654 en base 3, 5, 7, 13.

Effectuer les opérations suivantes, sans repasser par la base 10 :

(base 7)

                   456             601            143    
                 +  15           - 142          *  25

(base 4)

                   112             331            231    
                 +  13           -  12          *  12

(Passages entre les bases 2, 4, 8 et 16)
1. Donner la représentations des nombres suivants (écrits en base 2) dans les bases 4, 8 et 16 :
```
          10011101    100110011001100    10101110001110011100111001
```
2. Donner la représentations des nombres suivants (écrits en base 8) dans les bases 2, 4 et 16 :
```
          50234       254120      1547  
```
3. Donner la représentations des nombres suivants (écrits en base 4) dans les bases 2 et 16 :
```
          10232       203012      222330
```
4. Donner la représentations des nombres suivants (écrits en base 16) dans les bases 2 et 4 :
```
          4E0F        1FF8        ABCD
```
Programmer l'algorithme de changement de base avec un tableur (de la base 10 vers une base b quelconque, puis l'inverse).
Vérifier que, en base 4, 6 = 2× 3 s'écrit 12, 9 = 3² s'écrit 21. Vérifier de même que 12= 2× 6 et 36 = 6² s'écrivent respectivement 15 et 51 en base 7, et que 30 = 2× 15 et 225 = 15² s'écrivent 1E et E1 en base 16.

Généraliser : soit b un entier plus grand que 4. Montrer que le double de b-1 s'écrit 1(b-2) en base b, et que, dans cette même base, son carré s'écrit (b-2)1.
Trouvez la ou les bases dans chacun des cas suivants. Justifiez votre réponse.
1. 34 (écrit en base 5) s'écrit 31 en base b. Trouvez b.
2. 482 (écrit en base 10) s'écrit 742 en base b'. Trouvez b'.
3. Un nombre s'écrit 42 en base b₁ et 31 en base b₂. Un autre nombre s'écrit 14 en base b₁ et 12 en base b₂. Trouvez b₁ et b₂.
Autrefois, lorsque les calculatrices de poche n'existaient pas, on utilisait des trucs et astuces divers (des algorithmes) pour calculer. Ainsi, on utilisait l'algorithme suivant pour élever au carré les nombres entiers dont l'écriture en base 10 se termine par 5 :
- soit à élever au carré le nombre n5 (prenons par exemple 65);
- on multiplie n par n+1 pour obtenir le nombre m : ici, on obtient m=6× 7 = 42;
- le carré cherché est la concaténation de m et 25 : ici, on obtient 65² = 4225, ce qu'on peut facilement vérifier.
1. Justifier cet algorithme, c'est-à-dire montrer que le résultat est toujours correct, quel que soit l'entier (finissant par 5) choisi.
2. Généraliser : donner et justifier un algorithme simple permettant d'obtenir l'écriture en base 2b du carré d'un nombre dont l'écriture dans cette base se termine par b.
Soit x un nombre écrit en base 6. Comment reconnaît-on que x est pair ? Que x est multiple de 3 ?

Plus généralement, en base a.b, comment reconnaît-on simplement qu'un nombre écrit dans cette base est un multiple de a ou de b ?
Jeu de
1emN
I
M
: ce jeu se joue à 2 joueurs. On dispose au départ d'un nombre quelconque d'allumettes, réparties en un nombre quelconque de tas. Chaque joueur à son tour enlève 0 ou 1 allumette à chaque tas, mais au moins une allumette (on peut donc enlever, à chaque tour, un nombre d'allumettes compris entre 1 et le nombre de tas constituant la position). Le gagnant est celui qui enlève la dernière allumette.
1. Parmi les positions suivantes, lesquelles sont gagnantes ?
```
  (1 1 1 1)   (2 2 2)   (1 1 2 2)  (5 2 6 4 8)   (3 9 11 7 15)
```
2. Caractériser les positions gagnantes, et montrer en particulier qu'il est toujours possible de passer d'une position gagnante à une position perdante, mais que l'inverse est impossible.
Jeu de NIM : ce jeu se joue à 2 joueurs. On dispose au départ d'un nombre quelconque d'allumettes, réparties en un nombre quelconque de tas. Chaque joueur à son tour enlève entre 1 et toutes les allumettes d'un seul tas. Le gagnant est celui qui enlève la dernière allumette.
1. Donner, parmi les positions suivantes, celles qui sont gagnantes :
```
     (5 3 9 10)    (8 2 5 15)    (1 5 3 2)    (1 3 5 7)
```
2. Montrer que le jeu de Nim est un cas particulier du jeu précédent, et en déduire une caractérisation des positions gagnantes au jeu de Nim.
La dernière du tas : ce jeu se joue à 2 joueurs. On constitue un tas contenant un nombre quelconque d'allumettes. Chaque joueur à son tour enlève entre 1 et 2 fois le nombre d'allumettes enlevées par le joueur précédent. Par exemple, si l'adversaire vient d'enlever 3 allumettes, on peut enlever 1, 2, 3, 4, 5 ou 6=2×3 allumettes. Le premier joueur enlève 1 ou 2 allumettes. Le gagnant est celui qui enlève la dernière allumette.
1. Pour chacun des tas de départ suivant, indiquer lequel, du premier ou du deuxième joueur, a une ligne de jeu gagnante : 1, 2, 3, 5, 8, 13. Ces nombres vous rappellent-ils quelque chose ?
2. Donner un algorithme qui mène, lorsque c'est possible, à une victoire contre toute défense.
Solution de la dernière du tas : Soit d le nombre d'allumettes enlevées au coup précédent (on pose d=1 pour le premier joueur), et N le nombre d'allumettes restant dans le tas. L'écriture de N en base Fibonacci est un mot écrit avec des 0 et des 1, et se terminant par la chaîne 10^k (un 1 suivi de k 0): autrement dit, le plus petit nombre de Fibonacci intervenant dans l'écriture de N est F_k+2. Alors de deux choses l'une :
- soit d < é F_k+2/2 ù : la position est perdante, quel que soit le nombre d'allumettes que l'on enlève;
- soit d ³ é F_k+2/2 ù : la position est gagnante, il suffit d'enlever F_k+2 allumettes.
Exercice subsidiaire difficile: démontrer ces allégations, surtout la première. Pour la deuxième, soit A le joueur qui enlève F_k+2 allumettes, et B son adversaire. De deux choses l'une :
1. soit il n'y a plus d'allumettes et A a gagné;
2. soit il en reste, et on va montrer par induction que B est dans une position perdante. On avait au mieux N = N' + F_k+4 + F_k+2. Il reste N' + F_k+4 allumettes, et il suffit de montrer que
  
  F_k+2 < é
  ê
  ê
  ê
  
  F_k+4
  
  2
  ù
  ú
  ú
  ú .
  Or ceci est une banalité, car on sait que F_n < F_n+1, ce qui implique que 2F_n < F_n + F_n+1 = F_n+2. L'expression <<au mieux>> prend tout son sens si le nombre de Fibonacci suivant F_k+2 dans l'écriture de N est plus grand que F_k+4.
Donner la représentation dans le système d'Avizienis de base 10 qui a pour chiffres
{-5,-4,-3,-2,-1,0,1,2,3,4}
des entiers de 0 à 30.
On considère le système d'Avizienis de base 10 qui a pour chiffres
{-9,...,0,...,9}
Donner toutes les représentations des nombres de 1 à 10.
On se propose d'étudier certaines représentations d'Avizienis de base 10.
1. Si a=6, donner toutes les représentations des entiers de 1 à 20. Quel est le plus petit nombre à deux chiffres positifs qui admet deux représentations ? Et à 3 chiffres ? Montrer qu'aucun entier inférieur à 1000 n'admet plus de 2 représentations dans cette base.
2. On considère maintenant a=9. Donner le plus petit nombre à deux chiffres positifs admettant une infinité de représentations, puis le plus petit à 3 chiffres positifs.
On se propose de trouver (et de justifier) un algorithme simple permettant de déterminer si un nombre écrit dans une base b donnée est pair ou impair. On pourrait calculer la représentation en base 10 de ce nombre, puis regarder le dernier chiffre pour décider. Cependant, il est inutile de passer par la base 10 pour ceci, et le but de l'exercice est de trouver un moyen plus simple d'y parvenir.
1. Donner l'écriture en base 3 de tous les nombres compris entre 20 et 30 (20 et 30 inclus). Même question pour la base 4.
2. En s'inspirant de l'exemple de la base 4, trouver et prouver un critère de parité des nombres écrits dans une base paire.
3. En s'inspirant de l'exemple de la base 3, trouver et prouver un critère de parité des nombres écrits dans une base impaire.
Soit x un nombre écrit en base 16. Comment sait-on, à la vue de son écriture en base 16, que x est pair ? Que x est multiple de 4 ? Que x est multiple de 8 ?

Plus généralement, en base bⁿ, comment reconnaît-on simplement qu'un nombre écrit dans cette base est un multiple de b^k (avec 0 < k £ n) ?
Justifier la méthode de changement de représentation entre les bases b et b^k, et en particulier montrer qu'un nombre de k chiffres en base b est toujours strictement inférieur à b^k.
Soient b₁ et b₂ deux entiers plus grands que 1, tels que b₂ < b₁. On dit que les bases b₁ et b₂ sont amies s'il existe un entier qui s'écrit xy en base b₁ et yx en base b₂ (x et y doivent être différents de 0, et on a nécessairement x¹ y). Par exemple, les bases 5 et 3 sont amies car 7 s'écrit 12 en base 5 et 21 en base 3. On dit d'un tel entier qu'il est le témoin de l'amitié de b₁ et b₂.
1. Donner tous les témoins pour les base 3 et 5, 4 et 7 et 6 et 11.
2. Montrer que si b₁ = 2b₂ - 1 alors b₁ et b₂ sont amies.
3. Plus généralement, montrer que si b₁ = kb₂ - (k-1) alors b₁ et b₂ sont amies (on dit que b₁ est amie d'ordre k de b₂). Donner la plus petite base ayant une amie d'ordre k.
On se propose d'étudier certaines propriétés de la base -2. Dans cette base, comme en base 2, les chiffres sont 0 et 1. La notation x_nx_n-1... x₁x₀ où pour tout iÎ{0,...,n}, x₁ est le chiffre 0 ou le chiffre 1, désigne l'entier

n

å

i=0
x_i.(-2)ⁱ
Par exemple,

11011101 = 1.(-2)⁷+1.(-2)⁶+1.(-2)⁴+1.(-2)³+1.(-2)²+1.(-2)⁰

= -128 + 64 + 16 -8 +4 +1

= -51
On voit sur l'exemple que les entiers négatifs sont naturellement représentables dans cette base.
1. Donner les représentations des entiers de -10 à 10.
2. Énoncer une méthode simple permettant de trouver l'écriture de -x (en base -2) à partir de celle de x (en base -2).
3. On note X_n (avec n ³ 1) le nombre dont l'écriture en base (-2) est composée de n fois le chiffre 1 (par exemple X₁=1, et X₃=111). Montrer que
  
  X_2k+1=
  
  1
  
  3
  ( 2^2k+1+1 )
  Que vaut X_2k ? Et comment s'écrit -X_2k en base -2 ?

`431`₅	=	`3`₅	×	`123`₅	+	`2`₅
`123`₅	=	`3`₅	×	`22`₅	+	`2`₅
`22`₅	=	`3`₅	×	`4`₅	+	`0`₅
`4`₅	=	`3`₅	×	`1`₅	+	`1`₅
`1`₅	=	`3`₅	×	`0`₅	+	`1`₅

11011101	=	1.(-2)⁷+1.(-2)⁶+1.(-2)⁴+1.(-2)³+1.(-2)²+1.(-2)⁰
	=	-128 + 64 + 16 -8 +4 +1
	=	-51