on considere deux entiers naturelsa et b . Pour tout entier n, on note q(n) le reste de la division euclidienne de an+b par 26.On décide de coder un message,en procédant comme suit:à chaque lettre de l'alphabet on associe un entier compris entre 0 et 25 selon le tableau:
lettre:ABCDefghijklmnopqrstuvwxyz
nombre:012345678910111213141516171819202122232425
Pour chaque lettre x du message ,on determine l'entier n associé puis on calcule q(n). La lettre x est alors codée par la lettre associée à q(n).
On ne connait pas les entiers a et b, mais on sait que la lettre f est codée par la lettre k et la lettre t est codée par la lettre o.
a) montrer que les entiers a et b sont tels que: 5a + b congru à 10 modulo 26
19a + b congru à 14 modulo 26
b) en déduire qu'il existe un entier k tel que 14a-26k=4
c) déterminer tous les couples d' entiers (a,b),avec 0 inférieurou égal à a inférieur ou égal à 25 et 0 inférieur ou égal à b inférieur ou égal à 25, tels que: 5a+b congru à 10 modulo 26
19a+b congru à 14 modulo 26

Réponse de nos Cyberprofs

Bonjour Bertrand,

La principale chose que tu dois avoir comprise pour pouvoir faire cette exercice c'est ce que signifie « congru à ». Quand on écrit « modulo 26 » cela signifie que le résultat est donné à 26 fois un entier près. Autrement dit lorsque tu écris 5a + b ~= 10 [26] (le ~= veut dire congru à et les crochet veulent dire « modulo ») cela est équivalent à écrire 5a + b = 10 + 26i avec i qui est un entier naturel quelconque. Tous les nombres qui valent 10 plus un multiple de 26 sont égaux dans la classe de congruence modulo 26. Si tu comprend bien cela tu peux faire tout ton exercice.

Je reprend les questions dans l'ordre :

a) la première question ne sert qu'à t'aider à comprendre le système de codage utilisé. On te dit dans l'énoncé que f est codé par k. D'après le tableau f est associé à 5 et k est associé à 10. Pour coder f on te dit que l'on écrit n.a + b = 5a + b pour f, puis que l'on fait la division euclidienne de 5a + b par 26 pour en trouver le reste q(n). C'est-à-dire que l'on calcul (5a + b)/26 = i + q(n)/26 avec i qui est un entier naturel. Le reste q(n) est égal à 10 dans le codage de f puisque l'on te dit que f est codé par k. Le codage impose donc que l'on puisse écrire 5a + b = 10 + 26.i avec i entier naturel c'est-à-dire que 5a + b ~= 10 [26]. Tu n'as plus qu'à faire le même raisonnement sur le codage de t et tu trouveras la deuxième relation que l'on te demande.
b) Comme je te l'ai dit en introduction tu peux toujours écrire que 5a + b ~= 10 [26] est équivalent à 5a + b = 10 + 26.i . Tu peux de la même façon écrire que 19a + b = 14 + 26.j avec j un autre entier naturel pas forcément égal à i. Tu as désormais deux équations classiques avec lesquelles il est facile de travailler :
5a + b = 10 + 26.i (1)
19a + b = 14 + 26.j (2)
si tu écris la soustraction de (2)-(1) tu obtiens alors 14a = 4 + 26(j-i) et comme j et i sont des entiers naturels, tu peux écrire que j-i = k où k est un entier.
c) avec la question précédente tu as maintenant une expression de a en fonction de k. Tu sais que a dois être inférieur à 25 en écrivant cette inégalité avec l'expression de a en fonction de k tu trouves facilement que tu dois avoir k<13. Il ne te reste alors qu'à essayer toutes les valeurs de k comprises entre 0 et 13 pour trouver celle qui permettent d'avoir une valeur entière pour a. Tu dois trouver deux valeurs de k. Une de ces valeurs est k=2 ce qui donne a = (2+13k)/7 = 28/7 = 4 . Avec a = 4 tu peux maintenant réécrire le codage de f pour trouver la valeur de b : il faut que tu puisses avoir 5a + b = 10 + 26i avec a = 4 ce qui te donne b = -10 + 26i. Comme b dois être inférieur à 26 cela impose une unique valeur de i qui est i=1 donc b=16. Tu peux vérifier que le couple a=4 et b=16 marche bien en recalculant le codage de t. Tu trouves alors bien que 19a + b = 14 + 26j avec j qui vaut 3.
Tu dois faire exactement la même chose avec la deuxième valeur possible de k que je te laisse trouver?

Voila, j'espère que cela t'aidera et que tu comprends un peu mieux les classes de congruence.

A bientôt Bertrand