MetMat
Chapitres
S'abonner
Qui sommes-nous
FAQ
Connexion
S'inscrire
Arithmétique : Divisibilité et PGCD — cours et méthodes maths expertes | MetMat
Méthodes
›
Terminale Spécialité Maths + Maths Expertes
Terminale Spécialité Maths + Maths Expertes
Arithmétique : Divisibilité et PGCD
Division euclidienne, diviseurs, PGCD par l'algorithme d'Euclide et théorème de Bézout.
Maîtriser
Reconnaître
Résoudre
0/9 maîtrisées
1
Maîtriser
Comment déterminer les diviseurs d'un entier et établir des critères de divisibilité ?
En testant les entiers de
1
1
1
à
⌊
n
⌋
\lfloor\sqrt{n}\rfloor
⌊
n
⌋
: si
d
d
d
divise
n
n
n
, alors
n
/
d
n/d
n
/
d
aussi
Nouveau
En établissant un critère de divisibilité via les congruences (ex. :
n
≡
0
(
m
o
d
3
)
n \equiv 0 \pmod{3}
n
≡
0
(
mod
3
)
ssi la somme des chiffres de
n
n
n
est divisible par
3
3
3
)
Nouveau
Comment effectuer une division euclidienne ?
Nouveau
Comment calculer le PGCD de deux entiers ?
Nouveau
Comment exprimer le PGCD sous la forme de Bézout
a
u
+
b
v
au + bv
a
u
+
b
v
?
Nouveau
Comment résoudre une congruence
a
x
≡
b
(
m
o
d
n
)
ax \equiv b \pmod{n}
a
x
≡
b
(
mod
n
)
?
En posant
d
=
p
g
c
d
(
a
,
n
)
d = \mathrm{pgcd}(a,n)
d
=
pgcd
(
a
,
n
)
: l'équation admet des solutions ssi
d
∣
b
d \mid b
d
∣
b
; on divise alors par
d
d
d
et on résout
a
′
x
≡
b
′
(
m
o
d
n
′
)
a'x \equiv b' \pmod{n'}
a
′
x
≡
b
′
(
mod
n
′
)
avec
a
′
=
a
/
d
a'=a/d
a
′
=
a
/
d
,
b
′
=
b
/
d
b'=b/d
b
′
=
b
/
d
,
n
′
=
n
/
d
n'=n/d
n
′
=
n
/
d
, en trouvant l'inverse de
a
′
a'
a
′
modulo
n
′
n'
n
′
par Bézout
Nouveau
En utilisant directement l'inverse de
a
a
a
modulo
n
n
n
lorsque
p
g
c
d
(
a
,
n
)
=
1
\mathrm{pgcd}(a,n) = 1
pgcd
(
a
,
n
)
=
1
:
x
≡
a
−
1
b
(
m
o
d
n
)
x \equiv a^{-1}b \pmod{n}
x
≡
a
−
1
b
(
mod
n
)
Nouveau
Comment trouver l'inverse d'un entier
a
a
a
modulo
n
n
n
?
En appliquant l'algorithme d'Euclide étendu pour obtenir
a
u
+
n
v
=
1
au + nv = 1
a
u
+
n
v
=
1
(Bézout, possible car
p
g
c
d
(
a
,
n
)
=
1
\mathrm{pgcd}(a,n) = 1
pgcd
(
a
,
n
)
=
1
) : l'inverse est
u
m
o
d
n
u \bmod n
u
mod
n
Nouveau
En appliquant le petit théorème de Fermat si
n
n
n
est premier :
a
−
1
≡
a
n
−
2
(
m
o
d
n
)
a^{-1} \equiv a^{n-2} \pmod{n}
a
−
1
≡
a
n
−
2
(
mod
n
)
Nouveau
Reconnaître
Maîtrise encore 2 méthodes pour débloquer cette étape.
Résoudre
Maîtrise encore 2 méthodes pour débloquer cette étape.