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 :

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 m1, m2, ... mn sont des entiers ≥2 et premiers deux à deux et si a1, a2,... an sont des entiers quelconques,
alors il existe un entier x unique à une congruence modulo m1m2...mn près, vérifiant simultanément les congruences :
x ≡ a1 modulo m1
x ≡ a2 modulo m2
...
x ≡ an modulo mn

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

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.

q1 ≡ (11×13)-1 ≡ 143-1 ≡ 3-1 ≡ 5 modulo 7
q2 ≡ (7×13)-1 ≡ 91-1 ≡ 3-1 ≡ 4 modulo 11
q3 ≡ (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 pn), p premier impair

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

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 2n)

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

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 pn, 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 pn+1) s'obtiennent à partir d'une solution x0 de x² ≡ a (mod pn) sous la forme x0 + k.pn : (x0 + k.pn)2 = x02 + 2k.x0pn + k2p2n ≡ x02 + 2k.x0pn ≡ a (mod pn+1) puisque 2n>n+1 dès que n>1.
Comme x0² ≡ a (mod pn), ceci se réduit à une congruence modulo p : 2k.x0 ≡ (a - x0²)/pn   (mod p).
D'où la valeur de k et celle de x0 + k.pn.

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 : xn ≡ a (mod p)

Racine primitive

On appelle racine primitive de p, un entier g non multiple de p avec gk ≡ 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 ≡ ak 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, pn, 2pn, p premier impair.
gk ≡ 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

xn ≡ a modulo p, a non multiple de p.
Soit g une racine primitive de p : x ≡ gk modulo p et a ≡ gh modulo p.
gn.k ≡ gh modulo p où k est la nouvelle inconnue.
Et donc  n.k ≡ h modulo p-1  (Puisque ap-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 ≡ gh modulo p.

Exemple : x10 ≡ 43 modulo 97
Il faut tout d'abord chercher une racine primitive de 97
φ(97) = 96 = 25×3, le test de g porte alors sur gφ(m)/p = g48 et g32
216 ≡ 61 modulo 97 et donc 232 ≡ 35 et 2481
316 ≡ 61 modulo 97 et donc 3 ne convient pas non plus
516 ≡ 36 modulo 97 et donc 532 ≡ 35 et 548 ≡ 96
Donc 5 est racine primitive de 97.

Il faut chercher h tel que 5h ≡ 43 modulo 97
Le calcul des puissances successives de 5 donne :
5, 25, 28, 43... et donc 43 = 54 (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 ≡ 510 ≡ 53 modulo 97 et x ≡ 558 ≡ 44 modulo 97.

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Mail English version Sujet précédent Sujet suivant