- 1 / 4 - AArriitthhm mééttiiqquuee ddaannss ZZ II.. DDiivviissiibbiilliittéé 11°°)) DDiivviissiibbiilliittéé ddaannss ZZ Déf : Soit , a b ∈ ℤ . On dit que a divise b ssi k ∃ ∈ ℤ tel que b ak = . On note alors ;;; a b et on dit que a est un diviseur de b et que b est un multiple de a . Prop : , , ;;; ( ) ;;; , ;;; ( ) a b a b a b a b ∀ ∈ ⇒ − − ℤ et ( ) ;;; ( ) a b − − . Prop : , a b ∀ ∈ ℤ avec 0 b ≠ . ;;; a b a b ⇒ ≤ . Déf : Pour a ∈ ℤ on note Div( ) a l’ensemble des diviseurs de a et Mul( ) a l’ensemble des multiples de a . Ainsi : { } Div( ) / ;;; a k k a = ∈ ℤ et { } Mul( ) / a ak k = ∈ ℤ (aussi noté aℤ ). Prop : ;;; a b et ;;; ;;; b c a c ⇒ , ;;; a b et ;;; b a a b ⇒ = , ;;; a b et ;;; ;;; ( ) a c a b c ⇒ + , ;;; a b et ;;; ;;; c d ac bd ⇒ , ;;; , ;;; p p a b p a b ⇒ ∀ ∈ ℕ . 22°°)) DDiivviissiioonn eeuucclliiddiieennnnee Théorème : 2 , , !( , ) a b q r ∗ ∀ ∈ ∀ ∈ ∃ ∈ ℤ ℕ ℤ tel que 0 a bq r r b  = +  ≤ <  . q et r sont respectivement appelés quotient et reste de la division euclidienne de a par b . (visualisation dans la barre de division). Prop : a ∀ ∈ ℤ et b ∗ ∀ ∈ ℕ , on a équivalence entre : (i) ;;; b a , (ii) le reste de la division euclidienne de a par b est nul. 33°°)) CCaallccuullss eenn ccoonnggrruueennccee Déf : Soit , a b ∈ ℤ . On dit que a est congru à b modulo n ssi ;;; ( ) n a b − . On note alors [ ] a b n = . Ainsi [ ] , . a b n k a b k n = ⇔ ∃ ∈ = + ℤ . Prop : { } , ! 0,1, , 1 a r n ∀ ∈ ∃ ∈ − ℤ … tel que [ ] a r n = . De plus r correspond au reste de la division euclidienne de a par n . Prop : [ ] [ ] a b n b a n = ⇔ = [ ] a b n = et [ ] [ ] b c n a c n = ⇒ = . Prop : Soit , , , a a b b ′ ′ ∈ ℤ vérifiant [ ] a a n ′ = et [ ] b b n ′ = . On a [ ] a b a b n ′ ′ + = + , [ ] ab a b n ′ ′ = , [ ] a a n ′ − = − et [ ] , p p p a a n ′ ∀ ∈ = ℕ . IIII.. PPG GCCDD eett PPPPCCM M 11°°)) PPG GCCDD ddee ddeeuuxx eennttiieerrss Déf : Soit , a b ∈ ℤ . Tout d ∈ ℤ tel que ;;; d a et ;;; d b est appelé diviseur commun à a et b . On note Div( , ) a b l’ensemble des diviseurs communs à a et b . Ainsi Div( , ) Div( ) Div( ) a b a b = ∩ . Prop : , a b ∀ ∈ ℤ tels que ( , ) (0,0) a b ≠ l’ensemble Div( , ) a b possède un plus grand élément. Déf : Soit , a b ∈ ℤ tels que ( , ) (0,0) a b ≠ . Le plus grand élément de Div( , ) a b est appelé pgcd de a et b . On le note pgcd( , ) a b ou encore a b ∧ . Convention : On pose pgcd(0,0) 0 = . Prop : , a b ∀ ∈ ℤ , pgcd( , ) a b ∈ ℕ , pgcd( , ) pgcd( , ) a b b a = et pgcd( , ) pgcd( , ) a b a b = .