Arithmétique dans ℤ (3)
1.3 Algorithme d’Euclide
1.3.1 Théorème 1
Soient (a;b)∈IN*×ℤ tels 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)
ainsi Da∩Db=Da∩Dr.
Enfin a∧b =a∧r.
Exemple
Déterminer 320∧2350.
Correction
On utilise le théorème précédent
2350=7x320 + 110
320∧2350=320∧110
320=2.110+100
320∧110=110∧100
110= 1x100 + 10
110∧100=100∧10
100=10x10 + 0
le dérnier reste non nul est 10
donc 320∧2350= 10.
Ce procédure est appelé algorithme d’Euclide.
3.1.2 Cas général
Soit a; b∈ℤ tels que a<b ; b=qa+r et 0≤r<|a|.
a∧b=a∧r tel que 0≤r<|a|.
Si r=0 alors a∧b=a.
Si r≠0 alors a=q1.r+r1
et donc a∧b=r∧r1 tel que 0≤r1<r.
Si r1=0 alors a∧b=r.
Si r1≠0 alors r=q2.r1+r2
et donc a∧b=r1∧r2 tel que 0≤r2<r1.
Si r2=0 alors a∧b= r1.
Si r2≠0 alors r1=q3.r2+r3
et donc a∧b=r2∧r3 tel que 0≤r3<r2.
.......................
Si rn-1≠0 alors rn-2=qn.rn-1+rn
et donc a∧b=rn-1∧rn tel que 0≤rn<rn-1.
Supposons que rn=0 alors a∧b=rn-1 (le dérnier reste non nul)
sinon la suite (rn) d'entiers naturels est strictement décroissante et ce n'est pas possible.
Exercice 1 tp
Déterminer 7070∧123 en utilisant l'algorithme d'Euclide.
Correction
7070=57x123 + 59
0≤59<123
donc 7070∧123=123∧59.
123=2x59+5
0≤5<59
donc 123∧59=59∧5.
59= 11x5 + 4
0≤4<5
donc
59∧5=5∧4.
5=1x4+1
0≤1<4
donc 5∧4=4∧1.
4∧1=1x4 + 0
le dérnier reste non nul est 1
donc 7070∧123=1.
Exercice 2 tp
Déterminer 8070∧224 en utilisant l'algorithme d'Euclide.
3.1.3 Théorèmes
(∀(a;b)∈ℤ²)(∃(x;y)∈ℤ²): a∧b=xa+yb.
3.1.4 Théorème
(∀a;b;c∈ℤ): ca∧cb= |c|(a∧b).
(∀a;b;c∈ℤ): ca∨cb= |c|(a∨b).
Résultat
Soit (a;b)∈ℤ²
a∧b=d⇒(∀c∈ℤ*): ca∧cb=|c|d.
Exemple
45∧30=15
donc (-7x45)∧(-7x30)=7x15.