Congruences

Définitions

Deux nombres de Z sont dits congrus modulo m si leur différence est divisible par m.
On écrit x ≡ y (modulo m).

C'est une relation d'équivalence, c'est à dire que :

• x ≡ x (modulo m)
• x ≡ y (modulo m) implique y ≡ x (modulo m)
• x ≡ y (modulo m) et y ≡ z (modulo m) implique x ≡ z (modulo m)

On peut donc définir des classes d'équivalence. Il y a m classes d'équivalence pour la congruence modulo m.
Un ensemble de m nombres représentant ces classes d'équivalences sera appelé un ensemble de résidus modulo m.
L'ensemble de ces classes d'équivallence est noté Z/mZ, ensemble quotient de Z et des multiples de m.

Un cas particulier important est le cas où m est un nombre premier p :

Si p est un nombre premier Z/pZ est un corps

La condition est d'ailleurs nécessaire car si m est un nombre composé, Z/pZ contient au moins un diviseur de 0, c'est à dire deux entiers a et b non nuls avec a×b ≡ 0 (mod m). Si m est composé, Z/mZ est simplement un anneau.
Tout élement (a) de Z/pZ admet un inverse (a') : (a)×(a') = 1 ou encore a×a' ≡ 1 (mod p)
Si m est composé, (a) admet un inverse si et seulement si PGCD(a,m) = 1.

Résolution de congruences

Soit les équations dans Z/mZ, ou encore f(x) ≡ 0 (mod m).
En particulier le cas ou f(x) est un polynôme P(x) à coefficients dans Z/mZ.

Equation du premier degré a.x ≡ b (mod m)

Ceci s'écrit a.x = b + m.k, où on reconnaît une équation de Diophante que l'on sait résoudre.
Soit p = PGCD(a,m) alors l'équation est soluble si et seulement si p divise b.
Posons a' = a/p, b' = b/p, m' = m/p, l'équation devient a'.x ≡ b' (mod m') avec PGCD(a',m') = 1.
Alors a' admet un inverse (1/a') et x ≡ (1/a')×b' (mod m').
Dans la pratique l'inverse de a' s'obtient par l'algorithme d'Euclide.
Le théorème d'Euler Fermat dit que si a et m premiers entre eux,  a^φ(m) ≡ 1 (mod m)  où φ(m) est l'indicateur d'Euler de m. L'inverse de a est donc  a^φ(m)-1 
Notons que si m est un nombre premier p, l'inverse de a existant toujours, a.x ≡ b (mod p) est toujours soluble. Et φ(p) = p - 1.

Exemple : 14x ≡ 21 (mod 35)
Le PGCD de 14 et 35 est 7, qui divise 21, les solutions sont celles de 2x ≡ 3 (mod 5)
L'inverse de 2 modulo 5 est 3 , donc x ≡ 3×3 ≡ 4 (mod 5)
Et 7 solutions dans Z/35Z : 4, 9, 14, 19, 24, 29, 34.

Théorème des restes chinois

Si m₁, m₂, ... m_n sont des entiers ≥2 et premiers deux à deux et si a₁, a₂,... a_n sont des entiers quelconques,
alors il existe un entier x unique à une congruence modulo m₁m₂...m_n près, vérifiant simultanément les congruences :
x ≡ a₁ modulo m₁
x ≡ a₂ modulo m₂
...
x ≡ a_n modulo m_n

Posons m = m₁m₂...m_n et calculons les inverses q_i ≡ (m/m_i)^-1 modulo m_i
Alors x ≡ ∑q_ia_im/m_i    modulo m
L'application du théorème d'Euler-Fermat donne une formule pour les q_i ≡ (m/m_i)^φ(m_i)-1 modulo m_i
Dans la pratique, on utilise plutôt l'algorithme d'Euclide pour résoudre (m/m_i)×q_i ≡ 1 modulo m_i.

Exemple :
x ≡ a modulo 7
x ≡ b modulo 11
x ≡ c modulo 13
7, 11 et 13 étant premiers deux à deux (et même premiers tout court), on obtient un x unique à une congruence modulo 7×11×13 = 1001 près.

q₁ ≡ (11×13)^-1 ≡ 143^-1 ≡ 3^-1 ≡ 5 modulo 7
q₂ ≡ (7×13)^-1 ≡ 91^-1 ≡ 3^-1 ≡ 4 modulo 11
q₃ ≡ (7×11)^-1 ≡ 77^-1 ≡ 12^-1 ≡ 12 modulo 13

x ≡ a×5×11×13 + b×4×7×13 + c×12×7×11 ≡ 715a + 364b + 924c modulo1001

Equation du second degré a.x² + b.x + c ≡ 0 (mod m)

Si p = PGCD(a,m) : a'.p.x² + b.x + c ≡ 0 (mod (m'.p))
Une condition nécessaire est alors b.x + c ≡ 0 (mod p).
Les solutions de cette équation, une fois substituées dans l'équation de départ donnent une nouvelle équation avec PGCD(a',m') = 1, au besoin en répètant le procédé. Il se termine forcément puisque m' < m.
Par exemple : 6x² + 5x + 16 ≡ 0 (mod 33), PGCD(6,33) = 3, donc 5x + 16 ≡ 0 (mod 3) <=> 2x + 1 ≡ 0 (mod 3)
dont les solutions sont x ≡ 1 (mod 3) ou encore x = 1 + 3k.
Cela donne 6(1 + 3k)² + 15k + 21 ≡ 0 (mod 33) c'est à dire
2(1 + 3k)² + 5k + 7 ≡ 0 (mod 11) ou 18k² + 17k + 9 ≡ 0 (mod 11) c.a.d. 7k² + 6k + 9 ≡ 0 (mod 11)

On peut donc imposer pour la suite PGCD(a,m) = 1.
Il y a donc un inverse a' de a, et en multipliant par a' on obtient x² + b'.x + c' ≡ 0
Notre exemple donne 1/7 = 8 (mod 11) et 7k² + 6k + 9 ≡ 0 (mod 11) <=> k² + 4k + 6 ≡ 0 (mod 11)
Pour achever l'exemple, (k + 2)² + 2 ≡ 0 (mod 11) ou encore y² ≡ 9 (mod 11) => y ≡ ±3 (mod 11).
Cela donne en remontant les calculs k = y - 2 et
x = 1 + 3k = 3y - 5 ≡  4 et 19 (mod 33) 

Equation du second degré x² + b.x + c ≡ 0 (mod pⁿ), p premier impair

Il y a alors un inverse de 2, 2q = 1 (mod pⁿ) et on peut écrire :
x² + 2q.b.x + c ≡ 0 (mod pⁿ)
soit (x+b.q)² - (b.q)² + c ≡ 0 et en posant y = x + b.q et d = (b.q)² - c :
y² ≡ d (mod pⁿ)

Par exemple : x² + 3x + 5 ≡ 0 (mod 25)
1/2 = 13 (mod 25) et donc :
x² + 3x + 5 ≡ x² + 2×(13×3)x + 5 ≡ x² + 2×14x + 5 ou encore (x+14)² ≡ 14² - 5 ≡ 16 (mod 25)
Les solutions sont alors x + 14 ≡ ± 4 (mod 25) soit x = 7 et 15 mod 25

La multiplication par q = 1/2 est inutile si b est pair = 2b' :
x² + 2b'.x + c ≡ 0 s'écrit directement (x + b')² ≡ b'² - c

Equation du second degré x² + b.x + c ≡ 0 (mod 2ⁿ)

Il n'y a alors pas d'inverse de 2 (mod 2ⁿ) et la méthode précédente ne fonctionne plus si b impair.
Les solutions se cherchent successivement dans les deux familles :

• x pair = 2u, 4u² + 2bu + c ≡ 0 (mod 2ⁿ)
  nécessairement c ≡ 0 (mod 2), c = 2c' soit 2u² + bu + c' ≡ 0 (mod 2^n-1),
  donc bu + c' ≡ 0 (mod 2) et on poursuit comme précédement.

• x impair = 2u + 1, 4u² + 4u + 1 + 2bu + b + c ≡ 0 soit
  nécessairement b + c + 1 ≡ 0 (mod 2), soit c = 2c' - b - 1 et 2u² + (b + 2)u + c' ≡ 0 (mod 2^n-1),
  donc (b + 2)u + c' ≡ 0 (mod 2) et on poursuit comme précédement.

Exemple : x² + 7x + 2 ≡ 0 (mod 8)
1) x = 2u : 4u² + 14u + 2 ≡ 4u² + 6u + 2 ≡ 0 (mod 8)
2u² + 3u + 1 ≡ 0 (mod 4), 3u + 1 ≡ 0 (mod 2), u = 2k + 1
(2k + 1)² + 3k + 4 ≡ (2k + 1)² + k ≡ 0 (mod 2)
4k² + 5k + 1 ≡ k + 1 ≡ 0 (mod 2)
donc k = 2m + 1 et x = 2u = 4k + 2 =  8m + 6 

2) x = 2u + 1 : 4u² + 18u + 10 ≡ 4u² + 2u + 2 ≡ 0 (mod 8)
2u² + u + 1 ≡ 0 (mod 4), u = 2k + 1
(2k + 1)² + k + 1 ≡ 0 (mod 2)
4k² + 5k + 2 ≡ k ≡ 0 (mod 2)
donc k pair = 2m, x= 2u + 1 = 4k + 3 =  8m + 3 

Et deux solutions modulo 8.

Racine carrée x² ≡ a (mod m)

Notons tout d'abord le résultat important :

x² ≡ 1 (mod 2) a une seule solution : x = 1 x² ≡ 1 (mod 4) a deux solutions : x = ± 1 x² ≡ 1 (mod 2n), n>2, a quatre solutions :       x = ± 1 et x = ±(2n - 1 - 1) x² ≡ 1 (mod pn), p premier impair, a deux solutions : x = ± 1

Le même nombre de solutions au maximum existe pour x² ≡ a (mod m)
Sinon, il n'y a pas de solutions du tout.
On définit la notion de résidu quadratique comme étant un nombre pour lequel x² ≡ a (mod m) a une solution.
Plus précisément on se limite aux nombres a premiers avec m, et même aux m de la forme pⁿ, p premier, par l'utilisation du théorème des restes chinois.

Pour en revenir à x² ≡ a (mod m), donnons la méthode sur un exemple : trouvez les carrés se terminant par 329.
x² ≡ 329 (mod 1000). Comme 1000 = 2³×5³ il faut tout d'abord chercher les deux congruences :
x² ≡ 329 ≡ 1 (mod 8) et
x² ≡ 329 ≡ 79 (mod 125)

La première x² ≡ 1 (mod 8) a pour solutions x ≡ ±1 ou ±3 (mod 8)

La seconde x² ≡ 79 (mod 125)est un peu plus dure à résoudre.
Cherchons tout d'abord x² ≡ 79 ≡ 4 (mod 5) dont les solutions sont évidemment x ≡ ±2 (mod 5).
Les solutions de x² ≡ 79 ≡ 4 (mod 25), même si elles sont ici évidentes, mais c'est pour la méthode, s'obtiennent à partir des solutions précédentes ±2 (mod 5) sous la forme ±2 + 5k.
Soit (±2 + 5k)² = 4 ± 20k + 25k² ≡ 4 (mod 25) C'est à dire 20k ≡ 0 (mod 25) ou 4k ≡ 0 (mod 5).
Les solutions de x² ≡ 4 (mod 25) sont alors comme on pouvait s'y attendre x ≡ ±2 (mod 25)
Cherchons alors les solutions de x² ≡ 79 (mod 125) à partir de celles modulo 25 sous la forme ±2 + 25k :
(±2 + 25k)² = 4 ± 100k + 25²k² ≡ 79 (mod 125) ou encore ±100k ≡ 75 (mod 125) c'est à dire ±4k ≡ 3 (mod 5) dont les solutions sont k = ±2 + 5m et donc x = ±2 + 25k = ±52 + 125m.

De façon générale les solutions de x² ≡ a (mod pⁿ⁺¹) s'obtiennent à partir d'une solution x₀ de x² ≡ a (mod pⁿ) sous la forme x₀ + k.pⁿ : (x₀ + k.pⁿ)² = x₀² + 2k.x₀pⁿ + k²p²ⁿ ≡ x₀² + 2k.x₀pⁿ ≡ a (mod pⁿ⁺¹) puisque 2n>n+1 dès que n>1.
Comme x₀² ≡ a (mod pⁿ), ceci se réduit à une congruence modulo p : 2k.x₀ ≡ (a - x₀²)/pⁿ   (mod p).
D'où la valeur de k et celle de x₀ + k.pⁿ.

Les solutions de x² ≡ 329 (mod 8) et de x² ≡ 329 (mod 125) sont alors "combinées" par le théorème des restes chinois pour obtenir les solutions de x² ≡ 329 (mod 1000).
Tout d'abord calculons 1/125 ≡ 5 (mod 8) et 1/8 ≡ 47 (mod 125)
Alors les solutions sont : u×5×125 + v×47×8 (mod 1000)
avec u solution de x² ≡ 329 (mod 8) soit les 4 valeurs ±1 et ±3
et v solution de x² ≡ 329 (mod 125) soit v = ±52
Il y a donc 4×2 = 8 solutions :

1×625 + 52×376 ≡ 177 (mod 1000)
1×625 - 52×376 ≡ 73 (mod 1000)
-1×625 + 52×376 ≡ 927 (mod 1000)
-1×625 - 52×376 ≡ 823 (mod 1000)
3×625 + 52×376 ≡ 427 (mod 1000)
3×625 - 52×376 ≡ 323 (mod 1000)
-3×625 + 52×376 ≡ 677 (mod 1000)
-3×625 - 52×376 ≡ 573 (mod 1000)
(soit en fait deux solutions : 73 et 177 modulo 250)

Il suffit donc de savoir résoudre x² ≡ a (mod p), p premier.
Si pour les valeurs faibles de p ceci est résolu le plus efficacement par essai des (p-1)/2 valeurs entre 1 et (p-1)/2, pour de grandes valeurs de p il existe une méthode plus puissante : l'algorithme de Tonelli et Shanks.

Racine n^ème : xⁿ ≡ a (mod p)

Racine primitive

On appelle racine primitive de p, un entier g non multiple de p avec g^k ≡ 1 modulo p et la plus petite valeur de k est p-1 (l'ordre de g est p-1).
Tout nombre premier p admet une racine primitive (et même plusieurs).
Tout nombre x non multiple de a est alors x ≡ a^k modulo p c'est à dire que tout nombre x non multiple de p est "engendré" par une racine primitive.

Plus généralement, une racine primitive g de m existe si et seulement si m = 2, 4, pⁿ, 2pⁿ, p premier impair.
g^k ≡ 1 modulo m, et le plus petit k (ordre de g) est φ(m), indicateur d'Euler de m.
Il y a alors φ(φ(m)) racines primitives.

Le problème est de trouver une racine primitive.
g n'est pas une racine primitive de m si :
 - PGCD(g,m) ≠ 1
 - ou si p est un facteur premier de φ(m) et g^φ(m)/p ≡ 1 modulo m

La recherche de g peut alors se faire par essai systématique, ou au hasard :

m = 2 : g = 1 m = 4 : g = 3 m = pn ou 2pn : chercher une racine primitive de p      essayer g = 2, 3, 5, 6 (OK dans 80% des cas)      sinon essayer au hasard entre 7 et p-1  Si g n'est pas racine primitive de pn, remplacer g par g + p  Enfin si m = 2pn et g pair, remplacer g par g + pn

Racine n^ème

xⁿ ≡ a modulo p, a non multiple de p.
Soit g une racine primitive de p : x ≡ g^k modulo p et a ≡ g^h modulo p.
g^n.k ≡ g^h modulo p où k est la nouvelle inconnue.
Et donc  n.k ≡ h modulo p-1  (Puisque a^p-1 ≡ 1 modulo p, le calcul sur les exposants se fait modulo p-1).
Ceci est alors une congruence du premier degré que l'on sait résoudre.

Le nombre de solutions de xn ≡ a modulo p est soit 0 soit d = PGCD(n, p-1)

Le problème est donc de trouver une racine primitive g de p, et de trouver h avec a ≡ g^h modulo p.

Exemple : x¹⁰ ≡ 43 modulo 97
Il faut tout d'abord chercher une racine primitive de 97
φ(97) = 96 = 2⁵×3, le test de g porte alors sur g^φ(m)/p = g⁴⁸ et g³²
2¹⁶ ≡ 61 modulo 97 et donc 2³² ≡ 35 et 2⁴⁸ ≡ 1
3¹⁶ ≡ 61 modulo 97 et donc 3 ne convient pas non plus
5¹⁶ ≡ 36 modulo 97 et donc 5³² ≡ 35 et 5⁴⁸ ≡ 96
Donc 5 est racine primitive de 97.

Il faut chercher h tel que 5^h ≡ 43 modulo 97
Le calcul des puissances successives de 5 donne :
5, 25, 28, 43... et donc 43 = 5⁴ (sans qu'il soit besoin de calculer les 96 puissances ! ouf !)

Il reste à résoudre 10.k ≡ 4 modulo 96 soit 5.k ≡ 2 modulo 48 et k = 10 et 58.
Et finalement deux solutions x ≡ 5¹⁰ ≡ 53 modulo 97 et x ≡ 5⁵⁸ ≡ 44 modulo 97.