Arithmétique (1)
1- Division euclidienne et nombres premiers entre eux
1.1 Division euclidienne
1.1.1 Définition
Soient a; b∈ℤ
a|b ⇔ ∃t∈ℤtel que b=ta.
1.1.2 Théorème et définition
Soit (a;b)∈IN*×ℤ
(∃(q,r)∈ℤ×IN*) tel que b=aq+r et 0≤r<a.
q est appelé quotient et r est appelé reste.
Le procédure qui permet de trouver le couple (q;r) est appelé division euclidienne de b par a.
Exemple
1) On pose b=17 et a=5
17=5.3+2 donc q=3 et r=2 tel que 0≤2<<5.
2) 21 = 7x3 + 0 donc q=3 et r=0.
Remarque
Si r=0 alors a divise b et on écrit a|b.
1.1.3 Propriétés
Propriétés 1
Soient a;b;c∈ℤ
1) a|0 ; a|a
2) a|b et b|a⇔|a|=|b|
3) Transitivité: a|b et b|c⇒a|c
4) a|b⇒a|bc
(la réciproque est fausse 3|18 et 9|18 mais 3.9 ne divise pas 18)
Propriété 2
Soient a;b;c∈ℤ
(a|b et a|c) ⇒ (∀(x;y)∈ℤ²): a|xb+yc
Démonstration
a|b donc b=ka avec k∈Z et a|c donc c=k'a
ce qui donne xb+yc=xka+yk'a=a(xk+yk')
Puisque xk+yk'∈Z alors a|xb+yc.
Propriétés 3
Soient a;b;c∈ℤ
1) ac|b ⇒ (a|b et c|b).
2) (∀n∈IN*): an|b ⇒ a|b.
1.1.4 Le pgcd et le ppcm
Le plus petit commun multiple
Soit (a;b)∈ℤ².
Le plus petit entier positif des multiples de a et b est appelé le plus petit commun multiple de a et b et est est noté a∨b ou ppcm(a;b).
Le plus grand commun diviseur
Soit (a;b) ∈ℤ².
Le plus grand entier positif des diviseurs de a et b est appelé le plus grand commun diviseur de a et b et est noté a∧b ou pgcd(a;b).
Exemple 75∧50=25 et 24∨14=84
1.4 Algorithme d’Euclide
Théorème d’Euclide
Soit (a;b)∈IN*×ℤ tel que a<b
b=qa+r et 0≤r<|a|.
(a∧b) = (a∧r)
Démonstration
On désigne par Da; Db et Dr les ensembles respectifs des diviseurs de a; b et r.
Il suffit de montrer que Da∩Db Da∩Dr.
rappel 1 (E=F⇔E⊂F et F⊂E)
Soit d∈Da∩Db donc d|a et d|b.
rappel 2 (p|e et p|f⇒ ∀(x;y)∈ℤ²: p|xe+yf)
On a b=qa+r ou encore b-qa=r
donc d|b-qa ou encore d|r
ainsi d∈Da∩Dr alors (Da∩Db)⊂(Da∩Dr).
Soit d∈(Da ∩ Dr) donc d|a et d|r
on a b=qa+r donc d|b ainsi d∈(Da∩Db) et donc (Da∩Dr)⊂(Da ∩ Db)
alors Da∩Db=Da∩Dr
Finalement a∧b=a∧r.
Exemple Déterminer 310 ∧ 1030.
Correction
1030 = 3.310 + 100
310∧1030 = 310∧100
310 = 3.100 + 10
310∧100 = 100∧10
100 = 10.10 + 0
le dérnier reste non nul est 10 donc 310∧1030=10.
Ce procédure est appelée Algorithme d’Euclide.
Théorèmes
(∀(a;b)∈ℤ²)(∃(x;y)∈ℤ²): a∧b= xa+yb.