Faculté des Sciences ; Rabat Arithmétique (Prérequis)

Niveau Bac 2 ; Sciences Maths

Théorème "Division euclidienne" : ∀(𝑎, 𝑏) ∈ ℤ × ℤ∗ , (q,r) ∈ ℤ × ℕ∗ , a = b.q + r avec 0 r < |b|
 Cette opération s’appelle « la division euclidienne de a par b ».
 Les nombres a, b, q et r sont appelés respectivement le dividende, le diviseur, le quotient et le reste de cette division

La division Les classes d’équivalences La congruence

Soit (𝑎, 2
𝑏) ∈ ℤ . S’il existe un entier Soient (𝑎, 𝑛) ∈ ℤ × ℕ∗ et r le reste de la division Soit (𝒂, 𝒃, 𝒏) ∈ ℤ × ℤ × ℕ∗ .
relatif k tel que a = kb, on dit que : euclidienne de a par n. L’ensemble des entiers Si 𝑛/𝑏 − 𝑎, on dit que a et b sont congrus
 b divise a relatifs qui ont le même reste r de la division par modulo n et on note :
 b est un diviseur de a n est appelé la classe d’équivalence de a a  b [n] ou a  b mod(n)
 a est un multiple de b modulo n. Il est noté par 𝑎̅ 𝑛 , ou simplement 𝑎̅.
On note : b / a. ̅𝒂 = {𝒃 ∈ ℤ/∃𝒌 ∈ ℤ, 𝒃 = 𝒌𝒏 + 𝒓 }
 b/a ⇔ b/−a ⇔ −b/−a  𝒂 ̅=𝒃 ̅ ⇔ 𝒃∈ 𝒂 ̅  a  b [n] ⇔ a  b [n]
 b/a et a/b ⇔ |b| = |a|  ∀𝒂 ∈ ℤ, ∃! 𝒓 ∈ {𝟎; 𝟏; … ; 𝒏 − 𝟏}: 𝒂 ̅ = 𝒓̅ ⇔ ∃k ∈ ℤ; b = a + kn
 a/b et a′/b′ ⇒ aa′/bb′  L’ensemble des classes d’équivalences  Si n˄c =d, alors :
 x/a et a/z ⇒ x/z n
modulo n sera noté par ℤ/𝑛ℤ. ac = bc[n] ⇔ a = b[ ]
 Si a/b et b0 alors ab. Et on a : ℤ/𝒏ℤ = {𝟎 ̅; 𝟏̅; ⋯ ; ̅̅̅̅̅̅̅̅
𝒏−𝟏} d
 a/b et a/c ⇒ a/α. b + β. c ̅ est l’ensemble de multiples de n  a  b [n] et m/n ⇒ a  b [m]
 𝟎
̅ ⇔ 𝒏/𝒙  a˄n =1⇔ ∃m ∈ ℤ; am  1[n]
 𝒙 ̅=𝟎
𝒏/𝒃 − 𝒂 ⟺ ̅̅̅̅̅̅̅
𝒃−𝒂=𝟎 ̅ ⟺ ̅=𝒂
𝒃 ̅ ⟺ a  b [n] ⇔ ∃𝒌 ∈ ℤ; 𝒃 = 𝒂 + 𝒌𝒏
Théorème de Fermat Si a̅ = b̅ et x̅ = y̅, alors : Si a  b [n] et x  y [n], alors :
Soit p un nombre premier et a un entier:  ̅̅̅̅̅̅̅̅̅̅̅̅
α. a + β. x = ̅̅̅̅̅̅̅̅̅̅̅̅̅
α. b + β. y ∀(α, β) ∈ ℤ2  α. a + β. x  α. b + β. y [n] ∀(α, β) ∈ ℤ2
- Si p ne divise pas a, alors ap-1 ≡ 1 [p]. a. x = ̅̅̅̅
 ̅̅̅̅ b. y  a. x  b. y [n]
- Pour tout entier x, xp≡ x [p]. ̅̅̅
a =bk ̅̅̅
k ∀k ∈ ℕ  ak  bk [n] ∀k ∈ ℕ
Addition et produit des classes d’équivalence : Théorème : Soient 0 ≤ 𝑎 < 𝑛 𝑒𝑡 0 ≤ 𝑏 < 𝑛 .
Soit ℤ/𝑝ℤ avec p un nombre premier : a̅ + b̅ = ̅̅̅̅̅̅̅
a+b et a̅. b̅ = ̅̅̅̅
a. b On a :
̅𝟎
∀𝒂 ̅𝟎
̅, ∃𝒃 ̅: 𝒂
̅𝒃̅=𝟏 ̅ ̅̅̅̅̅̅̅̅̅̅̅̅ ̅
 α. a + β. x = α.̅a + β. b ∀(α, β) ∈ ℤ2 𝒂 = 𝒃[𝒏] ⇔ a=b
 ̅̅̅̅
ak = ̅𝑎𝑘 ∀k ∈ ℕ

1/2 Arithmétique (Prof. Bennis)

 Nombres premiers PGCD PPCM
Un entier relatif p est dit premier s’il admet Soient a et b deux entiers non tous deux nuls. Soient a et b des entiers non nuls.
que quatre diviseurs : p, -p, 1 et -1. Le plus grand commun diviseur de a et b le plus petit commun multiple de a et b (noté
Crible d’Ératosthène : Si un entier (noté pgcd (a,b) ou a˄b ) est le plus grand entier ppcm(a,b) ou a˅b ) est le plus petit entier
naturel a n’est pas premier, alors il admet positif divisant à la fois a et b. positif qui est à la fois multiple de a et de b.
Deux entiers non nuls sont dits premiers entre
un diviseur premier p vérifiant p2a.
eux lorsque a˄b = 1
En pratique : Si tous les nombres
 a˄1 = 1; a˄0 =|a|; a˄b= b˄a  a ˅ 1 = |a| ; a˅0 =0
premiers p vérifiant p√𝑎 ne divisent
 a/b  a˄b = |a|  a/b  a˅b = |b|.
pas n, alors n est aussi premier.
 (ka)˄(kb) =|k|  (a˄b)  ka˅kb = |k|  (a˅b)
Théorème : L’ensemble des nombres 𝑎 𝑏 1 𝑎 𝑏 1
premiers est infini.  k/a et k /b ⟹ ˄ =  (a˄b)  k/a et k/b ⟹ ˅ =  (a˅b)
𝑘 𝑘 |𝑘| 𝑘 𝑘 |𝑘|
Le théorème fondamental de  a˄b=1 et a˄c=1 ⟹ a˄bc=1
l’arithmétique : Tout entier non nul a ≠ En particulier : a˄b=1 ⟹ 𝑎𝑛 ˄𝑏 𝑚 =1 pour tous  (a˄b)  (a˅b) = |ab|
1 et -1 se décompose d’une manière m et n de ℕ∗ . En particulier : Si a˄b=1, alors a˅b = |ab|
unique en produit de nombres premier :  Si a/n et b/n et si a˄b = 1, alors ab/n.
𝛼 𝛼
𝑎 = 𝜀 𝑝1 1 ⋯ 𝑝𝑛 𝑛 d/a et d/b  d/( a˄b) a/m et /m  (a˅b)/m.
tel que les 𝑝𝑖 sont des nombres premiers Théorème de Gauss : Théorème de Bézout
positifs différents deux à deux et tel que a/bc et a˄b = 1 ⟹ a/c  a˄b =d ⟹ ∃(𝑢, 𝑣) ∈ ℤ2 : 𝑢𝑎 + 𝑣𝑏 = d
𝜀 = 1 si 𝑎 > 0 et 𝜀 = −1 si 𝑎 < 0.  a˄b =1 ⟺ ∃(𝑢, 𝑣) ∈ ℤ2 : 𝑢𝑎 + 𝑣𝑏 = 1
Conséquence:
Le nombre des diviseurs positifs de a est : Les équations diophantiennes :
N=(1+𝛼1 ) ⋯ (1 + 𝛼𝑛 ). Une équation diophantienne d’inconnue le couple (x,y) ∈ ℤ2 est de la forme : (*) ax + by = c
avec a , b et c des entiers.
Pour un nombre premier p on a :
…. .

 L’équation (*) a des solutions si et seulement si a˄b /c.

 p ne divise pas x  p ˄ x = 1  Si (𝑥0 , 𝑦0 ) est une solution de l’équation (*), alors l’ensemble de solutions de (*) s’écrit de la
 p/ab  p/a ou p/b 𝑏 𝑎
forme : 𝑆 = {(𝑥0 + 𝑘𝑏0 ; 𝑦0 + 𝑘𝑎0 )/𝑘 ∈ ℤ} avec 𝑏0 = a˄b et 𝑎0 = a˄b
 p/𝑎𝑛  p/a

2/2 Arithmétique (Prof. Bennis)