CHAPITRE
Accueil
Exercices
Fiches de cours
NON COMMENCÉ
0 pts
Imprimer
Formules et Théorèmes
Démonstrations
À savoir refaire
1
Divisibilité
2
Division euclidienne et congruence
3
PGCD
4
Nombres premiers
2
Division euclidienne et congruence
A
Théorème de la division euclidienne
Théorème
Théorème de la division euclidienne
Soit
a
a
a
un entier relatif et
b
b
b
un entier naturel.
Il existe un unique couple (
q
q
q
,
r
r
r
) avec
q
q
q
et
r
r
r
entiers naturels, tel que :
a
=
b
q
+
r
a=bq+r
a
=
b
q
+
r
avec
0
≤
r
<
b
0 \leq r < b
0
≤
r
<
b
.
Il s’agit de la division euclidienne de
a
a
a
par
b
b
b
.
On note
a
a
a
le dividende,
b
b
b
le diviseur,
q
q
q
le quotient et
r
r
r
le reste.
Remarque
Il s’agit simplement de la division telle qu’on la connaît !
Exemple
La division euclidienne de
5
4
54
5
4
par
2
1
21
2
1
est :
5
4
=
2
×
2
1
+
2
54=2 \times 21+2
5
4
=
2
×
2
1
+
2
.
Le dividende est
5
4
54
5
4
, le diviseur est
2
1
21
2
1
, le quotient est
2
2
2
et le reste est
2
2
2
.
B
Congruence
Définition
Congruence
Soit
n
n
n
un entier naturel supérieur à
2
2
2
, et
a
a
a
et
b
b
b
deux entiers relatifs.
Si
a
a
a
et
b
b
b
ont le même reste par la division euclidienne par
n
n
n
, alors
a
a
a
et
b
b
b
sont congrus modulo
n
n
n
.
On écrit alors :
a
≡
b
[
n
]
a\equiv b \ [n]
a
≡
b
[
n
]
qui se lit : «
a
a
a
est congru à
b
b
b
modulo
n
n
n
».
Théorème
1er théorème sur la congruence
a
a
a
est congru à
b
b
b
modulo
n
n
n
si et seulement si
a
−
b
a-b
a
−
b
divise
n
n
n
.
Cela s'écrit :
a
≡
b
[
n
]
a\equiv b \ [n]
a
≡
b
[
n
]
⇔
\Leftrightarrow
⇔
a
−
b
∣
n
a-b \mid n
a
−
b
∣
n
.
Propriété
Propriétés de la congruence
La congruence est :
réfléxive :
∀
a
∈
Z
\forall a\in Z
∀
a
∈
Z
,
∀
n
∈
N
\forall n \in N
∀
n
∈
N
,
a
≡
a
[
n
]
a\equiv a \ [n]
a
≡
a
[
n
]
;
symétrique :
si
a
≡
b
[
n
]
a\equiv b \ [n]
a
≡
b
[
n
]
, alors
b
≡
a
[
n
]
b \equiv a \ [n]
b
≡
a
[
n
]
;
transitive :
si
a
≡
b
[
n
]
a\equiv b \ [n]
a
≡
b
[
n
]
et
b
≡
c
[
n
]
b\equiv c \ [n]
b
≡
c
[
n
]
, alors
a
≡
c
[
n
]
a \equiv c \ [n]
a
≡
c
[
n
]
.
Propriété
Si
a
=
b
n
+
r
a=bn+r
a
=
b
n
+
r
, alors
a
≡
r
[
n
]
a \equiv r \ [n]
a
≡
r
[
n
]
.
Théorème
2nd théorème sur la congruence
Soient
a
a
a
,
b
b
b
,
c
c
c
et
d
d
d
4 entiers relatifs et
n
n
n
un entier naturel, tels que
a
≡
b
[
n
]
a \equiv b \ [n]
a
≡
b
[
n
]
et
c
≡
d
[
n
]
c \equiv d \ [n]
c
≡
d
[
n
]
.
On a :
a
+
c
≡
b
+
d
a+c \equiv b+d
a
+
c
≡
b
+
d
[
n
]
[n]
[
n
]
et
a
−
c
≡
b
−
d
a - c \equiv b - d
a
−
c
≡
b
−
d
[
n
]
[n]
[
n
]
a
×
c
≡
b
×
d
a \times c \equiv b \times d
a
×
c
≡
b
×
d
[
n
]
[n]
[
n
]
∀
k
∈
N
,
a
k
≡
b
k
[
n
]
\forall k \in N, a^{k} \equiv b^{k} \ [n]
∀
k
∈
N
,
a
k
≡
b
k
[
n
]
Exemple
Pour déterminer le modulo
7
7
7
de
5
0
50
5
0
:
la division euclidienne de
5
0
50
5
0
par
7
7
7
donne
5
0
=
7
×
7
+
1
50 = 7 \times 7+1
5
0
=
7
×
7
+
1
. Donc le reste de la division euclidienne de
5
0
−
1
50-1
5
0
−
1
par
7
7
7
est nul.
D’après le théorème 1),
4
9
≡
0
[
n
]
49 \equiv 0 \ [n]
4
9
≡
0
[
n
]
or
1
≡
1
[
n
]
1 \equiv 1 \ [n]
1
≡
1
[
n
]
, donc par la propriété 1) du théorème 2),
5
0
≡
[
7
]
50 \equiv \ [7]
5
0
≡
[
7
]
.
Pour déterminer le reste de la division euclidienne de
4
9
1
2
0
49^{120}
4
9
1
2
0
par
6
6
6
:
on a
4
9
=
8
×
6
+
1
49 = 8 \times 6 +1
4
9
=
8
×
6
+
1
donc
4
9
≡
1
[
6
]
49 \equiv 1 [6]
4
9
≡
1
[
6
]
.
Donc, avec la propriété 3) du 2nd théorème sur la congruence,
4
9
1
2
0
≡
1
1
2
0
49^{120} \equiv 1^{120}
4
9
1
2
0
≡
1
1
2
0
, soit
4
9
1
2
0
≡
1
[
6
]
49^{120} \equiv 1 [6]
4
9
1
2
0
≡
1
[
6
]
.
Le reste vaut donc
1
1
1
.
M'inscrire
Me Connecter
Afterclasse Premium
Objectifs du jour :
0/3
Découvrir
Niveau 3ème >
Français
Histoire
Géographie
Mathématiques
SVT
Physique-Chimie
Espagnol
Mentions légales
Mes enfants
Mes classes
créer une nouvelle classe
Fermer
6ème
5ème
4ème
3ème
2nde
Première
Terminale
Mon Profil
remplacer
Nom d'utilisateur
Prénom
Nom
Date de naissance
Niveau
6ème
5ème
4ème
3ème
2nde
Première
Terminale
Email
Email des Parents
Enregistrer
Changer mon mot de passe
Mon Profil
remplacer
Prénom
Nom
Matière
Allemand
Anglais
Arts plastiques
Espagnol
Français
Histoire-Géographie
Mathématiques
Musique
Philosophie
Physique-Chimie
SES
SVT
Email
Enregistrer
Changer mon mot de passe
Mon Profil
remplacer
Prénom
Nom
Email
Enregistrer
Changer mon mot de passe
Utilisation des cookies
Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.