6.8 Exercices
207
soit divisible par 11. Montrer que cette nouvelle d´ efinition est ´ equivalente `
a celle
qui est donn´ ee ci-dessus.
10. La m´ ethode suivante a ´ et´ e introduite par IBM pour construire un num´ ero de
carte de cr´ edit. Elle est aussi utilis´ ee au Canada dans les num´ eros de carte
d’assurance sociale. On construit des num´ eros de n chiffres, a 1 , . . . , a n , o` u a i ∈
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Le num´ ero est valide si le nombre b construit comme suit
est un multiple de 10 :
• si i est impair on pose c i = a i ;
• si i est pair et 2a i < 10, on pose c i = 2a i ;
• si i est pair et 2a i ≥ 10, alors 2a i = 10 + d i . On pose c i = 1 + d i , c’est-` a-dire
la somme des chiffres de 2a i ;
• alors
b =
n
i=1
c i .
a) Montrer que, si i est pair, alors c i est le reste de la division de 2a i par 9.
b) Les 15 premiers chiffres d’une carte sont 1234 5678 1234 567. Calculer le 16
e
chiffre.
c) Montrer que cette m´ ethode d´ etecte une erreur dans un des chiffres.
d) Un type d’erreur commun est l’inversion de deux chiffres cons´ ecutifs. La
m´ ethode IBM ne d´ etecte pas toujours ce genre d’erreur. Montrer cependant qu’elle
permet de d´ etecter une telle erreur si les deux chiffres cons´ ecutifs ne sont pas identiques (auquel cas l’inversion n’est pas une erreur) et s’ils ne sont pas tous les deux
dans l’ensemble {0, 9}.
11. Le code suivant est construit sur le mˆ eme principe que le code de Hamming. On
veut envoyer un mot de quatre bits (x 1 , x 2 , x 3 , x 4 ) o` u les x i = 0, 1. On l’allonge `
a
un mot de 11 lettres en ajoutant les bits x 5 , . . . , x 11 d´ efinis comme suit (on utilise
l’addition sur F 2 ) :
x 5 = x 1 + x 4 ,
x 6 = x 1 + x 3 ,
x 7 = x 1 + x 2 ,
x 8 = x 1 + x 2 + x 3 ,
x 9 = x 2 + x 4 ,
x 10 = x 2 + x 3 + x 4 ,
x 11 = x 3 + x 4 .
Montrer que ce code d´ etecte deux erreurs.
12. Construire le corps fini F 4 ` a quatre ´ el´ ements. (Donner explicitement les tables
d’addition et de multiplication.)
13. Donner tous les ´ el´ ements primitifs du corps F 9 de l’exemple 6.14 construit ` a l’aide
du polynˆ ome p(x) = x
2 + x + 2.
207
soit divisible par 11. Montrer que cette nouvelle d´ efinition est ´ equivalente `
a celle
qui est donn´ ee ci-dessus.
10. La m´ ethode suivante a ´ et´ e introduite par IBM pour construire un num´ ero de
carte de cr´ edit. Elle est aussi utilis´ ee au Canada dans les num´ eros de carte
d’assurance sociale. On construit des num´ eros de n chiffres, a 1 , . . . , a n , o` u a i ∈
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Le num´ ero est valide si le nombre b construit comme suit
est un multiple de 10 :
• si i est impair on pose c i = a i ;
• si i est pair et 2a i < 10, on pose c i = 2a i ;
• si i est pair et 2a i ≥ 10, alors 2a i = 10 + d i . On pose c i = 1 + d i , c’est-` a-dire
la somme des chiffres de 2a i ;
• alors
b =
n
i=1
c i .
a) Montrer que, si i est pair, alors c i est le reste de la division de 2a i par 9.
b) Les 15 premiers chiffres d’une carte sont 1234 5678 1234 567. Calculer le 16
e
chiffre.
c) Montrer que cette m´ ethode d´ etecte une erreur dans un des chiffres.
d) Un type d’erreur commun est l’inversion de deux chiffres cons´ ecutifs. La
m´ ethode IBM ne d´ etecte pas toujours ce genre d’erreur. Montrer cependant qu’elle
permet de d´ etecter une telle erreur si les deux chiffres cons´ ecutifs ne sont pas identiques (auquel cas l’inversion n’est pas une erreur) et s’ils ne sont pas tous les deux
dans l’ensemble {0, 9}.
11. Le code suivant est construit sur le mˆ eme principe que le code de Hamming. On
veut envoyer un mot de quatre bits (x 1 , x 2 , x 3 , x 4 ) o` u les x i = 0, 1. On l’allonge `
a
un mot de 11 lettres en ajoutant les bits x 5 , . . . , x 11 d´ efinis comme suit (on utilise
l’addition sur F 2 ) :
x 5 = x 1 + x 4 ,
x 6 = x 1 + x 3 ,
x 7 = x 1 + x 2 ,
x 8 = x 1 + x 2 + x 3 ,
x 9 = x 2 + x 4 ,
x 10 = x 2 + x 3 + x 4 ,
x 11 = x 3 + x 4 .
Montrer que ce code d´ etecte deux erreurs.
12. Construire le corps fini F 4 ` a quatre ´ el´ ements. (Donner explicitement les tables
d’addition et de multiplication.)
13. Donner tous les ´ el´ ements primitifs du corps F 9 de l’exemple 6.14 construit ` a l’aide
du polynˆ ome p(x) = x
2 + x + 2.