Question sur l'inverse modulaire

[invitedd654e81]

Bonjour, j'ai des troubles avec un exercice qui concerne l'inverse modulaire, je vais vous expliquer tout de suite.

D'abord, voici un exercice que j'ai fait tout a l'heure:

Question : Démontrez que 937 est un inverse de 13 mod 2436

Réponse: La démarche que j'utilise est de trouver le pgcd de 13 et 2436, qui est 1, grâce a l'algorithme d'euclide. Ensuite j'exprime 1 comme combinaison linéaire de 13 et 2436 en ''remontant'' l'algorithme d'euclide, et je réussis a obtenir que 1 = 937*13 - 5*2436 , et j'en conclut que 937 est bien un inverse de 13 mod 2436, car c'est le coéficient de 13 dans la combinaison linéaire du pgcd.

Maintenant l'exercice dans lequel je suis bloqué :

Question : Démontrez qu'un inverse de a mod m n'existe pas si pgcd(a,m) > 1.

Réponse : Eh ben y en a pas encore, je suis bloqué là. Jusqu'a présent j'ai écris que s*a + t*m > 1 , sa+tm étant la combinaison linéaire du pgcd de a et m exprimé en fonction de a et m, s et t étant les coéfficients, et s qui devrait être l'inverse. Il faut ici que je démontre que s ne peut exister, mais comment ?

En passant, ceci n'est pas un devoir, c'est une révision que je fais donc je ne demande pas que l'on travaille à ma place, je veux juste un peu d'aide s.v.p.
-----

[Médiat]

Bonsoir,

Il vous suffisait de calculer 937 * 13 mod 2436.

Pour la deuxième question, si a et m on un facteur commun > 1, tous les produits de a auront aussi ce facteur en commun ...

[invitedd654e81]

médiat:

Merci pour votre réponse:

1- 13*937 n'est pas divisible par 2436, mais 13*937-1 l'est, vouliez-vous dire qu'il fallait trouver que 13*937 est congru a 1 modulo 2436 ?
2- Je n'ai pas du tout compris... Pouvez-vous donner un exemple ?

[Médiat]

1- 13*937 n'est pas divisible par 2436, mais 13*937-1 l'est, vouliez-vous dire qu'il fallait trouver que 13*937 est congru a 1 modulo 2436 ?

Oui, puisque c'est la définition de l'inverse modulaire.

2- Je n'ai pas du tout compris... Pouvez-vous donner un exemple ?

Si a = kd et m = k'd, vous pouvez multiplier a par n'importe quel entier, vous ne trouverez jamais quelque chose de la forme k"m + 1 (il suffit d'étudier le reste modulo d des multipls de a et de k"m + 1)

[A voir en vidéo sur Futura]

[invitedd654e81]

Pour la première question c'est bon.

2- Votre d s'agit bien du pgcd de a et m n'est-ce pas ? Mais pourquoi est-ce qu'on ne pourra jamais avoir un résultat de la forme k''m+1 si on multiplie a par un entier ? Les multiples de a auront toujours la forme xkd avec x entier, et d sera donc toujours un diviseur, je comprends ça, mais quel est le rapport avec l'inverse modulaire ?

[Médiat]

Bonjour,

Pour que x soit l'inverse modulaire de a (modulo m) il faut que xa soit congru à 1 modulo m, c'est à dire de la forme k"m + 1

[invitedd654e81]

Ah d'accord, c'est bon merci

[invitecb373bbe]

L'algorithme d'Euclide peut être utile pour calculer l'inverse de 13 (mod 2436) si on ne connaît pas celui-ci :

On cherche deux entiers x et y tels que 13x + 2436y = 1 (possible puisque 13 et 2436 sont relativement premiers)

On a successivement :
_______ x ___ y
1) 2436__0____1
2) 13____1____0 (1ère ligne moins 187 fois la 2ème)
3) 5___-187___1 (2ème ligne moins 2 fois la 3ème)
4) 3____375__-2 (3ème ligne moins 1 fois la 4ème)
5) 2___-562___3 (4ème ligne moins la 5ème)
6) 1____937__-5 (5ème ligne moins 2 fois la 6ème)
7) 0____FIN algorithme

On obtient bien 13*937 + 2436 *(-5) = 1, donc 937 est bien l'inverse de 13 (mod 2436)