Code modulo 23 et inverse de 17
Pour sécuriser un registre, un lycée utilise un code de deux chiffres obtenu modulo 23. Le règlement indique que le code x, entier compris entre 1 et 22, doit vérifier 17x ≡ 5 (mod 23). L’intendant a entendu dire que 17 et 23 sont premiers entre eux, mais il veut une justification par l’algorithme d’Euclide et une identité de Bézout avant de calculer l’inverse de 17 modulo 23. Il doit ensuite déterminer le code, puis vérifier qu’il est unique dans l’intervalle autorisé. Un élève propose 3, un autre propose 20 ; l’intendant veut trancher par le calcul et non par essais successifs. Il souhaite aussi savoir combien de codes x de l’intervalle [1;22] satisfont 17x ≡ 0 (mod 23), afin de contrôler une éventuelle faiblesse du système.
1. Justifier que 17 et 23 sont premiers entre eux et déterminer des entiers u, v tels que 17u + 23v = 1.
Read the worked answer
Algorithme d’Euclide : 23 = 1×17 + 6 17 = 2×6 + 5 6 = 1×5 + 1 5 = 5×1 + 0. Le dernier reste non nul est 1, donc pgcd(17,23) = 1.
Remontée : 1 = 6 − 5 = 6 − (17 − 2×6) = 3×6 − 17 = 3×(23 − 17) − 17 = 3×23 − 4×17.
Ainsi 17×(−4) + 23×3 = 1. On peut prendre u = −4 et v = 3.
2. En déduire l’inverse de 17 modulo 23, puis résoudre 17x ≡ 5 (mod 23) avec 1 ≤ x ≤ 22. Les propositions 3 et 20 sont-elles acceptables ?
Read the worked answer
L’identité 17×(−4) + 23×3 = 1 donne 17×(−4) ≡ 1 (mod 23). Donc l’inverse de 17 modulo 23 est −4 ≡ 19 (mod 23). Vérification : 17×19 = 323 = 23×14 + 1.
En multipliant 17x ≡ 5 par 19 : x ≡ 5×19 = 95 ≡ 95 − 4×23 = 3 (mod 23). Donc x = 3 est la seule solution dans [1;22].
Vérification : 17×3 = 51 = 2×23 + 5. La proposition 20 donne 17×20 = 340 = 14×23 + 18, donc 17×20 ≡ 18, pas 5. Seul 3 convient.
3. Combien de codes x de [1;22] vérifient 17x ≡ 0 (mod 23) ? Que peut-on en conclure sur la faiblesse évoquée ?
Read the worked answer
Comme pgcd(17,23) = 1, on peut multiplier par l’inverse 19 : 17x ≡ 0 implique x ≡ 0×19 ≡ 0 (mod 23). Les solutions sont donc les multiples de 23. Dans l’intervalle [1;22], il n’y en a aucune : le nombre cherché est 0.
Cela signifie qu’aucun code autorisé n’annule 17 modulo 23 ; le système n’a pas la faiblesse d’un code nul. La congruence 17x ≡ 5 a bien une solution unique modulo 23, et donc un seul code dans l’intervalle imposé.