Pourquoi ne peut-on pas toujours simplifier une congruence par un facteur commun ?

Réponse courte

Annuler un facteur c dans cx ≡ cy [n] sans condition peut faire perdre des solutions. On peut le supprimer en gardant le module n si c et n sont premiers entre eux ; sinon, il faut réduire le module.

Comprendre

Une congruence conserve l’information du module

L’écriture cx ≡ cy [n] signifie que n divise c(x − y). Diviser les deux membres par c ne garantit pas que n divise encore x − y : une partie de la divisibilité pouvait provenir du facteur c. L’annulation est sûre à module inchangé lorsque c et n sont premiers entre eux.

Ce qui se passe dans un exemple

La congruence 2x ≡ 2 [6] équivaut à 6 | 2(x − 1). En divisant les deux membres de cette divisibilité par 2, on obtient 3 | x − 1, donc x ≡ 1 [3]. Les solutions sont x = 1 + 3k. Modulo 6, elles ont deux restes possibles : 1 et 4 ; conclure x ≡ 1 [6] oublierait notamment 4.

Règle générale pour annuler

Pour c non nul, pose d = pgcd(c, n). De cx ≡ cy [n], on peut déduire x ≡ y [n/d], et ce module réduit décrit exactement les solutions. Si d = 1, le module reste n et l’annulation habituelle est valide. Par exemple, 3x ≡ 3y [10] permet d’annuler 3 modulo 10, car pgcd(3, 10) = 1. Vérifie toujours le PGCD avant de simplifier.

Exemples

  • 2x ≡ 2 [6] équivaut à x ≡ 1 [3] ; les restes modulo 6 sont 1 et 4.
  • 3x ≡ 3y [10] permet d’annuler 3, car pgcd(3, 10) = 1 ; on obtient x ≡ y [10].

Pièges fréquents

  • Passer de 2x ≡ 2 [6] à x ≡ 1 [6] : cette écriture exclut la solution x = 4, qui vérifie pourtant la congruence de départ.
  • Croire qu’on ne peut jamais annuler : si le facteur est premier avec le module, son inverse modulo n existe et l’annulation conserve le module.

Et maintenant ?

Questions proches

← Toutes les questions-réponses