Devoir sur les Congruences

L'usage de la calculatrice est autorisé.

Durée: 55 min

Exercice 1

Avec des congruences, montrer que, pour tout entier n:

1. \(5^n-1\)  et \(13^n-1\)  sont divisibles par 4

2. En général, pour tout \(k\) entier naturel, \((4k+1)^n-1\) est divisible par 4.

Exercice 2

Le but de cet exercice est de prouver que, pour tout entier naturel \(n\), l'entier \(\text N=2^{2^{6n+2}}+3\)  est un multiple de 19.

1. Vérifier cette affirmation pour \(n=0\) .

2. Vérifier que \(2^6\)  \({\equiv}\) 1 mod(9).

   En déduire que pour tout n \({\in}\) \(\mathbb{N}\), il existe un entier naturel \(k\)  tel que: \(2^{6n}=9k+1\) .

3. À l'aide de congruences, déterminer le reste de la division euclidienne de \(2^{18}\)  par 19.

4. En utilisant les questions précédentes, prouver que N est bien un multiple de 19.

Exercice 3 : code correcteur de Hamming.

Considérons, par exemple, les nombres de 10 chiffres (numéros de téléphone) décimaux \(a_1a_2\ldots a_{10}\).

On rajoute une clé de 2 chiffres \(a_{11}a_{12}\) , où \(a_{11}\)  et \(a_{12}\)  sont l'un des symboles 0, 1, 2, ..., 9, X (X représentant la valeur 10), ainsi définis:

• \(a_{11}\)  est le reste de la division de \(\sum _{i=1}^{10}a_{\text i}\)  par 11;

• \(a_{12}\)  est le reste de la division de \(\sum _{i=1}^{10}\text i\times a_{\text i}\)  par 11.

• Calculer la clé pour chacun des numéros: 0380451956 et 0380395230.

• On suppose que, lors de la communication, une erreur est commise sur un et un seul des chiffres \(a_{\text i}\) . Quelle incidence cette erreur a-t-elle sur les clés ?

  (On distinguera les cas \(1\leqslant \text i\leqslant 10\) ,\(\text i=11\)  et \(\text i=12\) )

  Montrer alors qu'on peut corriger l'erreur. Comment ?

• Détecter et corriger l'erreur dans les numéros suivants:

  03 80 55 21 17 X5, 04 67 33 64 20 57 et 03 80 36 48 31 21