Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 25/09/2020

M'écrire

Brèves de Maths

 

INDEX

 

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

1110 = 32 mod 71

 

 

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)

13 ≡ 83 ≡ 1   [7] 

(83  = 512 = 73 x 7 + 1)

Attention

Aucune conclusion sur a ou b

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

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 x0 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.

 

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

*    Géométrie

*    Nombres Premiers

*    Nombres Rationnels

*    Preuve par 9Glossaire

*    Théorie des nombres

*    Variations sur les carrés

Livre

*      Algèbre 1 – Cours et 600  exercices corrigés – 1re 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