congruences et leurs propriétés

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 22/09/2020 Orientation générale DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	Arithmétique
Débutants Opérations	MODULO				Glossaire Nombres
INDEX Théorie des nombres	Introduction	Mod 9, 10, 11	Applications	Jeux
	Théorie	Carrés	Propriétés	Calculs
	Parité	7 ^ 7 ^ 7	Carrés et Cubes	Sun Zi
		11¹⁰ = 32 mod 71
	Terminale S	Sommaire de cette page >>> Propriétés des congruences >>> Équations avec les congruences >>> Classes complètes de congruences

Propriétés des CONGRUENCES

Modulo & Résidus

Voir préalablement Base de la théorie

PROPRIÉTÉS DES CONGRUENCES

Même chose

Ces écritures sont équivalentes

a b (mod m)

b a (mod m)

a – b 0 (mod m)

a – b = k.m

b est nommé résidu (ou reste) de a modulo m.

Cette sorte d'égalité est baptisée congruence.

Détermination

Soit a b (mod m)

Voir Tiers exclu

Relation d'équivalence

La relation de congruence modulo m est une relation d'équivalence entre les entiers rationnels, soit:

Réflexivité

a a (mod m)

Pour tout entier a

Symétrie

Si a b (mod m)

Alors b a (mod m)

Transitivité

Si a b (mod m)

et b c (mod m)

Alors a c (mod m)

Multiples

Si m est un multiple de m'

a b (mod m)

a b (mod m')

Si m est un multiple de m', m'', ...

Et m', m'', ... sont deux à deux

premiers entre eux

a b (mod m)

a b (mod m')

a b (mod m'')

etc.

Si a b (mod m)

et c > 0

a.c b.c (mod m)

a.c b.c (mod m.c)

Opérations

Si a b (mod m)	*a + x* *b + x* *(mod m)*
	*a – x* *b – x* *(mod m)*
	*a . x* *b . x* *(mod m)*
	*a . x* *b . x* *(mod m . x*)
Si a b *(mod m)* et d diviseur commun de a et b premier avec m	*a / d* *b / d (mod m)*
Si a + b c *(mod m)*	a *c – b* *(mod m)*
Si a – b c *(mod m)*	a *c + b* *(mod m)*
Si a + b *c + d* *(mod m)*	*a – b* *c – d* *(mod m)*
Si a + b *c + d* *(mod m)*	*a . b* *c . d* *(mod m)*
Si a a' *(mod m)* et b b' *(mod m)*	*a + b* *a' + b'* *(mod m)* *a – b* *a' – b'* *(mod m)* *a . b* *a' . b'* *(mod m)*

Si a b (mod m)

aⁿ bⁿ (mod m)

Si a^p b^p (mod m)

a^p b^p (mod m² )

Si a b (mod m)

Et c d (mod m)

En général

x^a x^b (mod m)

a^c b^d (mod m)

Merci à Dragos Zaharia pour ses remarques pertinentes

Égalités

Si a b (mod 0)

a = b

a.x a.y (mod m) si et seulement si

Si a.x a.y (mod m)

et (a, m) = 1

x y (mod m)

Multi-modulos

x y ( mod m )

x y ( mod m' )

(m m') = 1

x y ( mod m.m' )

x y ( mod m )

x y ( mod m' )

(m m') = c

x y ( mod c )

x y ( mod m_i ) pour i = {1, 2 … r}

si et seulement si

x y ( mod [m₁ , m₂ … m_r ] )

(a, m) = PGCD (a, m); [a, m] = PPCM (a, m)

Fractions (exemples)

2 x 4 1 (mod 7)

Fonctions

Si f(x) est un polynôme à coefficients entiers

a b (mod m)

f(a) f(b) (mod m)

Coin maths

Voir Lois de composition / Anneau

ÉQUATIONS AVEC LES CONGRUENCES

Résolution

a . x b (mod m)

Solution existe si :

b multiple de g.

Si x₀ est une solution

Il y a g solutions :

x = x₀ + k . m / g

g = PGCD (a, m)

On note g le PGCD (2^e lettre) car p est déjà réservé aux nombres premiers.

Exemples

Recherche des cas, par programme, pour lesquels le résidu:

r = (a . x – b) (mod m) = 0

On fixe a, b et m

a	x	b	m	g	r
3	4	5	7	1	0
	11			1	0
	18			1	0
	25			1	0
	32			1	0

Notez

g = PGCD (a, m) = 1

a = 3 et m = 7

sont premiers entre eux

Notez également

Écart entre les x successifs

= 7 = m / g

Solutions possibles

On maintient a = 3 et b = 5

On cherche la première solution en x pour les valeurs de m successives:

a	x	b	m	g	r
3	1	5	2	1	0
	3		4	1	0
	5		5	1	0
	4		7	1	0
	7		8	1	0
	5		10	1	0

Colonne x : première solution.

Colonne m : seules valeurs <10 pour lesquelles il existe une solution.

m = 3 et ses multiples ne marchent pas !

Dans ces cas g = PGCD(a, m) = 3 et 3 ne divise pas b = 5

=> Pas de solution, cela est conforme à notre théorème.

Même recherche

avec a = 25 multiple de b = 5

a	x	b	m	g	r
25	1	5	2	1	0
	2		3	1	0
	1		4	1	0
	1		5	5	0
	5		6	1	0
	3		7	1	0
	5		8	1	0
	2		9	1	0
	1		10	5	0

Voir Calculs (restes chinois)

CLASSES COMPLÈTES DE CONGRUENCES

Classe de résidus

Soit la classe S dans laquelle on trouve les résidus r

avec les propriétés équivalentes suivantes :

*a (mod m)*	donne un résidu unique r de S.
Un seul résidu quelconque r de S	suffit pour définir toute la classe S.
Les résidus r de S, pris deux à deux	sont non congrus modulo m.

Si dans S, on trouve effectivement tous les résidus possibles

(selon l'une des trois propriétés équivalentes ci-dessus)

S est un système complet de résidus modulo m

Suite Retour	Congruences – Exemples de calculs Approche
Voir	Carrés Divisibilité Clé de divisibilité, une application de la théorie du modulo La division Exemple d'application du modulo en Codage RSA
Aussi	Calcul mental Géométrie Nombres Premiers Nombres Rationnels Preuve par 9 – Glossaire Théorie des nombres Variations sur les carrés
Livre	Algèbre 1 – Cours et 600 exercices corrigés – 1^re année MPSI, PCSI, PTSI – Jean-Marie Monier – Dunod – 1996
Site	Congruences dans Z - Spé Maths – J'ai compris.com – Vidéo avec exercices corrigés Chapitre 3 : congruences et arithmétique modulaire Congruence – Wolfram MAthWorld Lecture 3: Congruences Lecture on Number Theory – Lars Ake Lindahl – 2002 – pdf 95 pages
Cette page	http://diconombre.fr/ThNbDemo/ModCongr.htm