Ressources mathématiques > Capes >
Accéder à mon compte > Accéder à ma feuille d'exercices >


Démonstrations capes - Arithmétique
Division euclidienne dans $mathbb N
Soient aa et bb deux entiers naturels avec b ≠ 0 b ≠ 0. Alors il existe un unique couple
d'entiers (q, r) (q, r) tel que a = bq + r a = bq + r et 0 ≤ r < b0 ≤ r < b.

Démonstration

Prouvons d'abord l'unicité. Si a = bq + r = bq ′ + r ′ a = bq + r = bq ′ + r ′
, avec 0 ≤ r < b0 ≤ r < b
et 0 ≤ r ′ < b 0 ≤ r ′ < b
, alors en effectuant la différence, on trouve 0 = b(q − q ′ ) + r − r ′
0 = b(q − q ′ ) + r − r ′
, c'est-à-dire

r − r ′ = b(q′ − q).

r − r ′ = b(q ′ − q).

Mais, puisque 0 ≤ r < b0 ≤ r < b
et −b < r ′ ≤ 0 − b < r ′ ≤ 0
, on a −b < r − r ′ < b− b < r − r ′ < b
et donc |r − r ′ | < b | r − r ′ | < b
. Si q ′ q ′
était différent de qq
, alors |b(q ′ − q)| | b(q ′ − q) |
serait supérieur ou égal à bb
, une contradiction. Donc r = r ′ r = r ′
et b = b ′ b = b ′
.

Prouvons maintenant l'existence. Si aa
est un multiple de bb
, le résultat est évident, avec r = 0 r = 0
. Sinon, puisque (a + 1)b > a(a + 1)b > a
, alors aa
est compris entre deux multiples consécutifs de bb
. Autrement dit, il existe q ∈ ℕq ∈ N
tel que qb < a < (q + 1)bqb < a < (q + 1)b
. Posons alors r = a − qb r = a − qb
. Il vient 0 < r < b0 < r < b
, et donc le couple (q, r) (q, r)
convient.
Division euclidienne dans ℤ Z
Soient aa et bb deux entiers relatifs avec b ≠ 0 b ≠ 0. Alors il existe un unique couple d'entiers
(q, r)(q, r) avec a = bq + r a = bq + r et 0 ≤ r < |b|0 ≤ r < | b | .

Démonstration

L'unicité se prouve exactement de la même façon que dans ℕ N
. Prouvons maintenant l'existence. On l'a déjà fait si a ≥ 0 a ≥ 0
et b > 0 b > 0
. Supposons ensuite a < 0 a < 0
et b > 0 b > 0
. Si aa
est un multiple de bb
, le résultat est évident. Sinon, effectuons la division euclidienne de −a − a
par bb
. Il existe un couple d'entiers (q 1 , r 1 ) (q 1, r 1)
avec 0 < r 1 < b 0 < r 1 < b
tels que −a = bq 1 + r 1 − a = bq 1 + r 1
. Prenant l'opposé de cette équation, on trouve a = b(−q 1 ) − r 1 a = b( − q 1) − r 1
. Malheureusement, −r 1 − r 1
n'est pas élément de [0, b[ [0, b[
, mais il le devient si on ajoute bb
. Concrètement, on a donc

a = b(−q1 ) + r 1 + b − b = b(−q1 − 1) + r 1 + b.
a = b( − q 1) + r 1 + b − b = b( − q 1 − 1) + r 1 + b.

On pose alors q = −q 1 − 1 q = − q 1 − 1
et r = r 1 + b r = r 1 + b
. Puisque −b < r 1 < 0 − b < r 1 < 0
, on a bien 0 < r 1 + b = r < b 0 < r 1 + b = r < b
.

On traite enfin le cas a < 0 a < 0
et b < 0 b < 0
. Comme précédemment, si aa
est un multiple de bb
, il n'y a rien à faire. Sinon, on effectue la division euclidienne de −a − a
par −b − b
: il existe un couple d'entiers (q 1 , r 1 ) (q 1, r 1)
tels que −a = −bq 1 + r 1 − a = − bq 1 + r 1
avec 0 < r 1 < b 0 < r 1 < b
. Prenant l'opposé, on trouve

a = bq1 − r 1 = b(q1 − 1) + (r 1 + b).
a = bq 1 − r 1 = b(q 1 − 1) + (r 1 + b).

On conclut exactement comme ci-dessus en posant q = q 1 − 1 q = q 1 − 1
 et r = r 1 + b r = r 1 + b
.


Algorithme d'Euclide
Soient aa et bb deux entiers avec bb non-nul et soit r r le reste dans la division euclidienne de
aa par bb. Alors pgcd(a, b) = pgcd(b, r). pgcd(a, b) = pgcd(b, r).

Démonstration

Il suffit de prouver que l'ensemble des diviseurs communs à aa
et bb
est égal à l'ensemble des diviseurs communs de bb
et de r r
. Écrivons donc a = bq + r a = bq + r
et soit d d
un diviseur commun de aa
et de bb
. Alors, écrivant r = a − bq r = a − bq
, dd
divise aussi r r
et c'est donc un diviseur commun à bb
et r r
.

Réciproquement, si d d
est un diviseur commun de bb
et de r r
, écrivant a = bq + r a = bq + r
, on trouve que d d
divise aa
, et donc que d d
est un diviseur commun de aa
et bb
.


Égalité de Bézout
Soit a, ba, b deux entiers dont l'un est non-nul et d d leur pgcd. Alors il existe u, v ∈ ℤ u, v ∈ Z
tels que au + bv = d au + bv = d.

Démonstration

Si on veut faire la démonstration "niveau Terminale", on doit la faire sans certains outils,
comme la notion de sous-groupes de ℤZ
. Mais on va imiter la preuve du fait que les sous-groupes de ℤZ
sont les nℤ nZ
. On peut supposer que aa
est non-nul. On note

G = {au + bv; (u, v) ∈ ℤ2 } ∩ ℕ ∗ .

G = {au + bv; (u, v) ∈ Z 2} ∩ N ∗ .
Alors GG
est non-vide car |a| | a |
est élément de GG
. Notons DD
le plus petit élément de GG
. On va prouver que D = d D = d
, le pgcd de aa
et bb
.

D'une part, puisque D ∈ GD ∈ G
, DD
s'écrit D = au + bvD = au + bv
. Puisque d|a d | a
et que d|b d | b
, alors d|D d | D
et donc d ≤ D d ≤ D
.

D'autre part, on va démontrer que DD
divise aa
et que DD
divise bb
. Ainsi, on aura aussi D|d D | d
, donc D ≤ d D ≤ d
, ce qui prouvera que D = d D = d
. Pour prouver que DD
divise aa
, effectuons la division euclidienne de aa
par DD
: a = Dq + r a = Dq + r
, avec 0 ≤ r ≤ D − 1 0 ≤ r ≤ D − 1
. On isole le reste, et on remplace DD
par au + bv au + bv
. Il vient

r = a − Dq = a − (au + bv) = a(1 − uq) + bvq.
r = a − Dq = a − (au + bv) = a(1 − uq) + bvq.

Mais alors, r = 0 r = 0
car sinon, r ∈ G r ∈ G
avec r < D r < D
ce qui contredit la définition de DD
. Donc D|a D | a
. Le même raisonnement, mais en effectuant cette fois la division euclidienne de bb
par DD
, prouve que D|b D | b
.

On peut donner une autre démonstration, par récurrence. Remarquons d'abord que,
quitte à échanger le rôle de aa
et de bb
, et à changer uu
en −u − u
et/ou v v
en −v − v
, on peut supposer a ≥ b ≥ 0 a ≥ b ≥ 0
et a ≠ 0 a ≠ 0
. Soit n ≥ 1 n ≥ 1
et notons (n) P(n)
la propriété suivante : ``Pour tout (a, b) ∈ ℕ 2 (a, b) ∈ N 2
avec n ≥ a ≥ b n ≥ a ≥ b
et a ≠ 0 a ≠ 0
, il existe (u, v) ∈ ℤ2 (u, v) ∈ Z 2
tels que au + bv = d au + bv = d
, où d = pgcd(a,b)d = pgcd(a,b)
''. On va prouver par récurrence que pour tout n ≥ 1 n ≥ 1
, la propriété (n) P(n)
est vraie. Remarquons d'abord que (1) P(1)
est vraie. En effet, les seuls cas possibles sont (a, b) = (1, 0) (a, b) = (1, 0)
et (a, b) = (1, 1) (a, b) = (1, 1)
. Dans les deux cas, le pgcd est 1 et on peut choisir u = 1 u = 1
, v = 0v = 0
. Soit maintenant n ≥ 1 n ≥ 1
tel que (n) P(n)
est vraie, et démontrons (n + 1) P(n + 1)
. On fixe donc a, b ∈ ℕ 2 a, b ∈ N 2
tels que n + 1 ≥ a ≥ b n + 1 ≥ a ≥ b
et a ≠ 0 a ≠ 0
. On distingue trois cas :

Si b = n + 1b = n + 1, alors a = b = d = n + 1a = b = d = n + 1 et on peut choisir
u = 1 u = 1 et v = 0 v = 0.
Si b = 0 b = 0, alors d = a d = a et on peut choisir là aussi u = 1 u = 1 et v = 0
v = 0.
Sinon, on a nécessairement 1 ≤ b ≤ n 1 ≤ b ≤ n
. Notons r r
le reste dans la division euclidienne de aa
par bb
: a = bq + r a = bq + r
avec 0 ≤ r < b0 ≤ r < b
. On sait que d = pgcd(a, b) = pgcd(b, r) d = pgcd(a, b) = pgcd(b, r)
. Alors, en appliquant l'hypothèse de récurrence au couple (b, r) (b, r)
, on sait qu'il existe u 1 u 1
et v 1 v 1
des entiers tels que bu 1 + rv 1 = d bu 1 + rv 1 = d
. Remplaçant r r
par sa valeur, il vient

bu1 + (a − bq)v 1 = d ⟺ av 1 + b(u1 − qv 1 ) = d.
bu 1 + (a − bq)v 1 = d ⟺ av 1 + b(u 1 − qv 1) = d.

On en déduit que (n + 1) P(n + 1)
est vraie, avec u = v 1 u = v 1
et v = u 1 − qv 1 v = u 1 − qv 1
. Par le principe de récurrence, (n) P(n)
 est vraie pour tout entier nn
.

Remarquons pour cette démonstration l'importance de mettre le quantificateur
∀(a, b) ∈ ℕ 2 ∀(a, b) ∈ N 2
à l'intérieur de (n) P(n)
, puisqu'on applique (n) P(n)
non pas à aa
et bb
, mais à r r
et bb
.


Théorème de Bézout
Deux entiers aa et bb sont premiers entre eux si et seulement s'il existe deux entiers uu et v v
tels que au + bv = 1au + bv = 1.

Démonstration

Le sens direct est l'égalité de Bézout démontrée ci-dessus. Le sens réciproque est très
facile. En effet, si d|a d | a
et d|b d | b
, alors d|au + bv = 1 d | au + bv = 1
, et donc tout diviseur commun à aa
et bb
divise 11
(et est donc égal à 11
ou −1 − 1
). Ainsi, le pgcd de aa
et de bb
est égal à 11
.


Lemme de Gauss
Soit a, b, c a, b, c des entiers tels que a|bca | bc et a ∧ b = 1 a ∧ b = 1. Alors a|c a | c.

Démonstration

C'est une conséquence du théorème de Bézout. En effet, l'hypothèse a|bca | bc
donne l'existence d'un entier k k
tel que bc = ka bc = ka
. Puisque a ∧ b = 1 a ∧ b = 1
, on sait également qu'il existe un couple d'entiers (u, v) (u, v)
tel que au + bv = 1au + bv = 1
. On multiplie par c c
cette dernière égalité, et on trouve auc + bvc = c auc + bvc = c
, soit a...