congruences et leurs propriétés

Édition du: 16/01/2023

INDEX Structures algébriques Théorie des nombres Types de nombres	Arithmétique – Modulo
	Introduction	Théorie		Propriétés	Formulaire
	Applications	Calculs		Carrés	Cubes
	Jeux	Sun Zi		Mod 9, 10, 11	Carrés et Cubes
	Parité	7 ^ 7 ^ 7		Log Modulaire	11¹⁰ = 32 mod 71
	Classes de congruence		Ensemble quotient
	N = 1 mod k (k = 2, 3,…)

CONGRUENCES – Propriétés

Arithmétique modulaire: les principales propriétés avec explications

Terminale S

Sommaire de cette page

>>> Bases

>>> Propriétés principales
>>> Relation d'équivalence

>>> Formules classiques

>>> Propriété d'addition et de multiplication

>>> Cas de la puissance – Démonstration

>>> Équations avec les congruences

>>> Classes complètes de congruences

Débutants

Opérations

Glossaire

Nombres

Voir préalablement Base de la théorie

Notations et conventions

Voir Entiers / Entiers Relatifs / PGCD / PPCM / SSI

BASES

haut

Définition

Si a b (mod m)

alors

a – b 0 (mod m)

a et b, divisés par m, ont le même reste.

Ex: 11 mod 5 = 1, 6 mod 5 = 1

=> 11 ≡ 6 mod 5 et 11 – 6 = 5 ≡ 0 mod 5

Reste

SSI

r est le reste de la division euclidienne de a par b.

Propriété

a b (mod m)

SSI a (mod m) b (mod m)

Remplacement

Dans une ADDITION ou une MULTIPLICATION (mod m), on peut remplacer un nombre par un autre égal modulo m.

On peut additionner ou soustraire ou multiplier par un MÊME NOMBRE de chaque côté d'une égalité mod m.

On peut élever à une PUISSANCE de chaque côté d'une égalité mod m (mais pas l'inverse: réciproque fausse).
Attention: ne pas travailler en modulo sur les exposants.

En général, on ne peut pas DIVISER avec les congruences.

Principales propriétés			haut
Écritures équivalentes	Le nombre a est la base, b est nommé résidu (ou reste) de a modulo m. Cette sorte d'égalité est baptisée congruence.	a – b 0 (mod m) a – b = k.m
Indication implicite	L'indication du modulo en fin de ligne est valable pour toute la ligne.
Détermination	Tiers exclu	Soit a b [m] Soit a b [m]

Relation d'équivalence		haut
Congruence	La relation de congruence modulo m est une relation d'équivalence entre les nombres rationnels.

Formules classiques			haut
Hypothèses	Ces hypothèses impliquent les relations suivantes:	Exemples 1 ≡ 8 [7] et 3 ≡ 10 [7] Avec k = 2.
Translation		1 + 2 ≡ 8 + 2 ≡ 3 [7] 1 – 2 ≡ 8 – 2 ≡ –1 ≡ 6 [7] (Rappel: –1 + 7 = 6)
Changement d'échelle		1 x 2 ≡ 8 x 2 ≡ 2 [7] 1 x 2 ≡ 8 x 2 ≡ 2 [14]
Addition mutuelle		1 + 3 ≡ 8 + 10 ≡ 4 [7] 1 – 3 ≡ 8 – 10 ≡ –2 ≡ 5 [7]
Multiplication mutuelle		1 x 3 ≡ 8 x 10 ≡ 3 [7] (80 = 11 x 7 + 3)
Puissance (k > 0)		1³ ≡ 8³ ≡ 1 [7] (8³ = 512 = 73 x 7 + 1)
		9³ ≡ 8³ ≡ 1 mod 7 or: 9 ≡ 2 mod 7 et 8 ≡ 1 mod 7

Astuce ! Avec cet exemple

Attention

Aucune conclusion sur a ou b

(a n'est pas nul mod m, ni b)

Modulaire inverse u de a

2 x 17 ≡ 1 [33]

17 ≡ 2^-1 [33] >>>

Voir Formulaire complet sur les congruences

Coin maths – Propriété d'addition et de multiplication

Voir Lois de composition / Anneau

Cas de la puissance – Démonstration

Équations avec les congruences

haut

Résolution

On note: g = PGCD (a, m)

Il existe une solution si b est un multiple de g.

Si x₀ est une solution, il y a g solutions :

Exemples

Solutions de

g = 1 => il existe des solutions

Elles sont toutes en x = 4 + 7k

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

Variantes sur le modulo

On fait varier m en maintenant a et b.

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

Pour m de 2 à 10, il n'existe pas de solution pour 3, 6 et 9, multiples de a.

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

Variantes avec b

On fixe a = 5 et b = 5a

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				haut
Même famille	Avec le modulo 5, par exemple, les nombres entiers positifs sur la même ligne du tableau ont tous le même reste dans la division par 5. Pour représenter tous les nombres en mod 5, il suffit de conserver la colonne des nombres en rouge. Cette classe des résidus mod 5 se note:		On peut étendre le tableau aux nombres relatifs (Z)
Classe d'équivalence	L'ensemble des nombres est partitionné en 5 (notre exemple). Ce sont cinq classes d'équivalence. L'ensemble des classes d'équivalence se nomme l'ensemble quotient de ℕ par R = mod 5.
Propriétés	Soit la classe S dans laquelle on trouve les résidus r. On a 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.

Voir Suite sur les classes de congruences

English corner

Suite Retour	Congruences – Exemples de calculs Congruence – Formules 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 Cribles – Tous les types 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 sur les entiers - Wikipédia Congruence – Wolfram MathWorld Lecture 3: Congruences Lecture on Number Theory – Lars Ake Lindahl – 2002 – pdf 95 pages
Cette page	http://villemin.gerard.free.fr/ThNbDemo/ModCongr.htm