Sommaire

Mes pages

Ouverture

p. 1-11

Nombres complexes

Ch. 1
Nombres complexes, point de vue algébrique

Ch. 2
Nombres complexes, point de vue géométrique

Arithmétique

Ch. 3
Divisibilité dans Z

Testez le chapitre 100 % débloqué

Ch. 4
PGCD et applications

Ch. 5
Nombres premiers

Graphes et matrices

Ch. 6
Calcul matriciel et applications aux graphes

Ch. 7
Suites et matrices

Annexes

Exercices transversaux

Exercicesp. 238-243

Se préparer au Grand Oral

Grand oral

Présentation du Grand Oral

Grand oral

Conseils pour le Grand Oral

Méthode

Cahier d'algorithmique et de programmation

Page précédente

Chapitre 3

Cours 3

Congruences

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

A
Définition

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Définition

Soient

m

un entier naturel non nul, et

a

b

deux entiers relatifs.
On dit que

a

b

sont congrus modulo

m

lorsqu'ils ont le même reste dans la division euclidienne par

m

.
On dit aussi que

a

est congru à

b

modulo $m$ .

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Notation

On note

a \equiv b [m]

;

a \equiv b (m)

a \equiv b mod m

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemple

15 = 2 \times 7 + 1

21 = 2 \times 10 + 1

donc

15 \equiv 21 [2]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Théorème

Soient

m

un entier naturel non nul et

a

b

deux entiers relatifs.

a \equiv b [m]

si, et seulement si,

m ∣ (a - b)

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Remarque

En particulier, si

a \equiv 0 [m]

, alors

m ∣ a

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Démonstration

Voir exercice

p. 109.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

B
Congruences et opérations

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Propriété

Soient

a

b

c

trois entiers relatifs et

m

un entier naturel non nul.
Si

a \equiv b [m]

b \equiv c [m]

, alors

a \equiv c [m]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Remarque

On dit que la relation de congruence est transitive.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Démonstration

D'après les hypothèses,

a

b

ont le même reste dans la division euclidienne par

m

, et

b

c

ont le même reste dans la division euclidienne par

m

, donc

a

c

ont le même reste dans la division euclidienne par

m

donc

a \equiv c [m]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemple

251 \equiv 8 [3]

8 \equiv 2 [3]

donc

251 \equiv 2 [3]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Propriété

Soient

a

b

c

d

quatre entiers relatifs et

m

un entier naturel non nul.
1. Compatibilité avec l'addition
Si

a \equiv b [m]

c \equiv d [m]

, alors

a + c \equiv b + d [m]

.

2. Compatibilité avec la multiplication
Si

a \equiv b [m]

c \equiv d [m]

, alors

a \times c \equiv b \times d [m]

.

3. Compatibilité avec les puissances
Soit

p

un entier naturel non nul. Si

a \equiv b [m]

, alors

a^{p} \equiv b^{p} [m]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Cas particuliers

c \equiv c [m]

donc, si

a \equiv b [m]

, alors

a + c \equiv b + c [m]

a \times c \equiv b \times c [m]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Attention

Il n'y a pas de compatibilité avec la division :

62 \equiv 26 [4]

mais

31

13

ne sont pas congrus modulo

4

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Démonstration

Voir exercice

p. 109.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Application et méthode - 5

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Énoncé

Montrer en utilisant un tableau de congruence que, pour tout entier relatif

n

n (n + 1) (2 n + 1)

est divisible par

3

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Méthode

On recherche les restes possibles de

n

dans la division par

3

(conséquence de la division euclidienne).
On complète le tableau de congruence pour obtenir, dans la dernière ligne, les restes possibles de la division de

n (n + 1) (2 n + 1)

par

3

. Ces restes étant toujours nuls, on en déduit que, pour tout entier

n

n (n + 1) (2 n + 1)

est divisible par

3

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Solution

On dresse un tableau de congruence de

n

modulo 3.

$n \equiv \dots [3]$	$0$	$1$	$2$
$(n + 1) \equiv \dots [3]$	$1$	$2$	$3 \equiv 0$
$(2 n + 1) \equiv \dots [3]$	1	$3 \equiv 0$	$5 \equiv 2$
Produit $n (n + 1) (2 n + 1)$ $\equiv \dots [3]$	$0 \times 1 \times 1 \equiv 0$	$1 \times 2 \times 0 \equiv 0$	$2 \times 0 \times 2 \equiv 0$

On remarque que, pour tout entier

n

n (n + 1) (2 n + 1) \equiv 0 [3]

, c'est‑à‑dire que

n (n + 1) (2 n + 1)

est divisible par

3

Pour s'entraîner

Exercices

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

C
Inverse modulo $m$

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Définition

Soient

a

un entier relatif et

m

un entier naturel non nul.
On dit que

a

est inversible modulo

m

lorsqu'il existe un entier

b

tel que

a \times b \equiv 1 [m]

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemple

8

est inversible modulo

3

car

8 \times 2 \equiv 1 [3]

2

est donc un inverse de

8

modulo

3

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Application et méthode - 6

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Énoncé

1. Démontrer que

3

est inversible modulo

5

.
2. Montrer que

4

n'admet pas d'inverse modulo

6

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Méthode

1. On recherche un entier

b

tel que

3 b \equiv 1 [5]

.
Pour cela, on établit un tableau de congruence modulo

5

, en recherchant les restes possibles de

3 b

modulo

5

. Dans le tableau, on recherche s'il existe un entier

b

tel que

3 b \equiv 1 [5]

. Dans ce cas, on observe que l'entier

2

est une solution.

2. On établit un tableau de congruence modulo

6

. On observe que

4 c

n'est jamais congru à

1

modulo

6

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Solution

1. Soit

b

un entier relatif. On établit un tableau de congruence modulo

5

$b \equiv \dots [5]$	$0$	$1$	$2$	$3$	$4$
$3 b \equiv \dots [5]$	$0$	$3$	$1$	$4$	$2$

On a donc

3 \times 2 \equiv 1 [5]

donc

2

est un inverse de

3

modulo

5

.
Cet inverse n'est d'ailleurs pas unique : tout entier s'écrivant

5 k + 2

, avec

k \in Z

, est un inverse de

3

modulo

5

.

2. Soit

c

un entier relatif. On établit un tableau de congruence modulo

6

$c \equiv \dots [6]$	$0$	$1$	$2$	$3$	$4$	$5$
$4 c \equiv \dots [6]$	$0$	$4$	$2$	$0$	$4$	$2$

Il n'existe pas d'entier

c

tel que

4 c \equiv 1 [6]

Donc

4

n'admet pas d'inverse modulo

6

Pour s'entraîner

Exercices

p. 105.

Page suivante

Une erreur sur la page ? Une idée à proposer ?

Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.

j'ai une idée !

Oups, une coquille

Ch. 1 Nombres complexes, point de vue algébrique

Ch. 2 Nombres complexes, point de vue géométrique

Ch. 3 Divisibilité dans Z

Ch. 4PGCD et applications

Ch. 5 Nombres premiers

Ch. 6Calcul matriciel et applications aux graphes

Ch. 7Suites et matrices

Cahier d'algorithmique et de programmation

Congruences

A Définition

Notation

Remarque

B Congruences et opérations

Remarque

Cas particuliers

Attention

Méthode

C Inverse modulo m

Méthode

Une erreur sur la page ? Une idée à proposer ?

Ch. 1
Nombres complexes, point de vue algébrique

Ch. 2
Nombres complexes, point de vue géométrique

Ch. 3
Divisibilité dans Z

Ch. 4
PGCD et applications

Ch. 5
Nombres premiers

Ch. 6
Calcul matriciel et applications aux graphes

Ch. 7
Suites et matrices

A
Définition

B
Congruences et opérations

C
Inverse modulo $m$