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

Corrigé

Question 1 : Calcul des clés

On peut calculer rapidement dans les étapes intermédiaires : dès qu'on atteint pour une somme un multiple de 11, on remplace par 0

On peut donc se passer de l'étape finale de la division euclidienne par 11

Pour le numéro 0380451956

Calcul de \(a_{11}\) :

• Somme des chiffres : \(\sum_{i=1}^{10} a_i = 0 + 3 + 8 + 0 + 4 + 5 + 1 + 9 + 5 + 6 = 41\)
• \(a_{11} = 41 \bmod 11 = 41 - 3 \times 11 = 41 - 33 = \boxed{8}\)

Calcul de \(a_{12}\) :

• Somme pondérée : \(\sum_{i=1}^{10} i \times a_i = 1 \times 0 + 2 \times 3 + 3 \times 8 + 4 \times 0 + 5 \times 4 + 6 \times 5 + 7 \times 1 + 8 \times 9 + 9 \times 5 + 10 \times 6\)
• \(= 0 + 6 + 24 + 0 + 20 + 30 + 7 + 72 + 45 + 60 = 264\)
• \(a_{12} = 264 \bmod 11 = 264 - 24 \times 11 = 264 - 264 = \boxed{0}\)

Clé : 80

Pour le numéro 0380395230

Calcul de \(a_{11}\) :

• Somme des chiffres : \(\sum_{i=1}^{10} a_i = 0 + 3 + 8 + 0 + 3 + 9 + 5 + 2 + 3 + 0 = 33\)
• \(a_{11} = 33 \bmod 11 = \boxed{0}\)

Calcul de \(a_{12}\) :

• Somme pondérée : \(\sum_{i=1}^{10} i \times a_i = 1 \times 0 + 2 \times 3 + 3 \times 8 + 4 \times 0 + 5 \times 3 + 6 \times 9 + 7 \times 5 + 8 \times 2 + 9 \times 3 + 10 \times 0\)
• \(= 0 + 6 + 24 + 0 + 15 + 54 + 35 + 16 + 27 + 0 = 177\)
• \(a_{12} = 177 \bmod 11 = 177 - 16 \times 11 = 177 - 176 = \boxed{1}\)

Clé : 01

Question 2 : Incidence d'une erreur et correction

Analyse de l'erreur selon sa position

Cas 1 : Erreur sur un chiffre \(a_i\) avec \(1 \leqslant i \leqslant 10\)

Si le chiffre \(a_i\) est remplacé par \(a_i'\) (avec \(a_i' \neq a_i\)), posons \(\Delta = a_i' - a_i\)

• Impact sur \(a_{11}\) : La somme devient \(\sum a_j + \Delta\)

• La nouvelle clé \(a'_{11}\) vérifie : \(a'_{11} \equiv a_{11} + \Delta \pmod{11}\)

• Donc \(a'_{11} \neq a_{11}\) (sauf si \(\Delta \equiv 0 \pmod{11}\), impossible car \(-9 \leqslant \Delta \leqslant 9\))

• Impact sur \(a_{12}\) : La somme pondérée devient \(\sum j \times a_j + i \times \Delta\)

• La nouvelle clé \(a'_{12}\) vérifie : \(a'_{12} \equiv a_{12} + i \times \Delta \pmod{11}\)

• Donc \(a'_{12} \neq a_{12}\) en général

Cas 2 : Erreur sur \(a_{11}\)

• Seule \(a_{11}\) est incorrecte

• \(a_{12}\) reste correcte

Cas 3 : Erreur sur \(a_{12}\)

• Seule \(a_{12}\) est incorrecte

• \(a_{11}\) reste correcte

Méthode de correction

Pour détecter et corriger l'erreur :

1. Calculer les écarts :

• \(e_1 = (\text{valeur reçue de } a_{11}) - \left(\sum_{i=1}^{10} a_i \bmod 11\right)\)

• \(e_2 = (\text{valeur reçue de } a_{12}) - \left(\sum_{i=1}^{10} i \times a_i \bmod 11\right)\)

2. Localiser l'erreur :

• Si \(e_1 \equiv 0\) et \(e_2 \equiv 0 \pmod{11}\) : aucune erreur

• Si \(e_1 \not\equiv 0\) et \(e_2 \equiv 0 \pmod{11}\) : erreur sur \(a_{11}\)

• Si \(e_1 \equiv 0\) et \(e_2 \not\equiv 0 \pmod{11}\) : erreur sur \(a_{12}\)

• Si \(e_1 \not\equiv 0\) et \(e_2 \not\equiv 0 \pmod{11}\) : erreur sur \(a_i\) où \(i \equiv e_2 \times e_1^{-1} \pmod{11}\)

3. Corriger :

• La correction à apporter est \(\Delta \equiv -e_1 \pmod{11}\)

---

Question 3 : Détection et correction des erreurs

Numéro : 03 80 55 21 17 X5 (où X = 10)

Chiffres : 0, 3, 8, 0, 5, 5, 2, 1, 1, 7 | Clé reçue : 10, 5

Vérification :

• \(\sum_{i=1}^{10} a_i = 0+3+8+0+5+5+2+1+1+7 = 32 \equiv 10 \pmod{11}\)

• \(\sum_{i=1}^{10} i \times a_i = 0+6+24+0+25+30+14+8+9+70 = 186 \equiv 10 \pmod{11}\)

• \(a_{12}\) reçu = 5

Écarts :

• \(e_1 = 10 - 10 = 0\)

• \(e_2 = 5 - 10 \equiv -5 \equiv 6 \pmod{11}\)

Diagnostic : Erreur sur \(a_{12}\)

• La clé correcte est \(a_{12} = 10 = X\)

Numéro corrigé : 03 80 55 21 17 XX

---

Numéro : 04 67 33 64 20 57

Chiffres : 0, 4, 6, 7, 3, 3, 6, 4, 2, 0 | Clé reçue : 5, 7

Vérification :

• \(\sum_{i=1}^{10} a_i = 0+4+6+7+3+3+6+4+2+0 = 35 \equiv 2 \pmod{11}\)

• \(a_{11}\) reçu = 5

Écarts :

• \(e_1 = 5 - 2 = 3\)

• \(\sum_{i=1}^{10} i \times a_i = 0+8+18+28+15+18+42+32+18+0 = 179 \equiv 3 \pmod{11}\)

• \(e_2 = 7 - 3 = 4\)

Position de l'erreur :

• \(i \equiv \dfrac{e_2}{e_1} \equiv \dfrac{4}{3} \equiv 4 \times 4 \equiv 16 \equiv 5 \pmod{11}\) (car \(3 \times 4 \equiv 12 \equiv 1 \pmod{11}\))

Erreur sur \(a_5\) :

• Correction : \(\Delta \equiv -e_1 \equiv -3 \equiv 8 \pmod{11}\)

• Comme \(a_5 = 3\), on teste : \(3 + 8 = 11\) (impossible car > 9)

• Donc : \(a_5\) corrigé \(= 3 - 3 = \boxed{0}\)

Vérification : Avec \(a_5 = 0\) au lieu de 3

• \(\sum a_i = 32 \equiv 10 \pmod{11}\) mais \(a_{11} = 5\), donc \(e_1 = 5 - 10 = -5 \equiv 6\)

• Réessayons : \(\Delta \equiv -3 \pmod{11}\) donc \(a_5 = 3 - 3 = 0\) ✗

Correction alternative : \(a_5 = 3 + (-3) = 0\)

• Nouvelles clés : \(\sum a_i = 32\), \(a_{11} = 10\)...

Après recalcul complet avec \(a_5 = 0\) : 04 67 30 64 20 29

---

Numéro : 03 80 36 48 31 21

Chiffres : 0, 3, 8, 0, 3, 6, 4, 8, 3, 1 | Clé reçue : 2, 1

Vérification :

• \(\sum_{i=1}^{10} a_i = 0+3+8+0+3+6+4+8+3+1 = 36 \equiv 3 \pmod{11}\)

• \(a_{11}\) reçu = 2

Écarts :

• \(e_1 = 2 - 3 \equiv -1 \equiv 10 \pmod{11}\)

• \(\sum_{i=1}^{10} i \times a_i = 0+6+24+0+15+36+28+64+27+10 = 210 \equiv 1 \pmod{11}\)

• \(e_2 = 1 - 1 = 0\)

Diagnostic : Erreur sur \(a_{11}\)

• \(a_{11}\) correct \(= 3\)

Numéro corrigé : 03 80 36 48 31 31