Chapitre 16: Arithmétiques des entiers.
Dias du 30/12/2023
LM6E-BENGURIR–MPSI1
TADDIST ABDELJALIL
December 29, 2023
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 1 / 18
Plus grand commun diviseur.
Avant de commencer!
Oubliez tout ce que vous savez sur
l’arithmétique!!
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 2 / 18
Plus grand commun diviseur.
Avant de commencer!
Oubliez tout ce que vous savez sur
l’arithmétique!!
C’est parti !
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 2 / 18
Plus grand commun diviseur.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 3 / 18
Plus grand commun diviseur.
Théorème et définition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 3 / 18
Plus grand commun diviseur.
Théorème et définition
Soient a et b deux éléments de Z, non tous nuls, alors il éxiste un
unique c de N∗ tel que : a.Z + b.Z = c.Z.
c est dit pgcd de a et b noté : c = a ∧ b.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 3 / 18
Plus grand commun diviseur.
Théorème et définition
Soient a et b deux éléments de Z, non tous nuls, alors il éxiste un
unique c de N∗ tel que : a.Z + b.Z = c.Z.
c est dit pgcd de a et b noté : c = a ∧ b.
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 3 / 18
Plus grand commun diviseur.
Théorème et définition (Caractérisation du pgcd)
c= a ∧ b ⇔
c divise a et c divise b.
et
(∀d ∈ N∗ : d divise a et d divise b) ⇒ d divise c.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 4 / 18
Plus grand commun diviseur.
Théorème et définition (Caractérisation du pgcd)
c= a ∧ b ⇔
c divise a et c divise b.
et
(∀d ∈ N∗ : d divise a et d divise b) ⇒ d divise c.
Preuve (A faire à titre d’exo)
[A faire à titre d’exo]
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 4 / 18
Éléments premiers entre eux
Definition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
Preuve (A faire à titre d’exo)
Remarque
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
Preuve (A faire à titre d’exo)
Remarque
Retenons les remarques suivantes:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
Preuve (A faire à titre d’exo)
Remarque
Retenons les remarques suivantes:
Les entiers u0 et v0 sont dits coefficients de Bézout.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Definition
Deux entiers a et b sont dits premiers entre eux si a ∧ b = 1
Théorème (De Bézout)
∀(a, b) ∈ Z∗2 , ∃(u0 , v0 ) ∈ Z2 : a ∧ b = a.u0 + b.v0
Preuve (A faire à titre d’exo)
Remarque
Retenons les remarques suivantes:
Les entiers u0 et v0 sont dits coefficients de Bézout.
Le couple (u0 , v0 ) n’ est pas unique.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 5 / 18
Éléments premiers entre eux
Proposition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
2 a ∧b =1
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
2 a ∧b =1
3 aZ + bZ = Z.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
2 a ∧b =1
3 aZ + bZ = Z.
4 ∃(u0 , v0 ) ∈ Z2 : au0 + bv0 = 1.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
2 a ∧b =1
3 aZ + bZ = Z.
4 ∃(u0 , v0 ) ∈ Z2 : au0 + bv0 = 1.
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux
Proposition
∀(a, b) ∈ Z∗2 , on a équivalence entre:
1 a et b ont pour seuls diviseurs communs 1 et -1
2 a ∧b =1
3 aZ + bZ = Z.
4 ∃(u0 , v0 ) ∈ Z2 : au0 + bv0 = 1.
Preuve (A faire à titre d’exo)
Exercice
Montrer que si z est une racine n i ème et m i ème de l’unité, alors z est
une racine d i ème de l’unité avec d = pgcd (n, m).
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 6 / 18
Éléments premiers entre eux.
Théorème
∀(a, b, c) ∈ Z3 :
1 ac ∧ bc = |c|.a ∧ b
a b a∧b
2 c divise a et b alors c
∧ c
= |c|
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 7 / 18
Éléments premiers entre eux.
Théorème
∀(a, b, c) ∈ Z3 :
1 ac ∧ bc = |c|.a ∧ b
a b a∧b
2 c divise a et b alors c
∧ c
= |c| ! Notation à éviter
absolument !
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 7 / 18
Éléments premiers entre eux.
Théorème
∀(a, b, c) ∈ Z3 :
1 ac ∧ bc = |c|.a ∧ b
2 c divise a et b alors ac ∧ bc = a∧b
|c| ! Notation à éviter
absolument !
3 ∀(a, b, c) ∈ Z3 : (a ∧ c = 1 et a ∧ b = 1) ⇒ a ∧ bc = 1.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 7 / 18
Éléments premiers entre eux.
Théorème
∀(a, b, c) ∈ Z3 :
1 ac ∧ bc = |c|.a ∧ b
2 c divise a et b alors ac ∧ bc = a∧b
|c| ! Notation à éviter
absolument !
3 ∀(a, b, c) ∈ Z3 : (a ∧ c = 1 et a ∧ b = 1) ⇒ a ∧ bc = 1.
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 7 / 18
Éléments premiers entre eux.
Théorème ( De Gauss)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 8 / 18
Éléments premiers entre eux.
Théorème ( De Gauss)
(a, b, d ) ∈ Z3 : (d divise ab et a ∧ d = 1) ⇒ d divise b
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 8 / 18
Éléments premiers entre eux.
Théorème ( De Gauss)
(a, b, d ) ∈ Z3 : (d divise ab et a ∧ d = 1) ⇒ d divise b
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 8 / 18
Algorithme d’Euclide
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 9 / 18
Algorithme d’Euclide
Lemme
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 9 / 18
Algorithme d’Euclide
Lemme
1. si b divise a alors a ∧ b = |b|
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 9 / 18
Algorithme d’Euclide
Lemme
1. si b divise a alors a ∧ b = |b|
2. Si b ne divise pas a alors a ∧ b = b ∧ r , ou r est le reste de la
division euclidienne de a par b.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 9 / 18
Algorithme d’Euclide
Lemme
1. si b divise a alors a ∧ b = |b|
2. Si b ne divise pas a alors a ∧ b = b ∧ r , ou r est le reste de la
division euclidienne de a par b.
Proposition (Algorithme d’Euclide)
Le pgcd de a et b est le dernier reste non nul dans les divisions
successives de a par b.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 9 / 18
Algorithme d’Euclide: exemple.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
Tout commence avec les divisions euclidiennes successives de
l’algorithme d’Euclide :
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
Tout commence avec les divisions euclidiennes successives de
l’algorithme d’Euclide : PGCD(525, 3080) =
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
Tout commence avec les divisions euclidiennes successives de
l’algorithme d’Euclide : PGCD(525, 3080) =35
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
Tout commence avec les divisions euclidiennes successives de
l’algorithme d’Euclide : PGCD(525, 3080) =35
La voilà, notre identité de Bézout:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
Algorithme d’Euclide: exemple.
Cherchons par exemple le PGCD de 525 et 3080 ainsi qu’une identité
de Bézout associée.
Tout commence avec les divisions euclidiennes successives de
l’algorithme d’Euclide : PGCD(525, 3080) =35
La voilà, notre identité de Bézout:
3080 ∧ 525 = 35 = 7 × 3080 − 41 × 525
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 10 / 18
PGCD de k entiers
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 11 / 18
PGCD de k entiers
Definition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 11 / 18
PGCD de k entiers
Definition
1 Le pgcd c des k entiers a1 , . . . , ak est défini par récurrence par:
^ ^
ai = ( ai ) ∧ ak .
1≤i<k 1≤i≤k −1
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 11 / 18
PGCD de k entiers
Definition
1 Le pgcd c des k entiers a1 , . . . , ak est défini par récurrence par:
^ ^
ai = ( ai ) ∧ ak .
1≤i<k 1≤i≤k −1
L V
2 ai .Z = ( ai ).Z
1≤i≤k 1≤i≤k
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 11 / 18
PGCD de k entiers
Definition
1 Le pgcd c des k entiers a1 , . . . , ak est défini par récurrence par:
^ ^
ai = ( ai ) ∧ ak .
1≤i<k 1≤i≤k −1
L V
2 ai .Z = ( ai ).Z
1≤i≤k 1≤i≤k
V
3 (a1 , . . . ak ) sont dits premiers entre eux si ai = 1.
1≤i≤k
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 11 / 18
Plus petit commun multiple
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 12 / 18
Plus petit commun multiple
Théorème et définition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 12 / 18
Plus petit commun multiple
Théorème et définition
∀(a, b) ∈ Z × Z\{(0, 0)}, ∃!c ∈ N∗ tel que aZ ∩ bZ = cZ
c est dit plus petit commun multiple( en abrégé ppcm) de a et b
noté a ∨ b
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 12 / 18
Caractérisation du PPCM
Proposition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
c = ppcm(a, b)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
c = ppcm(a, b)
c est multiple commun de a et b
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
c = ppcm(a, b)
c est multiple commun de a et b
et
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
c = ppcm(a, b)
c est multiple commun de a et b
et ∀m ∈ Z : m multiple commun de a et b ⇒ c|m.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Caractérisation du PPCM
Proposition
Le plus petit commun multiple de a et b est effectivement le plus
petit commun multiple de a et b.
càd que les p.s.s.e:
c = ppcm(a, b)
c est multiple commun de a et b
et ∀m ∈ Z : m multiple commun de a et b ⇒ c|m.
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 13 / 18
Éléments premiers entre eux.
Proposition
∀(a, b, k ) ∈ Z∗3 : (ka ∨ kb) = |k |(a ∨ b) .
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 14 / 18
Éléments premiers entre eux.
Proposition
∀(a, b, k ) ∈ Z∗3 : (ka ∨ kb) = |k |(a ∨ b) .
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 14 / 18
Nombres premiers
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
Théorème
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
Théorème
Tout entier naturel superieur ou égal à 2 admet un diviseur
premier.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
Théorème
Tout entier naturel superieur ou égal à 2 admet un diviseur
premier.
L’ensemble des nombres premiers est infini.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
Théorème
Tout entier naturel superieur ou égal à 2 admet un diviseur
premier.
L’ensemble des nombres premiers est infini.
Deux nombres premiers distincts sont premiers entre eux.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Nombres premiers
Definition
Un entier naturel non nul est dit premier s’il est distinct de 1 et si
ses seuls diviseurs ( positifs !)sont 1 et lui même.
Théorème
Tout entier naturel superieur ou égal à 2 admet un diviseur
premier.
L’ensemble des nombres premiers est infini.
Deux nombres premiers distincts sont premiers entre eux.
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 15 / 18
Décomposition primaire d’un entier.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
Tout entier n non nul distinct de ±1 peut s écrire sous la forme:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
Tout entier n non nul distinct de ±1 peut s écrire sous la forme:
n = ±p1α1 . . . pkαk
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
Tout entier n non nul distinct de ±1 peut s écrire sous la forme:
n = ±p1α1 . . . pkαk
Les pj sont tous premiers,les αj ∈ N∗ .
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
Tout entier n non nul distinct de ±1 peut s écrire sous la forme:
n = ±p1α1 . . . pkαk
Les pj sont tous premiers,les αj ∈ N∗ .
En plus la décomposition précédente est unique à une permutation
près.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Décomposition primaire d’un entier.
Théorème (De décomposition)
Tout entier n non nul distinct de ±1 peut s écrire sous la forme:
n = ±p1α1 . . . pkαk
Les pj sont tous premiers,les αj ∈ N∗ .
En plus la décomposition précédente est unique à une permutation
près.
Preuve (A faire à titre d’exo)
Remarque
L’entier αi est dit valuation p − adique de l’entier n.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 16 / 18
Théorème
Si n = ε.p1α1 . . . pkαk et m = ε.q1β1 . . . qsβs les décompositions en
facteurs premiers de n et m, alors:
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 17 / 18
Théorème
Si n = ε.p1α1 . . . pkαk et m = ε.q1β1 . . . qsβs les décompositions en
facteurs premiers de n et m, alors:
n ∧ m = Q1γ1 . . . Qrγr et n ∨ m = Q1δ1 . . . , Qrδr
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 17 / 18
Théorème
Si n = ε.p1α1 . . . pkαk et m = ε.q1β1 . . . qsβs les décompositions en
facteurs premiers de n et m, alors:
n ∧ m = Q1γ1 . . . Qrγr et n ∨ m = Q1δ1 . . . , Qrδr
où
{Q1 , . . . , Qr } = {p1 , . . . , pk } ∪ {q1 , . . . , qs , }
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 17 / 18
Théorème
Si n = ε.p1α1 . . . pkαk et m = ε.q1β1 . . . qsβs les décompositions en
facteurs premiers de n et m, alors:
n ∧ m = Q1γ1 . . . Qrγr et n ∨ m = Q1δ1 . . . , Qrδr
où
{Q1 , . . . , Qr } = {p1 , . . . , pk } ∪ {q1 , . . . , qs , }
γj = inf(αj , βj ), δj = sup(αj , βj )
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 17 / 18
Théorème
Si n = ε.p1α1 . . . pkαk et m = ε.q1β1 . . . qsβs les décompositions en
facteurs premiers de n et m, alors:
n ∧ m = Q1γ1 . . . Qrγr et n ∨ m = Q1δ1 . . . , Qrδr
où
{Q1 , . . . , Qr } = {p1 , . . . , pk } ∪ {q1 , . . . , qs , }
γj = inf(αj , βj ), δj = sup(αj , βj )
Preuve (A faire à titre d’exo)
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 17 / 18
Exemple
Exemple
Le PGCD de 300 et 740 est
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 18 / 18
Exemple
Exemple
Le PGCD de 300 et 740 est 20 = 22 × 5 car
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 18 / 18
Exemple
Exemple
Le PGCD de 300 et 740 est 20 = 22 × 5 car 300 = 22 × 3 × 52 et
740 = 22 × 5 × 37.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 18 / 18
Exemple
Exemple
Le PGCD de 300 et 740 est 20 = 22 × 5 car 300 = 22 × 3 × 52 et
740 = 22 × 5 × 37.
Voyez comme c’est facile! Il est interdit de ne pas savoir faire cela.
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 18 / 18
Fin du chapitre 16
Merci
LM6E-BENGURIR–MPSI1 TADDIST ABDELJALIL
Chapitre 16: Arithmétiques des entiers. December 29, 2023 18 / 18
